## An invitation to tensor networks

Michael Walter

University of Amsterdam

December 11, 2018

Michael Walter

University of Amsterdam

December 11, 2018

Ankit Garg

Microsoft Research

December 10, 2018

Chernoff-type bounds study concentration of sums of independent random variables and are extremely useful in various settings. In many settings, the random variables may not be completely independent but only have limited independence. One such setting, which turns out to be useful in derandomization and theoretical computer science, in general, involves random walks on expanders. I will talk about a Chernoff-type bound for sums of matrix-valued random variables sampled via a random walk on an expander.

Mika Goos

Member, School of Mathematics

November 27, 2018

For any unsatisfiable CNF formula F that is hard to refute in the Resolution proof system, we show that a gadget-composed version of F is hard to refute in any proof system whose lines are computed by efficient communication protocols---or, equivalently, that a monotone function associated with F has large monotone circuit complexity. As an application, we show that a monotone variant of XOR-SAT has exponential monotone circuit complexity, which improves qualitatively on the monotone vs. non-monotone separation of Tardos (1988).

Urmila Mahadev

UC Berkeley

November 26, 2018

We present the first protocol allowing a classical computer to interactively verify the result of an efficient quantum computation. We achieve this by constructing a measurement protocol, which allows a classical string to serve as a commitment to a quantum state. The protocol forces the prover to behave as follows: the prover must construct an n qubit state of his choice, non-adaptively measure each qubit in the Hadamard or standard basis as directed by the verifier, and report the measurement results to the verifier.

Mika Goos

Member, School of Mathematics

November 20, 2018

I will survey new lower-bound methods in communication complexity that "lift" lower bounds from decision tree complexity. These methods have recently enabled progress on core questions in communication complexity (log-rank conjecture, classical--quantum separations) and related areas (circuit complexity, proof complexity, LP/SDP formulations). I will prove one concrete lifting theorem for non-deterministic (NP) query/communication models.

Shachar Lovett

University of California San Diego

November 6, 2018

Shachar Lovett

University of California San Diego

November 5, 2018

The Erdos-Rado sunflower conjecture is one of the tantalizing open problems in combinatorics. In my talk, I will describe several attempts on how to get improved bounds for it. These will lead to surprising connections with several other combinatorial structures, such as randomness extractors, intersecting families and DNFs.

Based on joint works with Xin Li, Noam Solomon and Jiapeng Zhang.

Dor Minzer

Member, School of Mathematics

October 30, 2018

The Unique-Games Conjecture is a central open problem in the field of PCP’s (Probabilistically Checkable Proofs) and hardness of approximation, implying tight inapproximability results for wide class of optimization problems.

We will discuss PCPs, the Unique-Games Conjecture and some recent progress. (no familiarity with PCPs or with last week's talk are needed).

Ryan O'Donnell

Carnegie Mellon University

October 29, 2018

Gal Kronenberg

Tel Aviv University

October 29, 2018

For a family of graphs F, a graph G is F-universal if G contains every graph in F as a (not necessarily induced) subgraph. A natural candidate to serve as