### Skapa referens, olika format (klipp och klistra)

**Harvard**

Isaksson, M. (2010) *Topics in Hardness of Approximation and Social Choice Theory*. Göteborg : Chalmers University of Technology (Doktorsavhandlingar vid Chalmers tekniska högskola. Ny serie, nr: 3073).

** BibTeX **

@book{

Isaksson2010,

author={Isaksson, Marcus},

title={Topics in Hardness of Approximation and Social Choice Theory},

isbn={978-91-7385-392-7},

abstract={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.},

publisher={Institutionen för matematiska vetenskaper, matematisk statistik, Chalmers tekniska högskola,},

place={Göteborg},

year={2010},

series={Doktorsavhandlingar vid Chalmers tekniska högskola. Ny serie, no: 3073},

keywords={Hardness of approximation, social choice theory, Gibbard-Satterthwaite, max-q-cut, Condorcet voting, linear threshold functions.},

note={156},

}

** RefWorks **

RT Dissertation/Thesis

SR Electronic

ID 120378

A1 Isaksson, Marcus

T1 Topics in Hardness of Approximation and Social Choice Theory

YR 2010

SN 978-91-7385-392-7

AB 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.

PB Institutionen för matematiska vetenskaper, matematisk statistik, Chalmers tekniska högskola,

T3 Doktorsavhandlingar vid Chalmers tekniska högskola. Ny serie, no: 3073

LA eng

LK http://publications.lib.chalmers.se/records/fulltext/120378.pdf

OL 30