Till sidans topp

Sidansvarig: Webbredaktion
Sidan uppdaterades: 2012-09-11 15:12

Tipsa en vän
Utskriftsversion

Topics in Hardness of App… - Göteborgs universitet Till startsida
Webbkarta
Till innehåll Läs mer om hur kakor används på gu.se

Topics in Hardness of Approximation and Social Choice Theory

Doktorsavhandling
Författare Marcus Isaksson
Datum för examination 2010-05-24
Opponent at public defense Associate Professor Subhash Khot, New York University, USA.
ISBN 978-91-7385-392-7
Förlag Chalmers University of Technology
Förlagsort Göteborg
Publiceringsår 2010
Publicerad vid Institutionen för matematiska vetenskaper, matematisk statistik
Språk en
Ämnesord Hardness of approximation, social choice theory, Gibbard-Satterthwaite, max-q-cut, Condorcet voting, linear threshold functions.
Ämneskategorier Teoretisk datalogi

Sammanfattning

Tools from Fourier analysis of Boolean functions have commonly been used to prove results both in hardness of approximation in computer science and in the study of voting schemes in social choice theory. In this thesis we consider various topics in both these contexts. In hardness of approximation we study the asymptotic approximation curve of MAX-CSP's for predicates given by linear threshold functions and prove upper and lower bounds for this curve for majority-like threshold functions. We also relate the hardness of MAX-q-CUT to a conjecture in Gaussian isoperimetry and the plurality is stablest conjecture in social choice. In particular the Frieze-Jerrum semidefinite programming based algorithm for MAX-q-CUT achieves the optimal approximation factor assuming the unique games conjecture if plurality is indeed stablest. In social choice theory we show a quantitative version of the Gibbard-Satterthwaite Theorem, showing that for election schemes in elections with more than 2 candidates, situations in which a voter has an incentive to manipulate by not voting according to his true preference are common enough that they cannot completely be masked behind computational hardness. We also prove a generalization of a Gaussian isoperimetric result by Borell and show that it implies that the majority function is optimal in Condorcet voting in the sense that it maximizes the probability that there is a single candidate which the society prefers over all other candidates.

Sidansvarig: Webbredaktion|Sidan uppdaterades: 2012-09-11
Dela:

På Göteborgs universitet använder vi kakor (cookies) för att webbplatsen ska fungera på ett bra sätt för dig. Genom att surfa vidare godkänner du att vi använder kakor.  Vad är kakor?