diff --git a/disctospec.bib b/disctospec.bib new file mode 100644 index 0000000000000000000000000000000000000000..e06a6e484aea5f60925f449a7d21d16beab85701 --- /dev/null +++ b/disctospec.bib @@ -0,0 +1,619 @@ +@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}}