@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}}

\documentclass[11pt]{article}

\usepackage{fullpage}

\usepackage{amsmath, amsfonts}

\usepackage{amsmath, amsthm, amssymb}

\usepackage{graphicx}

\usepackage[ruled,noline]{algorithm2e}

\usepackage{multirow}

\title{Blah Blah Blah}

\author{

       Shravas Rao

}

\date{\today}

\usepackage{amsmath,amssymb,amsthm,setspace,algorithmic}

\singlespacing

\usepackage[letterpaper,hmargin=1.0in,tmargin=1.0in,bmargin=1.0in]{geometry}

\usepackage{url}

\input{marginnotes}

\DeclareRobustCommand{\stirling}{\genfrac\{\}{0pt}{}}

\newtheorem{thm}{Theorem}

\newtheorem{cor}[thm]{Corollary}

\newtheorem{lem}[thm]{Lemma}

\newtheorem{prob}[thm]{Problem}

\newtheorem{claim}[thm]{Claim}

\newtheorem*{thm*}{Theorem}

\newtheorem*{cor*}{Corollary}

\newtheorem*{lem*}{Lemma}

\newtheorem*{claim*}{Claim}

\newtheorem{conj}[thm]{Conjecture}

\newtheorem*{conj*}{Conjecture}

\theoremstyle{remark}

\newtheorem*{note}{Note}

\newtheorem{define}[thm]{Definition}

\newtheorem*{define*}{Definition}

\newcommand{\weakdivider}{\noindent\dotfill}

\newcommand{\divider}{\hrule}

\newcommand\numberthis{\addtocounter{equation}{1}\tag{\theequation}}

\newcommand{\eps}{\varepsilon}

