Monday, March 6th, 2017

9:30 am10:00 am
Explicit constructions of pseudorandom objects (e.g., pseudorandom generators, expander graphs, or boolean functions of large circuit complexity) often come with very constructive proofs of existence. For example,
(1) the Nisan-Wigderson (NW) generator based on an assumed ``hard'' function f (of large circuit complexity) has the constructive analysis: There is an efficient uniform reduction (with oracle access to f) taking an algorithm ``breaking'' the generator into a small circuit for f;
(2) the Natural Proofs framework of Razborov and Rudich argues that most circuit lower bound proofs come with an efficiently testable property  that distinguishes ``easy'' functions (with small circuit complexity) from random functions;
(3) the analysis of the iterative Zig-Zag construction of expanders due to Reingold, Vadhan, and Wigderson contains an efficient algorithm taking a non-expanding set of vertices in the graph at any given stage i into a non-expanding set of vertices in the graph at the previous stage (i-1). 
I'll talk about several recent applications of such constructive proofs: 
*  Properties (1) + (2)  yield an efficient (agnostic) learning query algorithm for every sufficiently strong circuit class that has a natural proof of circuit lower bounds.  As an application, the class AC^0[p], for any prime p, is (agnostically) learnable in quasi-polynomial time. (Previously, only the case of AC^0 was known by the results of Linial, Mansour, and Nisan.)  [joint with Carmosino, Impagliazzo, and Kolokolova.] 
* The analysis of the zig-zag construction in (3) can be made even more constructive: it is formalizable in the theory VNC^1 of NC^1-reasoning. This implies (using the previous work by Jerabek) that  monotone LK (MLK) proof system polynomially simulates LK proof system on monotone sequents, strengthening the quasi-polynomial simulation result by Atserias, Galesi, and Pudlak.  [joint with S. Buss, Kolokolova, and Koucky.]


10:00 am10:30 am
We give a deterministic poly(n)/epsilon^2 time algorithm for approximately counting (to within epsilon) the fraction of solutions to a system of quadratic n-variate equations over F2. Note that random sampling would yield a similar running time in terms of n and epsilon.


11:00 am12:00 pm

Tentative: There is an interesting connection between hash functions used in data structures and pseudorandom generators for small space. A sequence of results exploited this connection (in both directions) and there are several interesting open problems.

2:00 pm3:00 pm
A family of graphs G_1,...,G_k is said to pack into a host graph H if there is a colouring of the edges of H with colours 0,...,k such that the edges of colour i form a copy of G_i for i=1,...,k. Packing problems have a long and interesting history in (hyper)graph theory.
In particular, there has recently been much progress on various long-standing conjectures on packing families of large graphs into the complete graph. In this talk I will outline this progress, and introduce a new result on (near-perfect) packings of families of graphs with constant degeneracy which generalises several previous results. The proof of this new result uses a very natural randomised greedy packing algorithm and relies on the fact that this algorithm preserves certain pseudorandomness properties. I will sketch the ideas.
Based on joint work with Peter Allen, Jan Hladk\'y, and Diana Piguet.
3:10 pm3:40 pm

Advancing the sparse regularity method, we prove one-sided and two-sided regularity inheritance lemmas for subgraphs of bijumbled graphs, improving on results of Conlon, Fox and Zhao. These inheritance lemmas also imply improved $H$-counting lemmas for subgraphs of bijumbled graphs, for some $H$.

This is joint work with Peter Allen, Julia Boettcher and Jozef Skokan.


4:10 pm4:40 pm

Let A be a set of integers.  For any integer h\geq2, we say that A is a B_h-set if the h-wise sums  a_1 + ... + a_h (a_1,...,a_h\in A; a_1\leq...\leq a_h) are all distinct.  Let [n] = {1,...,n}.  A natural question is the determination or estimation of the extremal function
  F_h(n) = max{|A|: A\subset[n] is a B_h-set}.

