WACT 2015 – Program

Rooms:
Invited & contributed talks: Building E2.1 (Bioinformatics) Room 001
Informal Sessions: Building E1.3 (CS, new building), Rooms 014, 015, 016

Workshop dinner: Cafe am Schloss

Monday, March 16

Tuesday, March 17

Wednesday, March 18 (Contributed Talks)

Thursday, March 19

Friday, March 20

Abstracts

Rahul Santhanam, University of Edinburgh
Boolean vs Algebraic
I will survey relationships between Boolean and algebraic circuit complexity, with an emphasis on connections between circuit lower bounds and derandomization in the Boolean and algebraic settings.

Ramprasad Saptharishi, Chennai Mathematical Institute
Depth reduction in arithmetic circuits
The first step in almost all lower bound proofs is to find a good starting model to attack the circuit class of interest. This is normally achieved via a “depth reduction” to obtain a “shallow circuit” of not too large size. For most of the lower bounds in depth-4 circuits, this step is provided by the results of [Agrawal-Vinay] and subsequent strengthening by [Koiran] and [Tavenas]. Other lower bounds, such as the recent non-homogeneous depth-three lower bound by [Kayal-Saha] build on a depth reduction to depth three circuits [Gupta et al.].

In this talk, we shall see an overview of some of these depth reduction results and how they directly influenced lower bounds subsequently. We shall also see a slightly different perspective* of [Tavenas] strengthening of [Agrawal-Vinay] that might have some relevance to attacking homogeneous formulas.

Based on joint work with V Vinay

Ben Lee Volk/Amir Sphilka, Tel Aviv University
Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas
We give subexponential size hitting sets for bounded depth multilinear arithmetic formulas. Using the known relation between black-box PIT and lower bounds we obtain lower bounds for these models.

Our results are combinatorial in nature and rely on reducing the underlying formula, first to a depth-4 formula, and then to a read-once algebraic branching program (from depth-3 formulas we go straight to read-once algebraic branching programs).

Based on a joint work with Rafael Mendes de Oliveira and Ben Lee Volk

Michael Forbes, Institute for Advanced Study
Polynomial Identity Testing via Shifted Partial Derivatives
In this talk we consider the polynomial identity testing (PIT) problem: given an algebraic computation which computes a low-degree multivariate polynomial f, is f identically zero as a polynomial? This problem is of fundamental importance in computer algebra and also captures problems such as computing matchings in graphs. While this problem has a simple randomized algorithm (test whether f is zero at a random evaluation point), it is an active line of pseudorandomness research to develop efficient deterministic PIT algorithms for interesting models of algebraic computation.

A related problem is to develop lower bounds: given a model of algebraic computation, find an explicit polynomial f which is expensive to compute in this model. As efficient deterministic PIT algorithms for a model of algebraic computation can be shown to imply lower bounds for that model, developing lower bounds is often a precursor to developing such PIT algorithms. Recently, a new lower bounds technique called “the method of shifted partial derivatives” has been introduced and has been used to obtain a number of new lower bounds for various models, however its potential for yielding PIT algorithms is largely unexplored.

In this work, we use give the first usage of the method of shifted partial derivatives to develop PIT algorithms. In particular, we will highlight the relation to divisibility testing questions, that is, testing whether a given multivariate polynomial f divides another given multivariate polynomial g.

Ignacio Garcia Marco, ENS Lyon
Long-Concavity and Lower bounds for arithmetic circuits
Let f=∑di=0aiXi∈ℝ+[X] be a polynomial satisfying the log-concavity condition a2i>τai−1ai+1 for every i∈{1,…,d−1}, where τ>0. Whenever f can be written under the form f=∑ki=1∏mj=1fi,j where the polynomials fi,j have at most t monomials, it is clear that d≤ktm. Assuming that the fi,j have only non-negative coefficients, we improve this degree bound.

This investigation has a complexity-theoretic motivation: we show that a suitable strengthening of our results would imply a separation of the algebraic complexity classes VP and VNP. As they currently stand, these results are strong enough to provide a new example of a family of polynomials in VNP which cannot be computed by monotone arithmetic circuits of polynomial size.

