## Computer Science and Discrete Mathematics

Theoretical Computer Science and Discrete Mathematics

## On Bilinear Complexity

Pavel Hrubes
University of Washington
January 14, 2013 - 11:15am

For a set of polynomials F, we define their bilinear complexity as the smallest k so that F lies in an ideal generated by k bilinear polynomials. The main open problem is to estimate the bilinear complexity of the single polynomial $\sum_{i,j}x_i^2 y_j^2$. This question is related to the classical sum-of-squares problem as well as to problems in arithmetic circuit complexity. We will focus on related sets of polynomials and prove some lower and upper bounds on their bilinear complexity.

## The SOS (aka Lassere/Positivestellensatz/Sum-of-Squares) System Series

Raghu Meka (1) and Avi Wigderson (2)
DIMACS (1) and Professor, School of Mathematics, IAS (2)
December 18, 2012 - 10:30am

We will give an overview of this system, which has been at the center of recent algorithmic and proof complexity developments. We will give the definitions of the system (as a proof system for polynomial inequalities, and as an SDP-based algorithm), and basic upper and lower bounds for it. In particular we'll explain the recent SOS-proof of the hypercontractive inequality for the noisy hypercube of Barak et al., as well as the degree lower bounds for proving Tseitin and Knapsack tautologies of Grigoriev.

## Delegation for Bounded Space

Ran Raz
Weizmann Institute; Member, School of Mathematics, IAS
December 4, 2012 - 10:30am

## Information Complexity and Exact Communication Bounds

Mark Braverman
Princeton University
December 3, 2012 - 11:15am

In this talk we will discuss information complexity -- a measure of the amount of information Alice and Bob need to exchange to solve a problem over distributed inputs. We will present an information-theoretically optimal protocol for computing the AND of two bits distributed between Alice and Bob. We prove that the information complexity of AND is ~1.4923 bits. We use the optimal protocol and its properties to obtain tight bounds for the Disjointness problem, showing that the randomized communication complexity of Disjointness on n bits is ~0.4827n ± o(n).

## Matching: A New Proof for an Ancient Algorithm

Vijay Vazirani
Georgia Institute of Technology
December 10, 2012 - 11:15am

For all practical purposes, the Micali-Vazirani algorithm, discovered in 1980, is still the most efficient known maximum matching algorithm (for very dense graphs, slight asymptotic improvement can be obtained using fast matrix multiplication). However, this has remained a black box" result for the last 32 years. We hope to change this with the help of a recent paper giving a simpler proof and exposition of the algorithm:
http://arxiv.org/abs/1210.4594

## Combinatorial PCPs with Short Proofs

Or Meir
December 11, 2012 - 10:30am

The PCP theorem (Arora et. al., J. ACM 45(1,3)) asserts the existence of proofs that can be verified by reading a very small part of the proof. Since the discovery of the theorem, there has been a considerable work on improving the theorem in terms of the length of the proofs, culminating in the construction of PCPs of quasi-linear length, by Ben-Sasson and Sudan (SICOMP 38(2)) and Dinur (J. ACM 54(3)).

## Computational Complexity in Mechanism Design

Jing Chen
Massachusetts Institute of Technology; Member, School of Mathematics
November 27, 2012 - 10:30am

Some important mechanisms considered in game theory require solving optimization problems that are computationally hard. Solving these problems approximately may not help, as it may change the players’ rational behavior in the original mechanisms, leading to undesirable outcomes.

## Polynomial Identity Testing of Read-Once Oblivious Algebraic Branching Progress

Michael Forbes
Massachusetts Institute of Technology
November 26, 2012 - 11:15am

Polynomial Identity Testing (PIT) is the problem of identifying whether a given algebraic circuit computes the identically zero polynomial. It is well-known that this problem can be solved with small error probability by testing whether the circuit evaluates to zero on random evaluation points.

## On the AND- and OR-Conjectures: Limits to Efficient Preprocessing

Andrew Drucker
Massachusetts Institute of Technology; Member, School of Mathematics
October 16, 2012 - 10:30am

One of the major insights of the fixed-parameter tractability’’ (FPT) approach to algorithm design is that, for many NP-hard problems, it is possible to efficiently *shrink* instances which have some underlying simplicity.

## A Multi-Prover Interactive proof for NEXP Sound Against Entangled Provers

Tsuyoshi Ito
NEC Laboratories America, Inc.
October 15, 2012 - 11:15am

We prove a strong limitation on the ability of entangled provers to collude in a multiplayer game. Our main result is the first nontrivial lower bound on the class MIP* of languages having multi-prover interactive proofs with entangled provers; namely MIP* contains NEXP, the class of languages decidable in non-deterministic exponential time.