#LyX 2.1 created this file. For more info see http://www.lyx.org/ \lyxformat 474 \begin_document \begin_header \textclass article \begin_preamble %lyx2wpost preable August 3 2017. %This is an evolving preamble which works in tandem with myConfig5.cfg %and the lyx2wpost script \usepackage[english]{babel} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands. \newtheorem{theorem}{Theorem}[section] \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{claim}[theorem]{Claim} \newtheorem{remark}[theorem]{Remark} \newtheorem{definition}[theorem]{Definition} \newtheorem{construction}[theorem]{Construction} %Theorem 1 instead of Theorem 0.1 \renewcommand{\thetheorem}{% \arabic{theorem}} \renewenvironment{theorem} {\par \refstepcounter{theorem} \noindent \textbf{Theorem \thetheorem.}}{} \ifcsname thm\endcsname \renewenvironment{thm}% {\par \refstepcounter{theorem} \noindent \textbf{Theorem \thetheorem.}}{}% \fi \renewenvironment{definition} {\par \refstepcounter{theorem} \noindent \textbf{Definition \thetheorem.}}{} \renewenvironment{lemma} {\par \refstepcounter{theorem} \noindent \textbf{Lemma \thetheorem.}}{} %\renewenvironment{proof}{\par \noindent \textbf{Proof:}}{\hfill $\square$ \newline \newline} %QED \par\vspace{0.5cm}} \renewcommand{\qedsymbol}{$\square$} \renewcommand{\paragraph}[1]{\textbf{#1}. } \usepackage{xcolor} \end_preamble \use_default_options false \begin_modules theorems-ams \end_modules \maintain_unincluded_children false \language english \language_package none \inputencoding auto \fontencoding default \font_roman default \font_sans default \font_typewriter default \font_math auto \font_default_family default \use_non_tex_fonts false \font_sc false \font_osf false \font_sf_scale 100 \font_tt_scale 100 \graphics default \default_output_format default \output_sync 0 \bibtex_command default \index_command default \paperfontsize 12 \spacing single \use_hyperref false \papersize default \use_geometry false \use_package amsmath 2 \use_package amssymb 2 \use_package cancel 0 \use_package esint 1 \use_package mathdots 0 \use_package mathtools 0 \use_package mhchem 0 \use_package stackrel 0 \use_package stmaryrd 0 \use_package undertilde 0 \cite_engine basic \cite_engine_type default \biblio_style plain \use_bibtopic false \use_indices false \paperorientation portrait \suppress_date false \justification true \use_refstyle 0 \index Index \shortcut idx \color #008000 \end_index \secnumdepth 3 \tocdepth 3 \paragraph_separation indent \paragraph_indentation default \quotes_language english \papercolumns 1 \papersides 1 \paperpagestyle default \tracking_changes false \output_changes false \html_math_output 0 \html_css_as_file 0 \html_be_strict false \end_header \begin_body \begin_layout Standard \begin_inset FormulaMacro \newcommand{\E}{\mathrm{\mathbb{E}}} {\mathbb{E}} \end_inset \end_layout \begin_layout Standard \begin_inset FormulaMacro \newcommand{\e}{\mathrm{\mathbb{\epsilon}}} {\epsilon} \end_inset \end_layout \begin_layout Section* Special topics in complexity theory \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash vspace{1cm} \end_layout \end_inset \end_layout \begin_layout Standard \series bold \begin_inset CommandInset href LatexCommand href name "For a single file with all the lectures by the instructor click here" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/all.pdf" \end_inset . For more, check below. \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash vspace{1cm} \end_layout \end_inset \end_layout \begin_layout Paragraph \color magenta Instructor: \color inherit \begin_inset CommandInset href LatexCommand href name "Emanuele Viola" target "http://www.ccs.neu.edu/home/viola/" \end_inset \end_layout \begin_layout Paragraph Logistics \end_layout \begin_layout Standard Mondays 9:30 – 11:00am in 164 \begin_inset CommandInset href LatexCommand href name "West Village H" target "https://www.google.com/maps?q=west+village+H+neu&oe=utf-8&um=1&ie=UTF-8&sa=X&ved=0ahUKEwjd3Jr7j57WAhWDLSYKHZHVD00Q_AUICygC" \end_inset \end_layout \begin_layout Standard Tuesdays 1:35 pm - 3:15 pm \begin_inset CommandInset href LatexCommand href name "Ryder Hall " target "https://www.google.com/maps/place/Northeastern+University+-+Ryder+Hall/@42.3484052,-71.0910594,14z/data=!4m5!3m4!1s0x0:0x2c41b534c8efab93!8m2!3d42.3365736!4d-71.0906088" \end_inset 273. Office hours after class and by appointment. \end_layout \begin_layout Subsection* Tentative syllabus \end_layout \begin_layout Standard This class will present recent (amazing) progress in complexity theory and related areas. A highly tentative list of topics follows: \end_layout \begin_layout Standard (1) Pseudorandom generators. Bounded independence, small-bias, sandwiching polynomials. Bounded independence fools And, bounded independence fools AC0 (Braverman's result), the Gopalan-Kane-Meka inequality, the Gopalan-Meka-Reingold-Trevisan-V adhan generator. Vadhan's \begin_inset CommandInset href LatexCommand href name "survey" target "http://people.seas.harvard.edu/~salil/pseudorandomness/" \end_inset , \begin_inset CommandInset href LatexCommand href name "Amnon Ta-Shma's class" target "http://www.cs.tau.ac.il/~amnon/Classes/2016-PRG/class.htm" \end_inset \end_layout \begin_layout Standard (2) Approximate degree. Bounded indistinguishability. Bounded indistinguishability of Or, And-Or, and Surjectivity (the Bun-Thaler proof). \end_layout \begin_layout Standard (3) Circuit complexity. Williams' lower bounds from satisfiability. Succinct and explicit NP-completeness. ACC0-SAT algorithms. \begin_inset CommandInset href LatexCommand href name "Exposition " target "www.ccs.neu.edu/home/viola/classes/papers/accnexp.pdf" \end_inset in web appendix of Arora and Barak's book. Lower bounds from derandomization. \end_layout \begin_layout Standard (4) Quasi-random groups. \begin_inset CommandInset href LatexCommand href name "Austin's corner theorem in SL(2,q)" target "https://arxiv.org/abs/1503.08746" \end_inset . Regularity lemmas: \begin_inset CommandInset href LatexCommand href name "TTV" target "http://eccc.hpi-web.de/report/2008/103" \end_inset , \begin_inset CommandInset href LatexCommand href name "Skorski" target "https://eprint.iacr.org/2016/965.pdf" \end_inset \end_layout \begin_layout Standard (5) Communication complexity and quasi-random groups. Determinism vs. randomization in number-on-forehead communication complexity. Number-in-hand lower bounds for quasi-random groups. \begin_inset CommandInset href LatexCommand href name "Various notes." target "https://www.google.com/search?q=lecture+notes+communication+complexity&ie=utf-8&oe=utf-8" \end_inset \end_layout \begin_layout Standard (5) Data structures. Overview: static, dynamic, bit-probe, cell-probe. Siegel's lower bound for hashing. The Larsen-Weinstein-Yu superlogarithmic lower bound. \begin_inset CommandInset href LatexCommand href name "Demaine's advanced data structures class" target "http://courses.csail.mit.edu/6.851/fall17/" \end_inset \end_layout \begin_layout Standard (6) Arithmetic circuits. Overview. The chasm at depth 3. (The Gupta-Kamath-Kayal-Saptharishi result.) Shpilka and Yehudayoff's survey \begin_inset CommandInset href LatexCommand href name "Survey" target "www.cs.technion.ac.il/~shpilka/publications/SY10.pdf" \end_inset . \begin_inset CommandInset href LatexCommand href name "Kumar's concurrent class on arithmetic circuits." target "https://mrinalkr.bitbucket.io/arithmeticcktsF17.html" \end_inset \end_layout \begin_layout Standard (7) Fine-grained complexity reductions (SETH, 3SUM). SETH implies orthogonal vectors is hard. Faster orthogonal vectors via the polynomial method. \end_layout \begin_layout Subsection* Deliverables \end_layout \begin_layout Standard Each student will scribe #lectures/#students, and present a lecture. Grade is based on scribe, presentation, and class participation. \end_layout \begin_layout Standard Scribes: due 48 hours from the time of the lecture. Feel free to send me a draft and ask for suggestions before the cutoff. Scribe templates: see the .tex files below. I also have a template for Lyx if you use it. Optionally, the lectures will be posted on my blog. Using this template minimizes the risk that my wordpress compiler won't work. \end_layout \begin_layout Standard Presentations: should convey both a high-level overview of the proof of the result, as well as a self-contained exposition of at least one step. Talk to me for suggestions. Discuss with me your presentation plan at least 1 week before your presentation. \end_layout \begin_layout Standard Presentation papers: \end_layout \begin_layout Standard \series bold Note: Always look if there is an updated version. Check the authors' webpages as well as standard repositories (arxiv, ECCC, iacr, etc.) \end_layout \begin_layout Standard \series bold Pseudorandomness: \end_layout \begin_layout Standard \begin_inset CommandInset href LatexCommand href name "A relaxaxation of bounded independence which does not fool AC0" target "https://arxiv.org/abs/1110.6126" \end_inset \begin_inset ERT status open \begin_layout Plain Layout %Does this show that small-bias does not fool AC0? \end_layout \end_inset \end_layout \begin_layout Standard \begin_inset CommandInset href LatexCommand href name "Amnon Ta-Shma. Explicit, almost optimal, epsilon-balanced codes." target "http://www.cs.tau.ac.il/~amnon/Papers/T.STOC17.pdf" \end_inset \end_layout \begin_layout Standard (Perhaps \begin_inset CommandInset href LatexCommand href name "Avraham Ben-Aroya, Dean Doron and Amnon Ta-Shma. An efficient reduction from non-malleable extractors to two-source extractors, and explicit two-source extractors with near-logarithmic min-entropy." target "http://www.cs.tau.ac.il/~amnon/Papers/BDT.STOC17.pdf" \end_inset ) \end_layout \begin_layout Standard Unbalanced expander graphs from Parvaresh–Vardy codes: \begin_inset CommandInset href LatexCommand href name "survey" target "http://people.seas.harvard.edu/~salil/pseudorandomness/" \end_inset \end_layout \begin_layout Standard \begin_inset CommandInset href LatexCommand href name "Prahladh Harsha, Srikanth Srinivasan: On Polynomial Approximations to AC0" target "https://eccc.weizmann.ac.il/report/2016/068/" \end_inset \end_layout \begin_layout Standard \begin_inset CommandInset href LatexCommand href name "Improved parameters for bounded independence fools AC0" target "http://eccc.weizmann.ac.il/report/2014/174/" \end_inset \end_layout \begin_layout Standard \series bold SAT algorithms for depth-2 threshold circuits: \end_layout \begin_layout Standard \begin_inset CommandInset href LatexCommand href name "Here " target "https://arxiv.org/abs/1608.04355" \end_inset and \begin_inset CommandInset href LatexCommand href name "here" target "https://eccc.weizmann.ac.il/report/2016/100/download/" \end_inset . \end_layout \begin_layout Standard \series bold Approximate degree: \end_layout \begin_layout Standard \begin_inset CommandInset href LatexCommand href name "Making polynomials robust to noise" target "web.cs.ucla.edu/~sherstov/pdf/robust.pdf" \end_inset . \end_layout \begin_layout Standard More Bun-Thaler we did not see (ask me about it). \end_layout \begin_layout Standard \series bold Communication complexity: \end_layout \begin_layout Standard \begin_inset CommandInset href LatexCommand href name "Separating Deterministic from Randomized Multiparty Communication Complexity" target "https://www.cs.toronto.edu/~toni/Papers/random-multicc.pdf" \end_inset , \begin_inset CommandInset href LatexCommand href name "Query-to-communication lifting for BPP" target "www.cs.memphis.edu/~twwtson1/papers/bpp.pdf" \end_inset (see their Table 1 for other interesting papers as well). \end_layout \begin_layout Standard \begin_inset CommandInset href LatexCommand href name "Separation of information and communication for boolean functions" target "https://eccc.weizmann.ac.il/report/2014/113/download/" \end_inset \end_layout \begin_layout Standard \series bold Quasirandom groups: \end_layout \begin_layout Standard \begin_inset CommandInset href LatexCommand href name "Higher-dimensional corners" target "https://arxiv.org/pdf/1507.00844" \end_inset \end_layout \begin_layout Standard \series bold Data structures: \end_layout \begin_layout Standard Parts of Larsen-Weinstein-Yu superlogarithmic we left out. \end_layout \begin_layout Standard Any of the many lower bounds we didn't see. \end_layout \begin_layout Standard \series bold Arithmetic circuit complexity: \end_layout \begin_layout Standard Parts of the reduction we did not see. \end_layout \begin_layout Standard \begin_inset CommandInset href LatexCommand href name "Survey" target "www.cs.technion.ac.il/~shpilka/publications/SY10.pdf" \end_inset \end_layout \begin_layout Standard \begin_inset CommandInset href LatexCommand href name "Tavenas" target "https://arxiv.org/abs/1304.5777" \end_inset \end_layout \begin_layout Standard \series bold Fine-grained reductions: \end_layout \begin_layout Standard \begin_inset CommandInset href LatexCommand href name "Dynamic problems" target "https://arxiv.org/abs/1402.0054" \end_inset , \begin_inset CommandInset href LatexCommand href name "LCS" target "https://arxiv.org/abs/1501.07053" \end_inset , \begin_inset CommandInset href LatexCommand href name "edit distance" target "https://arxiv.org/abs/1412.0348" \end_inset . \end_layout \begin_layout Standard There are many other reductions in this area. \end_layout \begin_layout Standard \series bold Catalytic computation: \end_layout \begin_layout Standard \begin_inset CommandInset href LatexCommand href name "Survey" target "http://iuuk.mff.cuni.cz/~koucky/papers/cats.pdf" \end_inset , \begin_inset CommandInset href LatexCommand href name "Buhrman, Cleve, Koucký, Loff and Speelman" target "http://iuuk.mff.cuni.cz/~koucky/papers/catalytic.pdf" \end_inset \end_layout \begin_layout Standard \series bold More: \end_layout \begin_layout Standard \begin_inset CommandInset href LatexCommand href name "Fast Learning Requires Good Memory" target "https://arxiv.org/abs/1602.05161" \end_inset , see also \begin_inset CommandInset href LatexCommand href name "this" target "https://arxiv.org/abs/1708.02639" \end_inset \end_layout \begin_layout Standard the breakthrough on the cap-set problem \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout %Sadly, I can't get relative href in .lyx -- it adds an %"http" during the conversion which screws things up \end_layout \end_inset \end_layout \begin_layout Subsection* Classes \end_layout \begin_layout Enumerate 2017-09-12 Tue. Basics of PRGs. Bounded independence. \begin_inset ERT status open \begin_layout Plain Layout \backslash newline \end_layout \end_inset \begin_inset CommandInset href LatexCommand href name "Lecture 1.pdf" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/L1.pdf" \end_inset , \begin_inset CommandInset href LatexCommand href name "Lecture 1.tex" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/L1.tex" \end_inset , \begin_inset CommandInset href LatexCommand href name "Lecture 1 blog post" target "https://emanueleviola.wordpress.com/2017/09/15/special-topics-in-complexity-theory-lecture-1/" \end_inset \end_layout \begin_layout Enumerate 2017-09-18/19. Bounded independence fools And, fools AC0. \begin_inset ERT status open \begin_layout Plain Layout \backslash newline \end_layout \end_inset \begin_inset CommandInset href LatexCommand href name "Lectures 2-3.pdf" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/L2-3.pdf" \end_inset , \begin_inset CommandInset href LatexCommand href name "Lectures 2-3.tex" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/L2-3.tex" \end_inset , \begin_inset CommandInset href LatexCommand href name "Lectures 2-3 blog post" target "https://emanueleviola.wordpress.com/2017/09/22/special-topics-in-complexity-theory-lectures-2-3/" \end_inset \end_layout \begin_layout Enumerate 2017-09-25/26. Small-bias. Almost bounded independence. Fourier analysis. Vazirani xor lemma. The GMRTV generator. \begin_inset ERT status open \begin_layout Plain Layout \backslash newline \end_layout \end_inset \begin_inset CommandInset href LatexCommand href name "Lectures 4-5.pdf" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/L4-5.pdf" \end_inset , \begin_inset CommandInset href LatexCommand href name "Lectures 4-5.tex" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/L4-5.tex" \end_inset , \begin_inset CommandInset href LatexCommand href name "Lectures 4-5 blog post" target "https://emanueleviola.wordpress.com/2017/09/29/special-topics-in-complexity-theory-lectures-4-5/" \end_inset \end_layout \begin_layout Enumerate 2017-10-02/03 \begin_inset CommandInset href LatexCommand href name "Additive combinatorics workshop" target "http://cmsa.fas.harvard.edu/additive-combinatorics/" \end_inset . NO CLASS \end_layout \begin_layout Enumerate 2017-10-09/10 Monday holiday: no class. Bounded indistinguishability. Approximate degree. Duality. \end_layout \begin_layout Enumerate \begin_inset CommandInset href LatexCommand href name "W-R Lectures by Gowers" target "http://www.math.harvard.edu/conferences/ahlfors17/" \end_inset \end_layout \begin_layout Enumerate 2017-10-16/17 Monday: Approximate degree of Or. Approximate degree of And-Or. Tuesday: 10-minute pre-presentations by students. \begin_inset ERT status open \begin_layout Plain Layout \backslash newline \end_layout \end_inset \begin_inset CommandInset href LatexCommand href name "Lectures 6-7.pdf" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/L6-7.pdf" \end_inset , \begin_inset CommandInset href LatexCommand href name "Lectures 6-7.tex" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/L6-7.tex" \end_inset , \begin_inset CommandInset href LatexCommand href name "Lectures 6-7 blog post" target "https://emanueleviola.wordpress.com/2017/10/17/special-topics-in-complexity-theory-lectures-6-7/" \end_inset \end_layout \begin_layout Enumerate 2017-10-23/24 Finish approximate degree of And-Or. Approximate degree of SURJ. Quasirandom groups. \begin_inset ERT status open \begin_layout Plain Layout \backslash newline \end_layout \end_inset \begin_inset CommandInset href LatexCommand href name "Lectures 8-9.pdf" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/L8-9.pdf" \end_inset , \begin_inset CommandInset href LatexCommand href name "Lectures 8-9.tex" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/L8-9.tex" \end_inset , \begin_inset CommandInset href LatexCommand href name "Lectures 8-9 blog post" target "https://emanueleviola.wordpress.com/2017/10/26/special-topics-in-complexity-theory-lectures-8-9/" \end_inset \end_layout \begin_layout Enumerate 2017-10-30/31 Guest lecture by Justin Thaler. Presentation by Giorgos. \begin_inset ERT status open \begin_layout Plain Layout \backslash newline \end_layout \end_inset \begin_inset CommandInset href LatexCommand href name "Lecture 10.pdf" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/L10.pdf" \end_inset , \begin_inset CommandInset href LatexCommand href name "Lecture 10.tex" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/L10.tex" \end_inset , \begin_inset CommandInset href LatexCommand href name "Lecture 10 blog post" target "https://emanueleviola.wordpress.com/2017/11/25/special-topics-in-complexity-theory-lecture-10/" \end_inset \end_layout \begin_layout Enumerate 2017-11-06/07 Quasirandom groups. Number-in-hand communication complexity of quasirandom groups. 2-party interleaved communcation. \begin_inset ERT status open \begin_layout Plain Layout \backslash newline \end_layout \end_inset \begin_inset CommandInset href LatexCommand href name "Lectures 12-13.pdf" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/L12-13.pdf" \end_inset , \begin_inset CommandInset href LatexCommand href name "Lectures 12-13.tex" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/L12-13.tex" \end_inset , \begin_inset CommandInset href LatexCommand href name "Lectures 12-13 blog post" target "https://emanueleviola.wordpress.com/2017/11/17/special-topics-in-complexity-theory-lectures-12-13/" \end_inset . \end_layout \begin_layout Enumerate 2017-11-13/14 \begin_inset CommandInset href LatexCommand href name "Workshop" target "http://cmsa.fas.harvard.edu/algebraic-methods/" \end_inset . NO CLASS. To make up we'll meet Monday 9:30 - 12:30 and Tue 1:35 - 3:45 until the end. \end_layout \begin_layout Enumerate 2017-11-20/21 Monday: Presentation by Chin and Xuangui. Tuesday: Number-on-forehead communication complexity. Determinism vs. randomization. Reduction to corners theorem. \begin_inset ERT status open \begin_layout Plain Layout \backslash newline \end_layout \end_inset \begin_inset CommandInset href LatexCommand href name "Lecture 15.pdf" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/L15.pdf" \end_inset , \begin_inset CommandInset href LatexCommand href name "Lecture 15.tex" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/L15.tex" \end_inset , \begin_inset CommandInset href LatexCommand href name "Lecture 15 blog post" target "https://emanueleviola.wordpress.com/2017/12/01/special-topics-in-complexity-theory-lecture-15/" \end_inset . \end_layout \begin_layout Enumerate 2017-11-27/28 Monday: Presentation by Biswaroop. Monday.2: Weak regularity lemma. Tuesday: Corners theorem. \begin_inset ERT status open \begin_layout Plain Layout \backslash newline \end_layout \end_inset \begin_inset CommandInset href LatexCommand href name "Lectures 16-17.pdf" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/L16-17.pdf" \end_inset , \begin_inset CommandInset href LatexCommand href name "Lectures 16-17.tex" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/L16-17.tex" \end_inset , \begin_inset CommandInset href LatexCommand href name "Lectures 16-17 blog post" target "https://emanueleviola.wordpress.com/2017/12/06/special-topics-in-complexity-theory-lectures-16-17/" \end_inset . \end_layout \begin_layout Enumerate 2017-12-04/05 Monday: Presentation by Willy. Tuesday: Static data structure lower bounds. \begin_inset ERT status open \begin_layout Plain Layout \backslash newline \end_layout \end_inset \begin_inset CommandInset href LatexCommand href name "Lecture 18.pdf" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/L18.pdf" \end_inset , \begin_inset CommandInset href LatexCommand href name "Lecture 18.tex" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/L18.tex" \end_inset , \begin_inset CommandInset href LatexCommand href name "Lecture 18 blog post" target "https://emanueleviola.wordpress.com/2017/12/12/special-topics-in-complexity-theory-lecture-18/" \end_inset . \end_layout \begin_layout Enumerate 2017-12-11/12 Monday: Presentations by Matthew and Tanay. Tuesday: Guest lecture by Huacheng Yu. \begin_inset ERT status open \begin_layout Plain Layout \backslash newline \end_layout \end_inset \begin_inset CommandInset href LatexCommand href name "Lecture 19.pdf" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/L19.pdf" \end_inset , \begin_inset CommandInset href LatexCommand href name "Lecture 19.tex" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/L19.tex" \end_inset , \begin_inset CommandInset href LatexCommand href name "Lecture 19 blog post" target "https://emanueleviola.wordpress.com/2017/12/27/special-topics-in-complexity-theory-lecture-19/" \end_inset . \end_layout \begin_layout Subsection* Some presentations by students \end_layout \begin_layout Enumerate Matthew Dippel, \begin_inset CommandInset href LatexCommand href name "pdf" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/Dippel+Mehta.pdf" \end_inset , \begin_inset CommandInset href LatexCommand href name "tex" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/Dippel+Mehta.tex" \end_inset \end_layout \begin_layout Enumerate Xuangui Huang, \begin_inset CommandInset href LatexCommand href name "pdf" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/Huang.pdf" \end_inset , \begin_inset CommandInset href LatexCommand href name "tex" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/Huang.tex" \end_inset \end_layout \begin_layout Enumerate Chin Ho Lee, \begin_inset CommandInset href LatexCommand href name "pdf" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/Lee.pdf" \end_inset , \begin_inset CommandInset href LatexCommand href name "tex" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/Lee.tex" \end_inset \end_layout \begin_layout Enumerate Tanay Mehta, \begin_inset CommandInset href LatexCommand href name "pdf" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/Dippel+Mehta.pdf" \end_inset , \begin_inset CommandInset href LatexCommand href name "tex" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/Dippel+Mehta.tex" \end_inset \end_layout \begin_layout Enumerate Willy Quach, \begin_inset CommandInset href LatexCommand href name "pdf" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/Quach.pdf" \end_inset , \begin_inset CommandInset href LatexCommand href name "tex" target "http://www.ccs.neu.edu/home/viola/classes/spepf17-lectures/Quach.tex" \end_inset \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash end{document} \end_layout \end_inset \end_layout \begin_layout Section Todo \end_layout \begin_layout Standard cf. math/misc.lyx \end_layout \begin_layout Section Pseudorandomness \end_layout \begin_layout Enumerate 3 theories of randomness (trivia) Classical (can't distinguish). Kolmogorov Complexity. Pseudorandomness \end_layout \begin_layout Enumerate The goals of pseudorandomness. PRGs \begin_inset Formula $f:\{0,1\}^{s}\to\{0,1\}^{n}$ \end_inset as three properties. (1) \begin_inset Formula $n>s$ \end_inset . (2) fools a class of tests \begin_inset Formula $T=\{t:\{0,1\}^{n}\to\{0,1\}\}$ \end_inset , i.e. \begin_inset Formula $\forall t\in T$ \end_inset ... (3) Efficient Drop one and it's easy. E.g., drop efficiency. \end_layout \begin_layout Enumerate Claim: For all \begin_inset Formula $T$ \end_inset there exists an inefficient PRG with seed length \begin_inset Formula $\log_{2}\log_{2}|T|+2\log1/\e+O(1)$ \end_inset . Proof: Chernoff gives error \begin_inset Formula $2^{O(2^{s}\epsilon^{2})}$ \end_inset . \end_layout \begin_layout Enumerate Example: \begin_inset Formula $T=$ \end_inset circuits of size \begin_inset Formula $n^{100}$ \end_inset (all useful algorithms). Number of such circuits is \begin_inset Formula $2^{n^{O(1)}}$ \end_inset . So seed length is \begin_inset Formula $O(\log n/\epsilon)$ \end_inset . \end_layout \begin_layout Enumerate Goal: Construct explicit PRGs with good seed length for richer and richer \begin_inset Formula $T$ \end_inset . \end_layout \begin_layout Enumerate Simplest \begin_inset Formula $T$ \end_inset : \begin_inset Formula $k$ \end_inset -local functions. \begin_inset Formula $k=1$ \end_inset , \begin_inset Formula $s=1$ \end_inset . \begin_inset Formula $k=2$ \end_inset : \end_layout \begin_layout Enumerate Bounded independence. Achievable bounds. Finite fields. Lower bounds: Suppose you have a distribution over \begin_inset Formula $n$ \end_inset bits. Write down the whole space an \begin_inset Formula $\ell\times n$ \end_inset matrix. Work over \begin_inset Formula $\pm1$ \end_inset . Consider subsets of \begin_inset Formula $k/2$ \end_inset vectors. Any two are orthogonal. So they are independent. So \begin_inset Formula $\ell\ge\binom{n}{k/2}\ge\Omega(n/k)^{k}$ \end_inset . The linear-algebra method. Bounded independence fools And, AC \begin_inset Formula $^{0}$ \end_inset . (I could do sandwich, Section 15.1 in ineq.pdf, but it's useless.) \end_layout \begin_layout Enumerate Small-bias. Achievable bounds. The powering construction. Work on field of size \begin_inset Formula $2^{\ell}$ \end_inset use two elements \begin_inset Formula $a,b\in F$ \end_inset . \begin_inset Formula $i$ \end_inset -th output is \begin_inset Formula $\langle a^{i},b\rangle$ \end_inset . Error is \begin_inset Formula $\le n/2^{\ell}$ \end_inset seed = \begin_inset Formula $2\ell$ \end_inset . So pick \begin_inset Formula $\ell=\log(n/\epsilon)$ \end_inset get error \begin_inset Formula $\epsilon$ \end_inset and seed \begin_inset Formula $2\log(n/\epsilon)$ \end_inset . Derandomizing the powering construction. Replace \begin_inset Formula $b$ \end_inset with a small-bias. This shows: \begin_inset Formula $s(n,\epsilon)\le\log(n/0.5\e)+s(s(n,\e),0.5\e)$ \end_inset . Two steps: \begin_inset Formula $\log(n/\e)+\log(\log(n/\e)/\e)=\log(n)+2\log1/\e+\log\log n/\e$ \end_inset . Not much gain in more steps. Ta-Shma gets \begin_inset Formula $n+(2+o(1))\log1/\e$ \end_inset . \end_layout \begin_layout Enumerate Fooling functions with small variance. GKM and derandomized GKM. \end_layout \begin_layout Enumerate The tribes function. Goal: get error \begin_inset Formula $1/n$ \end_inset and seed length \begin_inset Formula $\tilde{O(\log n})$ \end_inset . Small-bias isn't enough \begin_inset CommandInset citation LatexCommand cite key "DETT" \end_inset . \end_layout \begin_layout Enumerate The GMRTV generator. \end_layout \begin_layout Subsection GMRTV \end_layout \begin_layout Standard Do Tribes in fixed order. \begin_inset Quotes eld \end_inset Noise \begin_inset Quotes erd \end_inset is always half the clauses. So you always get clauses of the same width. You expect only a polynomial fraction of clauses to survive. Induction argument: Given a Tribes function with width \begin_inset Formula $w$ \end_inset and some number of clauses, can reduce the width in half using \begin_inset Formula $\tilde{O(\log n/\e)}$ \end_inset seed length. \end_layout \begin_layout Standard At each step we use a small-bias generator with bias \begin_inset Formula $\alpha$ \end_inset . \end_layout \begin_layout Standard W.l.o.g. #clauses \begin_inset Formula $\le2^{w}\log(1/\e)$ \end_inset . \end_layout \begin_layout Standard Noise makes the variance \begin_inset Formula $1/2^{(1+\Omega(1))w}$ \end_inset . \end_layout \begin_layout Standard So total variance is \begin_inset Formula $1/2^{\Omega(w)}$ \end_inset assuming \begin_inset Formula $w\ge c\log\log(1/\e)$ \end_inset \end_layout \begin_layout Standard By the statement in the email I just sent Chin, the error is \begin_inset Formula \[ 2^{-\Omega(wd)}+2^{wd}\alpha. \] \end_inset \end_layout \begin_layout Standard We pick \begin_inset Formula $d$ \end_inset so that \begin_inset Formula $wd=\log(1/\e)$ \end_inset . This gives error \begin_inset Formula $\e$ \end_inset for \begin_inset Formula $\alpha=\e^{2}$ \end_inset . \end_layout \begin_layout Standard Repeat above until \begin_inset Formula $w \begin_inset Formula $2^{c}$ \end_inset rectangles. Use lemma. \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \end_layout \end_inset \end_layout \begin_layout Standard For any snafu have \begin_inset Formula $1/\log^{\Omega(1)}|G|$ \end_inset bound in lemma, hence \begin_inset Formula $\log\log|G|$ \end_inset in theorem. For \begin_inset Formula $A_{n}$ \end_inset tight. \end_layout \begin_layout Section Austin's proof \end_layout \begin_layout Standard Gift: Simpler \end_layout \begin_layout Standard Intuition: If set is \begin_inset Formula $A\times B$ \end_inset then \begin_inset Formula $A(x)B(y)A(xg)B(y)A(x)B(gy)=A(x)B(y)A(xg)B(gy)$ \end_inset . \end_layout \begin_layout Standard Same as \begin_inset Formula $A(x)B(y)A(z)B(x^{-1}zy)\sim\E[f]^{2}$ \end_inset . Follows by Th. 1.2 in \begin_inset CommandInset ref LatexCommand ref reference "sec:Quasirandom-groups" \end_inset . \end_layout \begin_layout Standard Idea: decompose. \end_layout \begin_layout Standard But if set is sum of \begin_inset Formula $2$ \end_inset rectangles, already not clear how to relate cross product to original function. \end_layout \begin_layout Standard Idea: Decompose into functions such that expectation is same for any \begin_inset Formula $g$ \end_inset . Then can set \begin_inset Formula $g=1$ \end_inset and get \begin_inset Formula $\E[f]^{3}$ \end_inset . \end_layout \begin_layout Standard Very important that structured functions are of the form \begin_inset Formula $u(x)v(y)w(xgy)$ \end_inset , so you can set \begin_inset Formula $g=1$ \end_inset and still fool via quasirandomness -- see Summary below. \end_layout \begin_layout Standard State regularity lemma for the simple decomposition \begin_inset Formula $\otimes_{1,2}$ \end_inset . \end_layout \begin_layout Standard Need 3 different decompositions: (15)-(17) \begin_inset CommandInset citation LatexCommand cite key "Austin2016" \end_inset . \end_layout \begin_layout Paragraph My intuition: \end_layout \begin_layout Standard With the naive decomposition in rectangles, where each of the three terms in the definition of corner is written as a rectangle, you can use pseudorandom ness easily to show that the structured parts behave well. However the problem is probably how to control the non-structured part. \end_layout \begin_layout Standard In the Austin decomposition, where you use more fancy base functions such as \begin_inset Formula $u(x)v(xy)$ \end_inset (in my version of Austin) structured functions only have \begin_inset Formula $3$ \end_inset terms, and are trivially fooled \end_layout \begin_layout Subsection Estimates for structured functions \end_layout \begin_layout Standard Corollary 2 in \begin_inset CommandInset citation LatexCommand cite key "Austin2016" \end_inset . \end_layout \begin_layout Standard Corollary: Functions are sum of \begin_inset Formula $|G|^{\Omega(1)}$ \end_inset structured functions again \begin_inset Formula $\psi(g)$ \end_inset does not vary. \end_layout \begin_layout Standard So just bound \begin_inset Formula $\psi(1_{G})=\E_{x,y}E_{1}f\cdot E_{2}f\cdot E_{3}f$ \end_inset where \begin_inset Formula $f$ \end_inset char. func. of set. \end_layout \begin_layout Standard Relate this to \begin_inset Formula $\E f$ \end_inset : \end_layout \begin_layout Lemma Holder inequality: Let \begin_inset Formula $X_{i}$ \end_inset be \begin_inset Formula $k$ \end_inset r.v., and \begin_inset Formula $c_{i}\ge0$ \end_inset so that \begin_inset Formula $\sum_{i}1/c_{i}=1$ \end_inset . Then \begin_inset Formula \[ \E[\prod_{i}X_{i}]\le\prod_{i}\E[X_{i}^{c_{i}}]^{1/c_{i}}. \] \end_inset \end_layout \begin_layout Standard Use as: \begin_inset Formula \begin{align*} \E f & =\E(fE_{1}fE_{2}fE_{3}f)^{1/4}(f/E_{1}f)^{1/4}(f/E_{2}f)^{1/4}(f/E_{3}f)^{1/4}\\ & \le\E^{1/4}[fE_{1}fE_{2}fE_{3}f]\cdot\E^{1/4}[f/E_{1}f]\cdot\E^{1/4}[f/E_{2}f]\cdot\E^{1/4}[f/E_{3}f]\ \ \ (Holder) \end{align*} \end_inset \end_layout \begin_layout Standard Last three terms are \begin_inset Formula $\le1$ \end_inset : \end_layout \begin_layout Standard \begin_inset Formula $\E(f/E_{1}f)=E_{x,y}f(x,y)/E_{(x',y')\in P(x,y)}f(x',y')$ \end_inset , \begin_inset Formula $P(x,y)$ \end_inset is cell \begin_inset Formula $\ni(x,y)$ \end_inset . \end_layout \begin_layout Standard But \begin_inset Formula $E_{x,y}=E_{x,y}E_{(x'',y'')\in P(x,y)}$ \end_inset so you get \begin_inset Formula \[ E_{x,y}a/a\le1 \] \end_inset \end_layout \begin_layout Standard So \begin_inset Formula $\E f\le(\E fE_{1}fE_{2}fE_{3}f)^{1/4}\le(\E E_{1}fE_{2}fE_{3}f)^{1/4}$ \end_inset where the last inequality holds because the functions are non-negative. \end_layout \begin_layout Subsection Bounds for quasirandom \end_layout \begin_layout Standard Intuitive guarantee: Each decomposition gives \begin_inset Formula $f^{\perp}$ \end_inset with low correlation with base funcs (15)-(17) \begin_inset CommandInset citation LatexCommand cite key "Austin2016" \end_inset . \end_layout \begin_layout Standard I write \begin_inset Formula $L^{g}(x,y)=xg,y$ \end_inset and \begin_inset Formula $R^{g}(x,y)=(x,gy)$ \end_inset . We are trying to bound \begin_inset Formula $E_{x,y,g}f(x,y)fL^{g}(x,y)fR^{g}(x,y)$ \end_inset . \end_layout \begin_layout Standard We decompose \begin_inset Formula $f$ \end_inset as \begin_inset Formula $f=r+f^{\perp}$ \end_inset and need to bound \begin_inset Formula $\E f\cdot fL^{g}\cdot f^{\perp}R^{g}$ \end_inset . Here's the argument. We iteratively pull out each \begin_inset Formula $f$ \end_inset until we have only \begin_inset Formula $f^{\perp}$ \end_inset : \begin_inset Formula \begin{align*} Ef\cdot fL^{g}\cdot f^{\perp}R^{g} & =Ef(x,y)f(xg,y)f^{\perp}(x,gy)\\ & =Ef(x,y)f(xgy^{-1},y)f^{\perp}(x,g)\ \ \ \ (g\to gy^{-1})\\ & =E_{x,y}f(x,y)E_{g}f(xgy^{-1},y)f^{\perp}(x,g)\\ & \le\left(E_{x,y}f(x,y)^{2}\right)E_{x,y,g,g'}f(xgy^{-1},y)f^{\perp}(x,g)f(xg'y^{-1},y)f^{\perp}(x,g')\\ & \le E_{x,y,g,g'}f(xgy^{-1},y)f^{\perp}(x,g)f(xg'y^{-1},y)f^{\perp}(x,g')\ (drop)\\ & =E_{x,y,g,g'}f(gy^{-1},y)f^{\perp}(x,x^{-1}g)f(g'y^{-1},y)f^{\perp}(x,x^{-1}g')\ (g\to x^{-1}g,g'\to x^{-1}g')\\ & =E_{y,g,g'}f(gy^{-1},y)f(g'y^{-1},y)E_{x}f^{\perp}(x,x^{-1}g)f^{\perp}(x,x^{-1}g')\\ & \le E_{g,g',x,x'}f^{\perp}(x,x^{-1}g)f^{\perp}(x,x^{-1}g')f^{\perp}(x',x'^{-1}g)f^{\perp}(x',x'^{-1}g'). \end{align*} \end_inset \end_layout \begin_layout Standard Note \begin_inset Formula $y$ \end_inset disappeared. Fix \begin_inset Formula $x'$ \end_inset and \begin_inset Formula $g'$ \end_inset . The last term becomes a bounded constant \begin_inset Formula $c$ \end_inset . Write \begin_inset Formula $g=xy$ \end_inset . Then we get \begin_inset Formula \[ c\cdot E_{x,y}f^{\perp}(x,y)f^{\perp}(x,x^{-1}g')f^{\perp}(x',x'^{-1}xy). \] \end_inset \end_layout \begin_layout Standard The second term is a function of \begin_inset Formula $x$ \end_inset only, the third is a function of \begin_inset Formula $xy$ \end_inset only. So we need to bound the correlation with such functions. \end_layout \begin_layout Standard So, we have \begin_inset Formula $u(x)$ \end_inset and \begin_inset Formula $v(xy)$ \end_inset here. \end_layout \begin_layout Paragraph Note: \end_layout \begin_layout Standard Austin gets \begin_inset Formula $v(x^{-1}y)$ \end_inset . What is off is that Austin works with a different type of corners: they are not \begin_inset Formula $(x,y)(xg,y)(x,gy)$ \end_inset as above but \begin_inset Formula $(x,y)(gx,y)(gx,gy)$ \end_inset . \end_layout \begin_layout Standard I think my type gives slightly different bases. You get base functions that depend on \begin_inset Formula $xy$ \end_inset instead of \begin_inset Formula $x^{-1}y$ \end_inset which is also a bit simpler. \end_layout \begin_layout Standard So the base functions might be like his except \begin_inset Formula $xy$ \end_inset instead of \begin_inset Formula $x^{-1}y$ \end_inset . \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \end_layout \end_inset \end_layout \begin_layout Standard So one base function is \begin_inset Formula $u(x)$ \end_inset and \begin_inset Formula $v(xy)$ \end_inset . \end_layout \begin_layout Standard Another is \begin_inset Formula $u(y)$ \end_inset and \begin_inset Formula $v(xy)$ \end_inset . This is the case in which \begin_inset Formula $f^{\perp}$ \end_inset appears in the second term. To analyze this you replace all vars with their inverses. Then \begin_inset Formula $f'(x,y):=f(y^{-1},x^{-1})$ \end_inset . Now the \begin_inset Formula $\perp$ \end_inset is in the third term, you apply the previous argument, you get the base of \begin_inset Formula $u(x)$ \end_inset and \begin_inset Formula $v(xy)$ \end_inset and you swap things back. \end_layout \begin_layout Standard The last base functions are \begin_inset Formula $u(x)$ \end_inset and \begin_inset Formula $v(y)$ \end_inset . This is if the \begin_inset Formula $\perp$ \end_inset is in the term \begin_inset Formula $f(x,y)$ \end_inset . Just do \begin_inset Formula $g\to x^{-1}g,$ \end_inset C.-S. to get \begin_inset Formula $f^{\perp}(x,y)f(x,x^{-1}gy)f^{\perp}(x',y)f(x',x'^{-1}gy)$ \end_inset . Then use \begin_inset Formula $g$ \end_inset to kill \begin_inset Formula $y$ \end_inset , do another C.-S. and you get the box norm of \begin_inset Formula $f^{\perp}$ \end_inset . \end_layout \begin_layout Standard One learning point is that the box norm measure the correlation with base functions (not sure if I'll use this explicitly). \end_layout \begin_layout Paragraph Summary: \end_layout \begin_layout Standard When you apply the above 3 decompositions to the functions, you get products of the type \begin_inset Formula \[ u_{1}(x)v_{1}(y)u_{2}(y)v_{2}(xy)u_{3}(x)v_{3}(xy). \] \end_inset \end_layout \begin_layout Standard When applied to my inputs, you get \begin_inset Formula \[ u_{1}(x)v_{1}(y)u_{2}(y)v_{2}(xgy)u_{3}(x)v_{3}(xgy). \] \end_inset \end_layout \begin_layout Standard This is the type such that you can set \begin_inset Formula $g=1$ \end_inset and argue the expectation over \begin_inset Formula $x,y$ \end_inset has not changed by quasirandomness. It is important here that e.g. you get \begin_inset Formula $u_{3}(x)$ \end_inset and not \begin_inset Formula $u_{3}(xg)$ \end_inset . \end_layout \begin_layout Paragraph Question: \end_layout \begin_layout Standard Weak regularity writes any function as a sum of \emph on polynomially \emph default many \emph on possibly overlapping \emph default rectangles. It seems everything goes through with the overlap \emph on except \emph default it's not clear how to get that the approximant is an average value. (Lemma 7 in the weak regularity lemma, whose proof I have not read, seems to rely on having a disjoint partition.) \end_layout \begin_layout Section Arithmetic complexity \end_layout \begin_layout Standard Ryser's formula is a depth-3 circuit. \end_layout \begin_layout Standard Fischer's identity is a special case of Ryser: Given \begin_inset Formula $x_{1},\ldots,x_{n}$ \end_inset build a matrix where every row is \begin_inset Formula $x_{1},\ldots,x_{n}$ \end_inset . \end_layout \begin_layout Standard Saxena's duality trick Sec. 2 of \begin_inset CommandInset href LatexCommand href name "this" target "www.cse.iitk.ac.in/users/nitin/papers/diagonal.pdf" \end_inset . \end_layout \begin_layout Section Faster orthogonal vectors via the polynomial method \end_layout \begin_layout Standard This is in Section 3 of http://web.stanford.edu/~rrwill/faster-orthog-final.pdf \end_layout \begin_layout Standard the parameters seem different there: the number of monomials is \begin_inset Formula $poly(s)\binom{d}{\log s}^{2}$ \end_inset instead of what's written in next paragraph. \end_layout \begin_layout Standard How to solve faster orthogonal vectors. I have two lists of \begin_inset Formula $n$ \end_inset vectors of dimension \begin_inset Formula $d=O(log$ \end_inset n). You break them up in \begin_inset Formula $n/s$ \end_inset groups of \begin_inset Formula $s$ \end_inset each. Construct a circuit that takes as input all the \begin_inset Formula $2s$ \end_inset vectors in two groups, and checks if some pair is orthogonal. This is just an OrAndOr polynomial. Convert this into a polynomial with \begin_inset Formula ${s \choose d}$ \end_inset monomials using standard tricks. Then you want to run this polynomial over all pairs of groups. So you want to evaluate this polynomial over \begin_inset Formula $A\times B$ \end_inset where \begin_inset Formula $|A|=|B|=n/s$ \end_inset . This can be done in time roughly \begin_inset Formula $(n/s)^{2}$ \end_inset as long as the number of monomials \begin_inset Formula ${s \choose d}$ \end_inset is less than the size of \begin_inset Formula $A$ \end_inset raised to \begin_inset Formula $0.1$ \end_inset . So we need \begin_inset Formula $s^{d}$ \end_inset to be less than \begin_inset Formula $(n/s)^{0.1}$ \end_inset . If I pick \begin_inset Formula $s=n^{1/10d}$ \end_inset I get that. \end_layout \begin_layout Standard This polynomial is probabilistic, so you also repeat this many times. \end_layout \begin_layout Standard To make it deterministic, use small-bias sets for the big Or. Then somehow you want to sum this over the integers, for which you use modulus-amplifying polynomials. \end_layout \begin_layout Standard \begin_inset CommandInset bibtex LatexCommand bibtex bibfiles "Bibliography,C:/home/krv/math/OmniBib" options "plain" \end_inset \end_layout \end_body \end_document