@inproceedings{Bhatt:2016,

  author    = {Arnab Bhattacharyya and

               Sivakanth Gopi},

  title     = {Lower Bounds for Constant Query Affine-Invariant LCCs and LTCs},

  booktitle = {31st Conference on Computational Complexity, {CCC} 2016, May 29 to

               June 1, 2016, Tokyo, Japan},

  pages     = {12:1--12:17},

  year      = {2016},

  crossref  = {DBLP:conf/coco/2016},

  url       = {http://dx.doi.org/10.4230/LIPIcs.CCC.2016.12},

  doi       = {10.4230/LIPIcs.CCC.2016.12},

  timestamp = {Thu, 02 Jun 2016 21:25:13 +0200},

  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/coco/BhattacharyyaG16},

  bibsource = {dblp computer science bibliography, http://dblp.org}

}

@proceedings{DBLP:conf/coco/2016,

  editor    = {Ran Raz},

  title     = {31st Conference on Computational Complexity, {CCC} 2016, May 29 to

               June 1, 2016, Tokyo, Japan},

  series    = {LIPIcs},

  volume    = {50},

  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},

  year      = {2016},

  url       = {http://www.dagstuhl.de/dagpub/978-3-95977-008-8},

  isbn      = {978-3-95977-008-8},

  timestamp = {Thu, 02 Jun 2016 21:24:46 +0200},

  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/coco/2016},

  bibsource = {dblp computer science bibliography, http://dblp.org}

}

@article {Tao:2012a,

    AUTHOR = {Tao, Terence and Ziegler, Tamar},

     TITLE = {The inverse conjecture for the {G}owers norm over finite

              fields in low characteristic},

   JOURNAL = {Ann. Comb.},

  FJOURNAL = {Annals of Combinatorics},

    VOLUME = {16},

      YEAR = {2012},

    NUMBER = {1},

     PAGES = {121--188},

      ISSN = {0218-0006},

   MRCLASS = {11B30 (11T06)},

  MRNUMBER = {2948765},

MRREVIEWER = {Tom Sanders},

       DOI = {10.1007/s00026-011-0124-3},

       URL = {http://dx.doi.org/10.1007/s00026-011-0124-3},

}

@book {Tao:2012b,

    AUTHOR = {Tao, Terence},

     TITLE = {Higher order {F}ourier analysis},

    SERIES = {Graduate Studies in Mathematics},

    VOLUME = {142},

 PUBLISHER = {American Mathematical Society, Providence, RI},

      YEAR = {2012},

     PAGES = {x+187},

      ISBN = {978-0-8218-8986-2},

   MRCLASS = {11B30 (11L07 11U07 37A45)},

  MRNUMBER = {2931680},

MRREVIEWER = {David Conlon},

       DOI = {10.1090/gsm/142},

       URL = {http://dx.doi.org/10.1090/gsm/142},

}

@incollection {Green:2007,

  	AUTHOR = {Green, Ben},

    TITLE = {Montr\'eal notes on quadratic {F}ourier analysis},

 	BOOKTITLE = {Additive combinatorics},

    SERIES = {CRM Proc. Lecture Notes},

    VOLUME = {43},

    PAGES = {69--102},

 	PUBLISHER = {Amer. Math. Soc., Providence, RI},

    YEAR = {2007}}

@incollection {Tao:2007,

	AUTHOR = {Tao, Terence},

    TITLE = {The dichotomy between structure and randomness, arithmetic progressions, and the primes},

 	BOOKTITLE = {International {C}ongress of {M}athematicians. {V}ol. {I}},

    PAGES = {581--608},

   PUBLISHER = {Eur. Math. Soc., Z\"urich},

   YEAR = {2007}}

@article{Szemeredi:1990,

	AUTHOR = {Szemer{\'e}di, E.},

    TITLE = {Integer sets containing no arithmetic progressions},

    JOURNAL = {Acta Math. Hungar.},

    FJOURNAL = {Acta Mathematica Hungarica},

    VOLUME = {56},

    YEAR = {1990},

    NUMBER = {1-2},

    PAGES = {155--158}}

@article {Sanders:2011,

    AUTHOR = {Sanders, Tom},

     TITLE = {On {R}oth's theorem on progressions},

   JOURNAL = {Ann. of Math. (2)},

  FJOURNAL = {Annals of Mathematics. Second Series},

    VOLUME = {174},

      YEAR = {2011},

    NUMBER = {1},

     PAGES = {619--636}}    

@article {Ruzsa:1993,

	AUTHOR = {Ruzsa, Imre Z.},

    TITLE = {Solving a linear equation in a set of integers. {I}},

    JOURNAL = {Acta Arith.},

    FJOURNAL = {Acta Arithmetica},

    VOLUME = {65},

    YEAR = {1993},

    NUMBER = {3},

    PAGES = {259--282}}

@article{Schoen:2014,

  title={Roth's theorem in many variables},

  author={Schoen, Tomasz and Shkredov, Ilya D},

  journal={Israel Journal of Mathematics},

  volume={199},

  number={1},

  pages={287--308},

  year={2014},

  publisher={Springer}}

@article {OBryant:2011,

	AUTHOR = {O'Bryant, Kevin},

    TITLE = {Sets of integers that do not contain long arithmetic progressions},

   	JOURNAL = {Electron. J. Combin.},

  	FJOURNAL = {Electronic Journal of Combinatorics},

    VOLUME = {18},

    YEAR = {2011},

    NUMBER = {1},

    PAGES = {Paper 59, 15}}

@article{Ellenberg:2016,

  title={On large subsets of $\mathbb{F}_q^n$ with no three-term arithmetic progression},

  author={Ellenberg, Jordan S.\ and Gijswijt, Dion},

  journal={arXiv preprint arXiv:1605.09223},

  year={2016}}

@article{Sanders:2012,

  title={On the {B}ogolyubov--{R}uzsa lemma},

  author={Sanders, Tom},

  journal={Analysis \& PDE},

  volume={5},

  number={3},

  pages={627--655},

  year={2012},

  publisher={Mathematical Sciences Publishers}}

@article{Bloom:2012,

  title={Translation invariant equations and the method of {S}anders},

  author={Bloom, Thomas F},

  journal={Bulletin of the London Mathematical Society},

  pages={bds045},

  year={2012},

  publisher={Oxford University Press}}

@article{OBryant:2004,

  title={A complete annotated bibliography of work related to {S}idon sequences},

  author={O'Bryant, Kevin},

  journal={Electron. J. Combin},

  volume={11},

  pages={39},

  year={2004}

}

@incollection{Lidl:1983,

	Author = {Lidl, R. and Niederreiter, H.},

	Booktitle = {Finite Fields},

	Editor = {Rota, Gian-Carlo},

	Publisher = {Addison-Wesley, Reading, Massachusetts},

	Series = {Encyclopedia of Mathematics and its Applications},

	Title = {Finite Fields},

	Volume = {20},

	Year = {1983}}

@article{tao:2014,

	author = {Tao, Terence},

	title = {Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory},

	journal = {EMS Surv.\ Math.\ Sci.},

	volume = {1},

	year = {2014},

	pages = {1--46}}	

@article{CohenTal:2014,

	title={Two structural results for low degree polynomials and applications},

  	author={Cohen, Gil and Tal, Avishay},

  	journal={arXiv preprint arXiv:1404.0654},

  	year={2014}}

@incollection{Krivelevich:2006,

  title={Pseudo-random graphs},

  author={Krivelevich, Michael and Sudakov, Benny},

  booktitle={More sets, graphs and numbers},

  pages={199--262},

  year={2006},

  publisher={Springer}}

@article{Bollobas:2004,

  title={Hermitian matrices and graphs: singular values and discrepancy},

  author={Bollob{\'a}s, B{\'e}la and Nikiforov, Vladimir},

  journal={Discrete Mathematics},

  volume={285},

  number={1},

  pages={17--32},

  year={2004},

  publisher={Elsevier}}

@article{Chung:1989,

	author={Chung, Fan R. K. and Graham, Ronald L. and Wilson, Richard M.},

	title={Quasi-random graphs},

  	journal={Combinatorica},

	volume={9},

  	number={4},

  	pages={345--362},

  	year={1989},

  	publisher={Springer}}

@article{Kohayakawa:2016,

  title={Discrepancy and eigenvalues of {C}ayley graphs},

  author={Kohayakawa, Yoshiharu and R\"odl, Vojt\v{e}ch and Schacht, Mathias},

  journal={preprint},

  note = {Available at arXiv:1602.02291 [math.CO]},

  year={2016}}

@article{Conlon:2016,

	author={Conlon, David and Zhao, Yufei},

	title={Quasirandom {C}ayley graphs},

	journal={preprint},

	note={Available at arXiv:1603.03025 [math.CO]},

	year={2016}}

@article{Lubotzky:1988,

  	title={Ramanujan graphs},

  	author={Lubotzky, Alexander and Phillips, Ralph and Sarnak, Peter},

  	journal={Combinatorica},

  	volume={8},

  	number={3},

  	pages={261--277},

  	year={1988},

  	publisher={Springer}}

@article{Margulis:1973,

	author={Margulis, Grigorii Aleksandrovich},

	title={Explicit constructions of expanders},

	journal={Problemy Pereda\v{c}i Informacii},

	volume={9},

	number={4},

	pages={71--80},

	year={1973}}	

@article{Margulis:1988,

	author={Margulis, Grigorii Aleksandrovich},

  	title={Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators},

  	journal={Problems of Information Transmission},

  	volume={24},

  	number={1},

  	pages={39--46},

  	year={1988}}

@article{Chung:1990,

  title={Quasi-random hypergraphs},

  author={Chung, Fan R. K. and Graham, Ronald L.},

  journal={Random Structures \& Algorithms},

  volume={1},

  number={1},

  pages={105--124},

  year={1990},

  publisher={Wiley Online Library}}

@inproceedings{Lenz:2015,

	author={Lenz, John and Mubayi, Dhruv},

  	title={Eigenvalues and linear quasirandom hypergraphs},

  	booktitle={Forum of Mathematics, Sigma},

  	volume={3},

  	year={2015},

  	organization={Cambridge Univ Press}}

@article{Friedman:1995,

	Author = {Friedman, Joel and Wigderson, Avi},

	Date-Added = {2015-05-18 10:03:23 +0200},

	Date-Modified = {2015-05-18 10:03:23 +0200},

	Journal = {Combinatorica},

	Number = {1},

	Pages = {43--65},

	Publisher = {Springer},

	Title = {On the second eigenvalue of hypergraphs},

	Volume = {15},

	Year = {1995}}

@article{Cohen:2014,

	Author = {Cohen, Emma and Mubayi, Dhruv and Ralli, Peter and Tetali, Prasad},

	Date-Added = {2015-05-18 10:01:46 +0200},

	Date-Modified = {2015-05-18 10:01:46 +0200},

	Journal = {arXiv preprint arXiv:1407.2285},

	Title = {Inverse Expander Mixing for Hypergraphs},

	Year = {2014}}

@article{Alon:1988,

	Author = {Alon, Noga and Chung, Fan RK},

	Journal = {Annals of Discrete Mathematics},

	Pages = {15--19},

	Publisher = {Elsevier},

	Title = {Explicit construction of linear sized tolerant networks},

	Volume = {38},

	Year = {1988}}

@article{Alon:1985,

	Author = {Alon, Noga and Milman, Vitali D.},

	Coden = {JCBTB8},

	Date-Added = {2015-05-15 10:49:03 +0200},

	Date-Modified = {2015-05-15 10:49:03 +0200},

	Eprint = {jcombthb:10.1016/0095-8956(85)90092-9},

	Issn = {0095-8956},

	Journal = {Journal of Combinatorial Theory. Series B},

	Mrclass = {05C50},

	Mrnumber = {87b:05092},

	Number = {1},

	Owner = {jbriet},

	Pages = {73--88},

	Timestamp = {2011.01.25},

	Title = {$\lambda\sb 1,$ isoperimetric inequalities for graphs, and superconcentrators},

	Volume = {38},

	Year = {1985}}

@article{Tanner:1984,

	Author = {Michael R. Tanner},

	Date-Added = {2015-05-15 10:48:19 +0200},

	Date-Modified = {2015-05-15 10:48:29 +0200},

	Journal = {SIAM Journal on Algebraic Discrete Methods},

	Number = {3},

	Pages = {287--293},

	Title = {Explicit Concentrators from Generalized $N$-gons},

	Volume = {5},

	Year = {1984}}

@article{Hoory:2006,

	Author = {Shlomo Hoory and Nathan Linial and Avi Wigderson},

	Date-Added = {2015-05-15 10:47:49 +0200},

	Date-Modified = {2015-05-15 10:48:05 +0200},

	Journal = {Bull. Amer. Math. Soc.},

	Pages = {439--561},

	Publisher = {AMS},

	Title = {Expander Graphs and their Applications},

	Volume = {43},

	Year = {2006},

}

@inbook{Vershynin:2012,

	Author = {Vershynin, R.},

	Chapter = {5, Introduction to the non-asymptotic analysis of random matrices},

	Date-Added = {2015-05-11 16:37:49 +0200},

	Date-Modified = {2015-05-11 16:37:49 +0200},

	Note = {Available at {http://www-personal.umich.edu/~romanv/papers/non-asymptotic-rmt-plain.pdf}},

	Pages = {210--268},

	Publisher = {Cambridge University Press},

	Title = {Compressed sensing: theory and applications},

	Year = {2012}}

@article{Tomczak-Jaegermann:1974,

	Author = {N. Tomczak-Jaegermann},

	Date-Added = {2015-05-11 16:37:38 +0200},

	Date-Modified = {2015-05-11 16:37:38 +0200},

	Journal = {Studia Math.},

	Owner = {jbriet},

	Pages = {163-182},

	Timestamp = {2011.01.25},

	Title = {The moduli of smoothness and convexity and the {R}ademacher averages of trace classes ${S}_p$ ($1\leq p<\infty$)},

	Volume = {50},

	Year = {1974}}

@article{Naor:2012b,

	Author = {Naor, Assaf},

	Date-Added = {2015-05-11 16:37:29 +0200},

	Date-Modified = {2015-05-11 16:37:29 +0200},

	Journal = {Combinatorics, Probability and Computing},

	Number = {04},

	Pages = {623--634},

	Publisher = {Cambridge Univ Press},

	Title = {On the {Banach}-space-valued {Azuma} inequality and small-set isoperimetry of {Alon--Roichman} graphs},

	Volume = {21},

	Year = {2012}}

@book{Ledoux:1991,

	Author = {Michel Ledoux and Michel Talagrand},

	Date-Added = {2015-05-11 16:37:18 +0200},

	Date-Modified = {2015-05-11 16:37:18 +0200},

	Owner = {jbriet},

	Publisher = {Springer},

	Timestamp = {2011.01.25},

	Title = {Probability in Banach Spaces},

	Year = {1991}}

@article{Landau:2004,

	Author = {Zeph Landau and Alexander Russell},

	Date-Added = {2015-05-11 16:37:11 +0200},

	Date-Modified = {2015-05-11 16:37:11 +0200},

	Journal = {Electron. J. Combin.},

	Number = {1},

	Title = {Random {C}ayley graphs are expanders: a simplified proof of the {A}lon-{R}oichman theorem},

	Volume = {11},

	Year = {2004}}

@article{Lust-Piquard:1991,

	Author = {Lust-Piquard, Fran{\c{c}}oise and Pisier, Gilles},

	Date-Added = {2015-05-11 16:37:04 +0200},

	Date-Modified = {2015-05-11 16:37:04 +0200},

	Journal = {Arkiv f\"{o}r Matematik},

	Number = {1},

	Pages = {241--260},

	Publisher = {Springer},

	Title = {Non commutative {Khintchine} and {Paley} inequalities},

	Volume = {29},

	Year = {1991}}

@article{Johnson:2001,

	Author = {Johnson, W.B. and Lindenstrauss, J.},

	Date-Added = {2015-05-11 16:36:48 +0200},

	Date-Modified = {2015-05-11 16:36:48 +0200},

	Issn = {1874-5849},

	Journal = {Handbook of the geometry of Banach spaces},

	Pages = {1--84},

	Publisher = {Elsevier},

	Title = {{Basic concepts in the geometry of Banach spaces}},

	Volume = {1},

	Year = {2001}}

@article{Gamburd:2009,

	Author = {Gamburd, Alexander and Hoory, Shlomo and Shahshahani, Mehrdad and Shalev, Aner and Vir{\'a}g, Balint},

	Date-Added = {2015-05-11 16:36:40 +0200},

	Date-Modified = {2015-05-11 16:36:40 +0200},

	Journal = {Random Structures \& Algorithms},

	Number = {1},

	Pages = {100--117},

	Publisher = {Wiley Online Library},

	Title = {On the girth of random {C}ayley graphs},

	Volume = {35},

	Year = {2009}}

@article{Ellis:2014,

	Author = {Ellis, David and Linial, Nathan},

	Date-Added = {2015-05-11 16:36:31 +0200},

	Date-Modified = {2015-05-11 16:36:31 +0200},

	Journal = {Electron. J. Combin.},

	Number = {1},

	Title = {On regular hypergraphs of high girth},

	Volume = {21},

	Year = {2014}}

@article{Carlen:2006,

	Author = {Carlen, Eric and Lieb, Elliott H. and Loss, Michael},

	Date-Added = {2015-05-11 16:36:24 +0200},

	Date-Modified = {2015-05-11 16:36:24 +0200},

	Journal = {Methods Appl. Anal.},

	Number = {1},

	Pages = {1--17},

	Title = {An inequality of {H}adamard type for permanents},

	Volume = {13},

	Year = {2006},

}

@article{Bilu:2004,

	Author = {Yonatan Bilu and Shlomo Hoory},

	Date-Added = {2015-05-11 16:36:15 +0200},

	Date-Modified = {2015-05-11 16:36:15 +0200},

	Eprint = {elsevier:10.1016/j.ejc.2003.10.002},

	Journal = {European Journal of Combinatorics},

	Number = {3},

	Owner = {jbriet},

	Pages = {339--354},

	Timestamp = {2011.01.25},

	Title = {On codes from hypergraphs},

	Volume = {25},

	Year = {2004}}

@article{Bilu:2006,

	Author = {Bilu, Yonatan and Linial, Nathan},

	Date-Added = {2015-05-11 16:36:15 +0200},

	Date-Modified = {2015-05-11 16:36:15 +0200},

	Journal = {Combinatorica},

	Number = {5},

	Pages = {495--519},

	Title = {Lifts, discrepancy and nearly optimal spectral gap},

	Volume = {26},

	Year = {2006},

}

@article{Ahlswede:2002,

	Author = {Rudolf Ahlswede and Andreas Winter},

	Date-Added = {2015-05-11 16:36:04 +0200},

	Date-Modified = {2015-05-11 16:36:04 +0200},

	Eprint = {ieee:10.1109/18.985947},

	Journal = {IEEE Transactions on Information Theory},

	Number = {3},

	Owner = {jbriet},

	Pages = {569--579},

	Timestamp = {2011.01.25},

	Title = {Strong Converse for Identification via Quantum Channels},

	Volume = {48},

	Year = {2002}}

@article{Alon:1994a,

	Author = {Noga Alon and Yuval Roichman},

	Date-Added = {2015-05-11 16:35:55 +0200},

	Date-Modified = {2015-05-11 16:35:55 +0200},

	Journal = {Random Structures \& Algorithms},

	Owner = {jbriet},

	Timestamp = {2011.01.25},

	Title = {Random {C}ayley Graphs and Expanders},

	Url = {http://citeseer.ist.psu.edu/alon97random.html},

	Volume = {5},

	Year = {1994},

}

@article{Linial:2014,

	Author = {Linial, Nathan and Luria, Zur},

	Date-Added = {2015-05-21 08:56:27 +0200},

	Date-Modified = {2015-05-21 08:56:27 +0200},

	Journal = {Discrete Comput. Geom.},

	Number = {1},

	Pages = {161--170},

	Title = {On the vertices of the {$d$}-dimensional {B}irkhoff polytope},

	Volume = {51},

	Year = {2014},

}

@incollection {Kwapien:1976,

	AUTHOR = {Kwapie{\'n}, S.},

    TITLE = {A theorem on the {R}ademacher series with vector valued coefficients},

	BOOKTITLE = {Probability in {B}anach spaces ({P}roc. {F}irst {I}nternat. {C}onf., {O}berwolfach, 1975)},

    PAGES = {157--158. Lecture Notes in Math., Vol. 526},

 	PUBLISHER = {Springer, Berlin},

    YEAR = {1976}

}

@book {Chafai:2012,

	AUTHOR = {Chafa{\"{\i}}, Djalil and Gu{\'e}don, Olivier and Lecu{\'e}, Guillaume and Pajor, Alain},

    TITLE = {Interactions between compressed sensing random matrices and high dimensional geometry},

    SERIES = {Panoramas et Synth\`eses [Panoramas and Syntheses]},

    VOLUME = {37},

 	PUBLISHER = {Soci\'et\'e Math\'ematique de France, Paris},

    YEAR = {2012},

    PAGES = {181}

}

@article {Pisier:1973,

	AUTHOR = {Pisier, Gilles},

    TITLE = {Type des espaces norm\'es},

   	JOURNAL = {C. R. Acad. Sci. Paris S\'er. A-B},

    VOLUME = {276},

    YEAR = {1973},

    PAGES = {A1673--A1676}

}

@book {Talagrand:2014,

	AUTHOR = {Talagrand, Michel},

    TITLE = {Upper and lower bounds for stochastic processes},

    SERIES = {Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A

              Series of Modern Surveys in Mathematics [Results in

              Mathematics and Related Areas. 3rd Series. A Series of Modern

              Surveys in Mathematics]},

    VOLUME = {60},

    NOTE = {Modern methods and classical problems},

 	PUBLISHER = {Springer, Heidelberg},

    YEAR = {2014}

}

@book {Boucheron:2013,

	AUTHOR = {Boucheron, St{\'e}phane and Lugosi, G{\'a}bor and Massart, Pascal},

    TITLE = {Concentration inequalities},

    NOTE = {A nonasymptotic theory of independence, with a foreword by Michel Ledoux},

 	PUBLISHER = {Oxford University Press, Oxford},

    YEAR = {2013}

}

@article {Haagerup:1981,

  	AUTHOR = {Haagerup, Uffe},

    TITLE = {The best constants in the {K}hintchine inequality},

   	JOURNAL = {Studia Math.},

    VOLUME = {70},

    YEAR = {1981},

    NUMBER = {3},

    PAGES = {231--283 (1982)}

}

@article {Szarek:1976,

  	AUTHOR = {Szarek, S. J.},

    TITLE = {On the best constants in the {K}hinchin inequality},

    JOURNAL = {Studia Math.},

    VOLUME = {58},

    YEAR = {1976},

    NUMBER = {2},

    PAGES = {197--208}

}

@article{Briet:2012d,

	Journal = {Electronic Research Announcements in Mathematical Sciences (ERA-MS)},

	Pages = {120--130},

	Title = {Locally decodable codes and the failure of cotype for projective tensor products},

	Volume = {19},

	Year = {2012}}

@article{Briet:2015,

	title = {On Embeddings of $\ell_1^k$ from Locally Decodable Codes},	

	Ee = {http://eccc.hpi-web.de/eccc-reports/2015/TR07-086/index.html},

	Journal = {Electronic Colloquium on Computational Complexity (ECCC)},

	Number = {86},

	Year = {2015}}