The particular case of this problem in which h = 2 was raised by Simon Sidon in the 1930s and B_2-sets are known as Sidon sets.  An immediate argument shows that F_h(n) = o(n) and, therefore, this is a so called `degenerate' extremal problem.  As it is often the case with
degenerate problems, the structure of the extremal, that is, largest, B_h-sets A\subset[n] is not well understood.

We address the simpler problem of estimating the number of B_h-sets A\subset[n] of a given cardinality.  As a consequence of these bounds, we determine, asymptotically, for any integer m\leq n, the cardinality
of the largest B_h-sets contained in a typical m-element subset of [n].

This is joint work with D. Dellamonica Jr, S.J. Lee, V. Rödl and W. Samotij.

Tuesday, March 7th, 2017

9:30 am10:30 am

Addressing a problem of Goldreich and of Alon and Fox, we prove new sufficient and necessary criteria, guaranteeing that a graph property admits a removal lemma with a polynomial bound. Although both are simple combinatorial criteria, they imply almost all prior positive and negative results of this type, as well as many new ones. In particular, we will show that every semi-algebraic graph property admits a removal lemma with a polynomial bound. This confirms a conjecture of Alon. 

Joint work with L. Gishboliner

11:00 am12:00 pm
We study \emph{forcing pairs} for \emph{quasirandom graphs}. Chung, Graham, and Wilson initiated the study of families~$\cF$ of graphs with the property that if a large graph~$G$ has approximately homomorphism density $p^{e(F)}$ for some fixed $p\in(0,1]$ for every $F\in \cF$, then $G$ is quasirandom with density~$p$. Such families $\cF$ are said to be \emph{forcing}. Several forcing families were found over the last three decades and characterising all bipartite graphs $F$ such that $(K_2,F)$ is a forcing pair is a well known open problem in the area of quasirandom graphs, which is closely related to Sidorenko's conjecture. In fact, most of 
the known forcing families involve bipartite graphs only.
We consider forcing pairs containing the triangle~$K_3$. In particular, we show that if~$(K_2,F)$ is a forcing pair, then so ist $(K_3,F^\Delta)$, where $F^\Delta$ is obtained from~$F$ by replacing every edge of $F$ by a triangle (each of which introducing a new vertex). For the proof we first show that $(K_3,C_4^\triag)$ is a forcing pair, which strengthens related results of Simonovits and S\'os and of Conlon et al.
2:00 pm3:00 pm

The question of finding an epsilon-biased set with close to optimal support size, or, equivalently, finding an explicit binary code with distance $\frac{1-\eps}{2}$ and rate close to the Gilbert-Varshamov bound, attracted a lot of attention in recent decades. In this paper we solve the problem almost optimally and show an explicit $\eps$-biased set over $k$ bits with support size $O(\frac{k}{\eps^{2+o(1)}})$. This improves upon all previous explicit constructions which were in the order of $\frac{k^2}{\eps^2}$, $\frac{k}{\eps^3}$ or $\frac{k^{5/4}}{\eps^{5/2}}$. The result is close to the Gilbert-Varshamov bound which is $O(\frac{k}{\eps^2})$ and the lower bound which is $\Omega(\frac{k}{\eps^2 \logeps})$.

The main technical tool we use is bias amplification with the $s$-wide replacement product. The sum of two independent samples from an $\eps$-biased set is $\eps^2$ biased. Rozenman and Wigderson showed how to amplify the bias more economically by choosing two samples with an expander. Based on that they suggested a recursive
construction that achieves sample size $O(\frac{k}{\eps^4})$. We show that amplification with a long random walk over the $s$-wide replacement product reduces the bias almost optimally.

3:10 pm3:40 pm
Speaker: Piotr Indyk, MIT
For every fixed constant α > 0, we design a *deterministic* algorithm for computing the k-sparse Walsh-Hadamard
transform of an N-dimensional vector x  in time k^(1+α) polylog n. Specifically, the algorithm is given query access to x and computes an approximate  minimizer of the L1 approximation error ||y^ − x^||_1 over all k-sparse y^, where x^ denotes the spectrum of x. This is the first sub-linear time deterministic algorithm for this problem with sub-quadratic dependence on k.  
An important technical tool that we use is a construction of nearly optimal and linear lossless
condensers which is a careful instantiation of the GUV condenser (Guruswami, Umans, Vadhan,
JACM 2009). 
Joint work with Mahdi Cheraghchi. Appeared in SODA'16.


Wednesday, March 8th, 2017

9:30 am10:30 am

We introduce the concept of a randomness steward, a tool for saving random bits when executing a randomized estimation algorithm 𝖤𝗌𝗍 on many adaptively chosen inputs. For each execution, the chosen input to 𝖤𝗌𝗍 remains hidden from the steward, but the steward chooses the randomness of 𝖤𝗌𝗍 and, crucially, is allowed to modify the output of 𝖤𝗌𝗍. The notion of a steward is inspired by adaptive data analysis, introduced by Dwork et al. Suppose 𝖤𝗌𝗍 outputs values in ℝd, has ℓ∞ error ϵ, has failure probability δ, uses n coins, and will be executed k times. For any γ>0, we construct a computationally efficient steward with ℓ∞ error O(ϵd), failure probability kδ+γ, and randomness complexity n+O(klog(d+1)+(logk)log(1/γ)). To achieve these parameters, the steward uses a PRG for what we call the block decision tree model, combined with a scheme for shifting and rounding the outputs of 𝖤𝗌𝗍. (The generator is a variant of the INW generator.)

As applications of our steward, we give time- and randomness-efficient algorithms for estimating the acceptance probabilities of many adaptively chosen Boolean circuits and for simulating any algorithm with an oracle for 𝗉𝗋𝗈𝗆𝗂𝗌𝖾-𝖡𝖯𝖯 or 𝖠𝖯𝖯. We also give a randomness-efficient version of the Goldreich-Levin algorithm; our algorithm finds all Fourier coefficients with absolute value at least θ of a function F:{0,1}n→{−1,1} using O(nlogn)⋅poly(1/θ) queries to F and O(n) random bits, improving previous work by Bshouty et al. Finally, we prove a randomness complexity lower bound of n+Ω(k)−log(δ′/δ) for any steward with failure probability δ′, which nearly matches our upper bounds in the case d≤O(1).

11:00 am12:00 pm
From the the fundamental theorem of statistical learning, one can learn any hypothesis class H with O(log|H|) labeled examples. Alas, learning with so few examples requires saving the examples in memory, and this requires |X|^O(log|H|) memory states, where X is the set of all labeled examples. 
A question that arises is how many labeled examples are needed in case the memory is bounded. 
Previous work showed, using techniques such as linear algebra and Fourier analysis, that parities cannot be learned with bounded memory.
One might wonder whether a combinatorial condition exists for the unlearnability with bounded memory of general classes H, as we have with the condition VCdim(H)=infinity for PAC unlearnability. 
We show such a combinatorial condition by demonstrating a surprising connection between an hypothesis class H being "mixing" and its unlearnability with bounded memory. 
More specifically, we show that if an hypothesis class H, when viewed as a bipartite graph between hypotheses H and labeled examples X, is mixing then it is unlearnable under a certain bound on the memory. 
Note that the class of parities is mixing. Additionally, as an immediate corollary, we get that most hypotheses classes are unlearnable with bounded memory (even though they are all learnable with unbounded memory). 
Our proof technique is combinatorial in nature and very different from previous work.
This is joint work with Michal Moshkovitz
3:30 pm4:00 pm
Regularity lemmas are very useful tools in graph theory and theoretical computer science. They roughly involve dividing a graph into a bounded number of parts such that the graph looks in some sense like a graph that is pseudorandom between the pairs. Due to these applications, having algorithmic versions is of interest. We review a recent algorithmic version of the (weak) Frieze-Kannan regularity lemma, and give some applications to finding strong regular partitions, and subgraph counting. Joint work with Jacob Fox and Yufei Zhao.


4:10 pm5:10 pm
A subspace design is a (large) collection of subspaces of F_q^n, each of small co-dimension, such that for any low-dimensional subspace W, only a small number from the collection have a non-trivial intersection with W. This notion was put forth in the context of algebraic list decoding where it enabled the construction of optimal redundancy list-decodable codes over small alphabets and for the rank-metric. An explicit construction of subspace designs over large fields with near-optimal parameters was later given based on polynomials; curiously, this construction is closely related to folded Reed-Solomon codes, the list-decodable codes which motivated subspace designs in the first place. 
Subspace designs have since been found to play a central role in the emerging theory of "linear-algebraic pseudorandomness" which aims to understand analogs of Boolean pseudorandom objects where the rank of subspaces plays the role of the size of subsets. In particular, they yield “rank condensers” which in turn enable construction of dimension expanders, the linear-algebraic analog of (vertex) expanders. Via this connection, the known explicit construction of subspace designs yield simple constant-degree dimension expanders over F_q^n when q \ge poly(n). Subspace designs over any field were recently constructed based on algebraic function fields; while this incurs a slight worsening of parameters, it raises hope that perhaps one can get constant-degree dimension expanders over any field via this route (the only known explicit construction for arbitrary fields, via monotone expanders, is quite complicated).
This talk will survey these developments revolving around subspace designs, their construction, and connections.
(Based on several joint works with Chaoping Xing, Swastik Kopparty, Michael Forbes, and Chen Yuan.)


Thursday, March 9th, 2017

9:30 am10:30 am
The polynomial identity testing problem is to decide whether a given succinct algebraic expression simplifies to the zero expression. This problem has a simple randomized algorithm, and derandomizing this algorithm is analogous to constructing pseudorandom generators fooling boolean computation. 
We will discuss a recent line of work derandomizing polynomial identity testing for the restricted class of expressions known as "read-once oblivious algebraic branching programs".  Pseudorandom generators for the analogous boolean notion are fundamental, as they correspond to derandomization of randomized logspace computations (RL).  Further, research into such generators has had many connections to well-studied objects such as expanders, extractors, and k-wise independent hash functions.
Likewise, the work on derandomizing "algebraic RL" has connections to linear-algebraic pseudorandomn objects such as rank-extractors and subspace-designs, which themselves have connections to list-decodable codes and dimension expanders. We will discuss the known results for derandomizing "algebraic RL", the various connections to other pseudorandom objects, and highlight the analogy with boolean pseudorandomness.
11:00 am11:30 am
We recently had a derandomization of the Isolation Lemma for perfect matchings in bipartite graphs and common base sets of two matroids. That is, a deterministic construction of an isolating weight assignment. The common idea in both the constructions is to work with their corresponding polytopes. In this talk, we present the approach in terms of general polytopes and describe sufficient conditions on the polytope for this approach to work. Finally, we argue that these conditions hold for bipartite matching polytope and common base set polytope.
11:40 am12:10 pm
The development of unconditional pseudorandom generators that fool small-space computations has seen much research activity and significant progress.
Notably, Nisan's generator stretches a seed of O(log^2 n) bits to n bits that cannot be distinguished from uniform by an O(log n)-space algorithm. However, reducing the seed length to O(log n) bits -- and, thus, proving RL=L -- remains an elusive goal. Subsequent improvements to Nisan's result only address special cases, and it seems new techniques are needed.
For other classes, such as small-depth circuits, halfspaces, and polynomials, there has been success in using Fourier-analytic techniques to construct pseudorandom generators.
This talk will discuss the use of Fourier-analytic techniques to construct pseudorandom generators that fool constant-space computations. In particular, for constant-width branching programs (a nonuniform model of constant-space computation), we can construct pseudorandom generators with polylogarithmic seed length for two special cases: permutation branching programs, and width 3. The generator uses small bias spaces combined with the ``mild pseudorandom restrictions'' approach of Gopalan, Meka, Reingold, Trevisan, and Vadhan. One advantage of the Fourier-analytic approach is that the pseudorandomness property is invariant under permutations of the output bits of the pseudorandom generator, which is a property that Nisan's generator lacks.
2:00 pm3:00 pm
We consider the fundamental derandomization problem of deterministically finding a satisfying assignment to a CNF formula that has many satisfying assignments. We give a deterministic algorithm which, given an n-variable poly(n)-clause CNF formula F that has |F^{-1}(1)| \geq \eps 2^n, runs in time
n^{\tilde{O}(\log\log n)^2}
for \eps \ge 1/\polylog(n) and outputs a satisfying assignment of F.  Prior to our work the fastest known algorithm for this problem was simply to enumerate over all seeds of a pseudorandom generator for CNFs; using the best known PRGs for CNFs [DETT10], this takes time n^{\tilde{\Omega}(\log n)} even for constant \eps.
Joint work with Rocco Servedio.
3:10 pm3:40 pm
Pseudorandom switching lemmas---randomness-efficient algorithms for sampling restrictions that dramatically simplify depth-two circuits---were first studied by Ajtai and Wigderson in their pioneering 1985 work on unconditional derandomization. While numerous pseudorandom switching lemmas have since been developed and employed in a variety of contexts, one that achieves the optimal parameters of Hastad's influential 1986 switching lemma  (which uses full randomness) was only obtained recently by Trevisan and Xue in 2013.
In this work we derandomize recently-developed ``multi-switching" lemmas, powerful generalizations of Hastad's 1986 switching lemma that deal with families of depth-two circuits. Our pseudorandom multi-switching lemma---a randomness-efficient algorithm for sampling restrictions that simultaneously simplify all circuits in a family---achieves the optimal parameters obtained by Impagliazzo, Matthews, and Paturi (2012) and Hastad (2014) using full randomness.  
We employ our pseudorandom multi-switching lemma to give the best known pseudorandom generators for two well-studied classes in unconditional derandomization: we give an $\eps$-PRG for the class of size-$M$ depth-$d$ AC^0 circuits with seed length $\log(M)^{d+O(1)}\cdot \log(1/\eps)$, and an $\eps$-PRG for the class of $S$-sparse $\F_2$ polynomials with seed length $2^{O(\sqrt{\log S})}\cdot \log(1/\eps)$. 
Our results bring the state of the art for unconditional derandomization of these classes into sharp alignment with the state of the art for computational hardness: improving on the seed lengths of either PRG would require breakthrough progress on longstanding and notorious circuit lower bounds. 
Joint work with Li-Yang Tan. 
4:10 pm4:40 pm
For any n-bit boolean function f, we show that the randomized communication complexity of the composed function f o g^n, where g is a small index gadget, is characterized by the randomized decision tree complexity of f. In particular, this means that many query complexity separations involving randomized models (e.g., classical vs. quantum) automatically imply analogous separations in communication complexity.

Joint work with Toniann Pitassi and Thomas Watson.


Friday, March 10th, 2017

9:30 am10:30 am
The goal of property testing is to quickly distinguish between objects which satisfy a property and objects that are $\epsilon$-far from satisfying the property. There are now several general results in this area which show that natural properties of combinatorial objects can be tested with ``constant'' query complexity, depending only on $\epsilon$ and the property, and not on the size of the object being tested. The upper bound on the query complexity coming from the proof techniques are often enormous and impractical. It remains a major open problem if better bounds hold. 

Hoppen, Kohayakawa, Moreira, and Sampaio conjectured and Klimo\v sov\'a and Kr\'al' proved that hereditary permutation properties are strongly testable, i.e., can be tested with respect to Kendall's tau distance. The query complexity bound coming from this proof is huge, even for testing a single forbidden subpermutation. We give a new proof which gives a polynomial bound in $1/\epsilon$ in this case. 

Maybe surprisingly, for testing with respect to the cut metric, we prove there is a universal (not depending on the property), polynomial in $1/\epsilon$ query complexity bound for two-sided testing hereditary properties of sufficiently large permutations. We further give a nearly linear bound with respect to a closely related metric which also depends on the smallest forbidden subpermutation for the property. Finally, we show that several different permutation metrics of interest are related to the cut metric, yielding similar results for testing withrespect to these metrics. 

This is a joint work with Jacob Fox.

11:00 am12:00 pm

This talk surveys problems from graph theory and additive combinatorics where randomness gives an essentially optimal bound. In some instances, pseudorandomness characterizes the optimizers.

2:00 pm3:00 pm
We show a reduction from the existence of explicit t-non-malleable extractors with a small seed length, to the construction of explicit two-source extractors with small error. Previously, such a reduction was known either when one source had entropy rate above half [Raz05] or for general entropy rates but only for large error [CZ16].
As in previous reductions we start with the Chattopadhyay and Zuckerman approach [CZ16], where an extractor is applied on one source to create a table, and the second source is used to sample a sub-table. In previous work, a resilient function was applied on the sub-table and the use of resilient functions immediately implied large error. In this work we replace the resilient function with the parity function (that is not resilient). 
The parameters we require from the non-malleable construction hold (quite comfortably) in non-explicit construction, but currently it is not known how to explicitly construct such graphs. As a result we do not give an unconditional construction of an explicit low-error two-source extractor. However, the reduction shows a new connection between non-malleable and two-source extractors, and also shows resilient functions do not play a crucial role in the two-source construction framework suggested in [CZ16].
Joint work with Avraham Ben-Aroya, Eshan Chattopadhyay, Xin Li and Amnon Ta-Shma.