\DeclareMathOperator{\Tr}{Tr}

  \newcommand{\R}{\mathbb{R}} % reals

  \newcommand{\C}{\mathbb{C}} % complex numbers

  \newcommand{\N}{\mathbb{N}} % natural numbers

  \newcommand{\Z}{\mathbb{Z}} % integers

  \newcommand{\F}{\mathbb{F}} % field

  \newcommand{\K}{\mathbb K} % field

  \newcommand{\T}{\mathbb T} % circle

  \newcommand{\pmset}[1]{\{-1,1\}^{#1}} % hypercube in +-1 basis

  \newcommand{\bset}[1]{\{0,1\}^{#1}} % hypercube

  \newcommand{\sphere}[1]{S^{#1-1}} % real unit sphere of dimension #1

  \newcommand{\ball}[1]{B_{#1}} % real unit ball of dimension $1

  \newcommand{\Orth}[1]{O(\R^{#1})} % orthogonal group

  \DeclareMathOperator{\im}{im} % image

  \DeclareMathOperator{\vspan}{Span} % kernel

  \newcommand{\1}{\mathbf{1}}

  \DeclareMathOperator{\Cball}{\mathcal C}

  \DeclareMathOperator{\cay}{Cay} 

  \DeclareMathOperator{\sol}{Sol} 

\newenvironment{enumerate*}%

  {\vspace{-2ex} \begin{enumerate} %

     \setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%

  {\end{enumerate}}

\newenvironment{itemize*}%

  {\vspace{-2ex} \begin{itemize} %

     \setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%

  {\end{itemize}}

\newenvironment{description*}%

  {\vspace{-2ex} \begin{description} %

     \setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%

  {\end{description}}

\begin{document}

We attempt to prove that small discrepancy implies small spectral expansion for Cayley hypergraphs over certain types of abelian groups.  In the case of regular graphs, this is known to hold for Cayley graphs over any group by a result of Conlan and Zhao, but does not hold for general graphs~\cite{Conlon:2016}.

We start by giving definitions.  Because these are just my personal notes, I will let the definition of Cayley hypergraphs be the exact same as that in my paper with Jop, except we let $\mathbf{g} = (0, g, g^2, \ldots, g^{t-1})$ and $q = \mathbf{1}$ for now.  In particular, $K = \cay^{(t)}(\Gamma, q, S)$ is a $t$-uniform Cayley hypergraph with edges induced by the set $S \subseteq \Gamma$, and we let $A_K$ be the corresponding adjacency tensor.  Given a Cayley hypergraph $K$, we say that a sub-hypergraph of $K$, $H = \cay^{(t)}(\Gamma, q, S')$ for some $S' \subseteq S$ has spectral expansion $\lambda$ with respect to $K$ if \[\lambda \geq \|A_H-A_K\|_{\ell_t, \ldots, \ell_t}.\]  We say that $H$ has discrepancy $\epsilon$ with respect to $K$ if for all $T_1, \ldots, T_t \subseteq \Gamma$, \[|A_H(1_{T_1}, \ldots, 1_{T_t})-A_K(1_{T_1}, \ldots, 1_{T_t})| \leq \epsilon |\Gamma|.\]  We can lower bound discrepancy in terms of the $\ell_{\infty}, \ldots, \ell_{\infty}$-norm of $A_H-A_K$ as stated in the following Lemma (the upper bound is trivial).  The proof follows almost exactly that of the same fact for matrices in Lemma 2.1 in~\cite{Conlon:2016}.

\begin{lem}\label{lem:disctoinfty}

If $A$ is an $n \times \cdots \times n$ $t$-linear form, there exist $T_1, \ldots, T_t \subseteq [n]$ such that \[\|A\|_{\ell_{\infty}, \ldots, \ell_{\infty}} \leq \pi^t|A(1_{T_1}, \ldots, 1_{T_t})|\]

\end{lem}

\begin{proof}

Let $\mathbb{D}$ be the set of complex numbers with absolute value $1$.  Recall that for all $z \in \mathbb{C}$ and a uniformly random unit complex vector $w$ that

\[

z = \pi \mathbb{E}_{w \in \mathbb{D}} [1_R(z \overline{w}) |z| w],

\]

where $R = \{z \in \mathbb{C} : \mathcal{R}(z) \geq 0\}$ is the set of all numbers with non-negative real part, and $1_R$ is the corresponding indicator function.  For a vector $x \in \mathbb{C}^{n}$, let $x'$ be the random vector defined by $x'_i = 1_R(x_i \overline{w})|x_i|$ where $w$ is again a uniformly random unit complex vector $w$.  Then we have

\begin{align}

\|A\|_{\ell_{\infty}, \ldots, \ell_{\infty}} &= \sup_{x[1], \ldots, x[t] \in \mathbb{D}^n} \sum_{i_1, \ldots, i_t \in [n]^t} A_{i_1, \ldots, i_t} x[1]_{i_1}\ldots x[t]_{i_t} \nonumber \\

&= \sup_{x[1], \ldots, x[t] \in \mathbb{D}^n} \left| \pi^t \mathbb{E}_{w_1, \ldots, w_t \in \mathbb{D}} \sum_{i_1, \ldots, i_t \in [n]^t} A_{i_1, \ldots, i_t} x'[1]_{i_1}\ldots x'[t]_{i_t} w_1 \ldots w_t \right| \nonumber \\

&\leq \pi^t \mathbb{E}_{w_1, \ldots, w_t \in \mathbb{D}} \sup_{x[1], \ldots, x[t] \in \mathbb{D}^n} \left| \sum_{i_1, \ldots, i_t \in [n]^t} A_{i_1, \ldots, i_t} x'[1]_{i_1}\ldots x'[t]_{i_t} \right|. \label{eq:reduce}

\end{align}

By convexity,~\eqref{eq:reduce} is maximized when $x'[j] \in \{0, 1\}^n$ for all $j$, or in other words, is an indicator vector.  Letting $T_j = \{i : x'[j]_{i} = 1\}$ proves the lemma.

\end{proof}

By a straightforward generalization of the Expander Mixing Lemma, it follows that if a Cayley hypergraph has spectral expansion $\lambda$, then it also has discrepancy $\lambda$.  We attempt to prove the converse, stated below.

\begin{lem}\label{lem:disctospec}

Let $\Gamma = F_p^n$. For $t \leq p$ and every $\lambda$ there exists an $\epsilon$ such that if a Cayley $t$-uniform hypergraph $H = \cay^{(t)}(\Gamma, q, S')$ has discrepancy $\epsilon$ with respect to $K = \cay^{(t)}(\Gamma, q, S)$, then it also has spectral expansion $\lambda$ with respect to $K = \cay^{(t)}(\Gamma, q, S)$.

\end{lem}

To prove this we use the generalized von Neumann inequality and the inverse Gowers theorem, which we state below.  We first state the definition of the Gowers norm.

\begin{define}

Given a function $f: \Gamma \rightarrow \mathbb{C}$, its Gowers uniformity norm is defined by

\[

\|f\|_{U^d} = [\mathbb{E}_{h_1, \ldots, h_d, x \in G} \Delta_{h_1}\cdots\Delta_{h_d} f(x)]^{1/2^d}

\]

where $\Delta_{h}$ is the multiplicative derivative

\[

\Delta_h f(x) = f(x+h)\overline{f(x)}.

\]

\end{define}

The following lemma relates the Gowers norm to \snote{not sure how to describe this}.  We state the form given in~\cite{Bhatt:2016}

\begin{lem}[Generalized von Neumann inequality]\label{lem:genvn}

Let $(\mathcal L_1, \ldots, \mathcal L_{t+1})$ be a collection of affine-linear forms $\mathcal L_i: (\mathbb{F}_p^n)^m \rightarrow \mathbb{F}_p^n)^m$ for some prime $p$ such that no form is a multiple of another.  Then for $f_1, \ldots, f_{t+1}: \mathbb{F}_p^n)^m \rightarrow \mathbb{C}$,

\[

|\mathbb{E}_{z_1, \ldots, z_m \in \mathbb{F}_p^n)^m} \prod_{i=1}^{t+1} f_i(\mathcal L_i(z_1, \ldots, z_m))| \leq \min_{1 \leq i \leq t+1} \|f_i\|_{U^t}.

\]

\end{lem}

For certain groups $\Gamma$, a lower bound on the Gowers norm of a function $f$ implies certain structural properties of the function.  To do this, we define the notion of a non-classical polynomial.

\begin{define}

A non-classical polynomial of degree $< d$ is a function $f: \mathbb{F}^n \rightarrow G$ where $G$ is an additive group, if for all $h_1, \ldots, h_{d+1}, x \in \mathbb{F}^n$, the following holds.

\[

D_{h_1}\cdots D_{h_{d+1}} f(x) = 0

\]

where $D_h f(x) = f(x+h)-f(x)$.

\end{define}

We denote by $\mathbb{T}$ the circle group $\mathbb{R}/\mathbb{Z}$.  

%For any $\mathbb{F}_p$ there exists a natural homomorphism to $\mathbb{T}$ given by $(j) = j/p$. 

The following lemma gives an equivalent formulation of non-classical polynomials when the additive group is $\mathbb{T}$ and $d$ is less than $p$.

\begin{lem}[Lemma 1.7 in~\cite{Tao:2012a}]\label{lem:classtonon}

If $d < p$, then the non-classical polynomials of degree $d$ of the form $P: \mathbb{F}_p^n \rightarrow \mathbb{T}$ coincide with the classical polynomials of degree $d$.  In particular, $P$ can be expressed as

\[

P(x_1, \ldots, x_n) = \sum_{i=0}^d T_i(\mathbf{x}, \ldots, \mathbf{x})

\]

where $T_i$ is an $i$-linear form.

\end{lem}

Let $e: \mathbb{T} \rightarrow \mathbb{C}$ be the standard character $e(x) = e^{2\pi i x}$.  Then the inverse Gowers theorem states the following.

\begin{thm}[Inverse Gowers theorem~\cite{Tao:2012a}]

Let $\delta > 0$ and $s \geq 0$.  Then there exists an $\epsilon = \epsilon_{\delta, s}$ such that for every $\mathbb{F}_p^n$ and function $f : \mathbb{F}_p^n \rightarrow \mathbb{C}$ bounded in absolute value by $1$ such that $\|f\|_{U^{s+1}} \geq \delta$, there exists a non-classical polynomial $P: \mathbb{F}_p^n \rightarrow \mathbb{T}$ of degree $\leq s$  such that

\[

|\mathbb{E}_{x \in \mathbb{F}_p^n} f(x)e(-P(x))| \geq \epsilon.

\]

\end{thm}

Given the structure of non-classical polynomials that take on values in $\mathbb{T}$ described above, we have the following lemma.

\begin{lem}\label{lem:decomp}

Let $P: \mathbb{F}_p^n \rightarrow \mathbb{T}$ be a non-classical polynomial of degree $d < p$.  Then there exist non-classical polynomials $P_0, \ldots, P_{d}$ such that

\[

\sum_{j=0}^d P_i(x+jy) = P(y)

\]

for all vectors $x, y \in \mathbb{F}_p^n$.

\end{lem}

\snote{This is the lemma to change if we want to make our statement more general, I think}

\begin{proof}

Decompose $P$ into a sum of linear forms as in Lemma~\ref{lem:classtonon}.  For each $T_i$, we show that there exist $\alpha_0, \ldots, \alpha_{d}$ such that

\begin{equation}

\sum_{j=0}^d \alpha_j T_i(x+jy, \ldots, x+jy) = T_i(y, \ldots, y).\label{eq:need}

\end{equation}

This is enough to construct the $P_i$ desired.

Because $T_i$ is an $i$-linear form, we can rewrite the left-hand side of~\eqref{eq:need} as

\[

\sum_{j=0}^d \sum_{s \in \{0, 1\}^i} \alpha_j T_i((1-s_1)x+js_1y, \ldots, (1-s_i)x+js_iy) = 

\sum_{j=0}^d \sum_{s \in \{0, 1\}^i} \alpha_j j^{|s|}T_i((1-s_1)x+s_1y, \ldots, (1-s_i)x+s_iy)

\]

where $|s|$ denotes the Hamming weight of $s$.  Then~\eqref{eq:need} holds if for all $0 \leq k < i$,

\[

\sum_{j=0}^d \alpha_j j^{k} = 0

\]

and

\[

\sum_{j=0}^d \alpha_j j^{i} = 1.

\]

This is a system of linear equations whose coefficients come from the first $i+1$ rows of a $(d+1) \times (d+1)$ Vandermonde matrix.  Because $d < p$, the determinant of such a matrix is non-zero and thus the matrix is invertible and $\alpha_j$ exist as desired.

\end{proof}

\begin{proof}[Proof of Lemma~\ref{lem:disctospec}]

We prove the contrapositive.  Assume that $\cay^{(t)}(\Gamma, q, S')$ does not have spectral expansion $\lambda$, that is that there exist vectors $x_1, \ldots, x_t$ such that $\|x_i\|_{\ell_p} = 1$ for all $i$, but $(A_H-A_K)(x_1, \ldots, x_t) \geq \lambda$.  Let $1_{H, K} = \left(\frac{1}{|S'|}-\frac{1}{|S|}\right)(1_{S'}-1_{S})$.  Then

 \begin{equation}

(A_H-A_K)(x_1, \ldots, x_t) = \frac{1}{t!} \sum_{\sigma \in S_t} \mathbb{E}_{u, g}[x_1(ug^{\sigma(1)-1})x_2(ug^{\sigma(2)-1})\cdots x_t(ug^{\sigma(t)-1})1_{H, K}(g)]. \label{eq:unravel}

\end{equation}

  By the Lemma~\ref{lem:genvn},~\eqref{eq:unravel} is bounded above by $\|1_{H, K}\|_{U^t}$.  By the inverse Gowers theorem, there exists a polynomial $P$ of degree $t-1$ such that $\mathbb{E}_{h}[e(P(g)) 1_{H, K}] \geq \epsilon$ for some $\epsilon$.  By Lemma~\ref{lem:decomp}, there exist $P_0, \ldots, P_{t-1}$ such that \[e(P_0(x))e(P_1(x+y))\cdots e(P_{t-1}(x+(t-1)y)) = e(P(y)),\] and therefore \[\mathbb{E}_{u, g}[e(P_0(u))e(P_1(ug))\cdots e(P_{t-1}(ug^{t-1})) 1_{H, K}] = \mathbb{E}_{h}[e(P(g)) 1_{H, K}] \geq \epsilon,\]

and

\[

(A_H-A_K)(e(P_0), \ldots, e(P_{t-1})) \geq \frac{\epsilon}{t!}.

\]

Because the coordinates of $e(P_i)$ are bounded above in absolute value by $1$ for all $i$, by Lemma~\ref{lem:disctoinfty}, this implies that $H$ has discrepancy at least $\epsilon/(t!\pi^t)$ with respect to $K$.

\end{proof}

\bibliographystyle{alphaabbrv}

\bibliography{disctospec.bib}

\end{document}