CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Topics in Hardness of Approximation and Social Choice Theory

Marcus Isaksson (Institutionen för matematiska vetenskaper, matematisk statistik)
Göteborg : Chalmers University of Technology, 2010. ISBN: 978-91-7385-392-7.- 156 s.

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.

Nyckelord: Hardness of approximation, social choice theory, Gibbard-Satterthwaite, max-q-cut, Condorcet voting, linear threshold functions.

Denna post skapades 2010-04-26. Senast ändrad 2013-09-25.
CPL Pubid: 120378


Läs direkt!

Lokal fulltext (fritt tillgänglig)

Institutioner (Chalmers)

Institutionen för matematiska vetenskaper, matematisk statistik (2005-2016)


Teoretisk datalogi

Chalmers infrastruktur


Datum: 2010-05-24
Tid: 13:15
Lokal: Sal Euler, Matematiska Vetenskaper, Chalmers tvärgata 3, Göteborg
Opponent: Associate Professor Subhash Khot, New York University, USA.

Ingår i serie

Doktorsavhandlingar vid Chalmers tekniska högskola. Ny serie 3073