000			02209nam a22003378i 4500
001			CR9781139814782
003			UkCbUP
005			20200124160246.0
006			m|||||o||d||||||||
007			cr||||||||||||
008			121011s2014||||enk o ||1 0|eng|d
020			_a9781139814782 (ebook)
020			_z9781107038325 (hardback)
020			_z9781107471542 (paperback)
040			_aUkCbUP _beng _erda _cUkCbUP
050	0	0	_aQA76.9.M35 _bO36 2014
082	0	0	_a004.01/51 _223
100	1		_aO'Donnell, Ryan, _d1979- _eauthor.
245	1	0	_aAnalysis of boolean functions / _cRyan O'Donnell, Carnegie Mellon University, Pittsburgh, Pennsylvania.
264		1	_aCambridge : _bCambridge University Press, _c2014.
300			_a1 online resource (xx, 423 pages) : _bdigital, PDF file(s).
336			_atext _btxt _2rdacontent
337			_acomputer _bc _2rdamedia
338			_aonline resource _bcr _2rdacarrier
500			_aTitle from publisher's bibliographic system (viewed on 05 Oct 2015).
520			_aBoolean functions are perhaps the most basic objects of study in theoretical computer science. They also arise in other areas of mathematics, including combinatorics, statistical physics, and mathematical social choice. The field of analysis of Boolean functions seeks to understand them via their Fourier transform and other analytic methods. This text gives a thorough overview of the field, beginning with the most basic definitions and proceeding to advanced topics such as hypercontractivity and isoperimetry. Each chapter includes a 'highlight application' such as Arrow's theorem from economics, the Goldreich-Levin algorithm from cryptography/learning theory, Håstad's NP-hardness of approximation results, and 'sharp threshold' theorems for random graph properties. The book includes roughly 450 exercises and can be used as the basis of a one-semester graduate course. It should appeal to advanced undergraduates, graduate students and researchers in computer science theory and related mathematical fields.
650		0	_aComputer science _xMathematics.
650		0	_aAlgebra, Boolean.
776	0	8	_iPrint version: _z9781107038325
856	4	0	_uhttps://doi.org/10.1017/CBO9781139814782
999			_c518960 _d518958