This is a joint work with Pascal Koiran and Sébastien Tavenas.

Daniel König, Universität Siegen
Polynomial identity testing in coRNC for powerful skew circuits
Polynomial identity testing (PIT) is the question whether a given arithmetic circuit over some Ring R evaluates to the zero polynomial. It is known that this problem belongs to coRP for the ring of integers (as well as many other rings). It is a famous open problem whether there is a deterministic polynomial time algorithm for PIT, and this question is tightly related to lower bounds. We introduce so called powerful skew arithmetic circuits that generalize skew circuits in the following way: A powerful skew arithmetic circuit is a circuit, where for every multiplication gate one of the two input gates is labelled with a monomial axa11,…,xakk,wherea, a_1,\dots,a_k$ are binary coded numbers. We show that PIT for powerful skew arithmetic circuits can be solved in coRNC. Furthermore we reduce two other problems to PIT for powerful skew arithmetic circuits: (i) the problem whether two strings (or even higher dimensional pictures) that are given by straight-line programs (context-free grammars that produce a single string (picture)) are identical, and (ii) the circuit evaluation problem for wreath products of f.g. abelian groups. Hence, these two problems belong to coRNC as well. For problem (i) polynomial time algorithms for the string case are known, but no NC- algorithm is known; in the higher dimensional case the best upper bound so far was coRP due to Berman, Karpinski, Larmore, Plandowski, and Rytter.

Joing work with Markus Lohrey

Neeraj Kayal, Microsoft Research India
Lower Bounds for some circuit classes and a generalized complexity measure.
It is known that strong enough lower bounds for certain circuit subclasses (such as homogeneous depth four circuits or even depth three circuits) would yield lower bounds for arbitrary arithmetic circuits. We survey some lower bounds for restricted classes of circuits, emphasizing on the geometric intuition behind the complexity measures used in these lower bounds. We then describe a complexity measure which generalizes most of the known complexity measures and propose potential applications.

Guillaume Malod, University Paris Diderot
Lower bounds for non-commutative skew circuits.
Nisan (STOC 1991) exhibited a polynomial which is computable by linear sized non-commutative circuits but requires exponential sized non-commutative algebraic branching programs. Nisan’s hard polynomial is in fact computable by linear sized skew circuits (skew circuits are circuits where every multiplication gate has the property that all but one of its children is an input variable or a scalar). We prove that any non-commutative skew circuit which computes the square of the polynomial defined by Nisan must have exponential size.

As a further step towards proving exponential lower bounds for general non-commutative circuits, we also extend our techniques to prove an exponential lower bound for a class of circuits which is a restriction of general non-commutative circuits and a generalization of non-commutative skew circuits. As far as we know, this is the strongest model of non-commutative computation for which we have superpolynomial lower bounds.

Joint work with Nutan Limaye and Srikanth Srinivasan.

Chandan Saha, Indian Institute of Science, Bangalore
Multi-k-ic depth three circuit lower bound.
In a multi-k-ic depth three circuit, every variable appears in at most k of the linear polynomials in every product gate of the circuit. This model is a natural generalization of multilinear depth three circuits that allows the formal degree of the circuit to exceed the number of underlying variables (as the formal degree of a multi-k-ic depth three circuit can be kn where n is the number of variables). The problem of proving lower bounds for depth three circuits with high formal degree has gained in importance following a work by Gupta, Kamath, Kayal and Saptharishi (2013) on depth reduction to high formal degree depth three circuits. In the talk, we will show an exponential lower bound for multi-k-ic depth three circuits for any arbitrary constant k.

Based on joint work with Neeraj Kayal.

Pascal Koiran, ENS Lyon
Lower bounds for sums of powers of low degree univariates
We consider the problem of representing a univariate polynomial f(x) as a sum of powers of low degree polynomials. We prove a lower bound of Ω((√d/t) for writing an explicit univariate degree d polynomial f(x) as a sum of powers of degree-t polynomials.

Joint work with Neeraj Kayal, Timothée Pecatte and Chandan Saha.