@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,
	Author = {Bri\"{e}t, Jop and Naor, Assaf and Regev, Oded},
	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,
	author={Bri\"{et}, Jop},
	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}}