# WACT 2014 - Program

Rooms:

Invited & contributed talks: Building E2.1 (Bioinformatics) Room 001

Welcome Reception: Building E1.1 (CS, old building), Room 407

Informal Sessions: Building E1.3 (CS, new building), Rooms 107

Workshop dinner: Cafe am Schloss

Monday, March 24 | ||
---|---|---|

10:00 - 10:10 | Opening remarks | |

10:10 - 11:10 | Meena Mahajan | The quest for VP-completeness. |

11:10 - 11:40 | Coffee Break | |

11:40 - 12:40 | Chris Umans | Approaches to bounding the exponent of matrix multiplication. |

12:40 - 14:00 | Break | |

14:00 - 17:00 | Discussion session | |

17:00 - | Welcome Reception |

Tuesday, March 25 | ||
---|---|---|

10:00 - 11:00 | Peter Bro Miltersen | Real algebraic geometry in computational complexity. |

11:00 - 11:30 | Coffee Break | |

11:30 - 12:30 | Michael Sagraloff | Near-optimal Algorithms for Computing Real Roots of a Polynomial |

12:30 - 14:00 | Break | |

14:00 - 17:00 | Contributed Talks | Ankit Gupta: Approaching the chasm at depth four Michael Forbes: Hitting Sets for Multilinear Read-Once Algebraic Branching Programs, in any Order |

Wednesday, March 26 | ||
---|---|---|

10:00 - 11:00 | Kristoffer Arnsfelt Hansen | Circuit Complexity of Properties of Graphs with Constant Planar Cutwidth |

11:00 - 11:30 | Coffee Break | |

11:30 - 12:30 | Thomas Thierauf | Counting the number of perfect matchings in $K_5$-free graphs. |

12:30 - 14:00 | Break | |

14:00 - 17:00 | Discussion Session |

Thursday, March 27 | ||
---|---|---|

10:00 - 11:00 | Pascal Koiran | A $\tau$-conjecture for Newton polygons. |

11:00 - 11:30 | Coffee Break | |

11:30 - 12:30 | Nitin Saxena | Towards hitting-sets for multilinear depth-3 circuits |

12:30 - 14:00 | Break | |

14:00 - 17:00 | Discussion Session | |

19:00 - | Workshop Dinner |

Friday, March 28 | ||
---|---|---|

10:00 - 11:00 | Neeraj Kayal | Lower Bounds for Homogeneous Low Depth Formulas. |

11:00 - 11:30 | Coffee Break | |

11:30 - 12:30 | V Arvind | Lower bounds for multiplicative and linear circuits in noncommutative domains |

12:30 - 12:35 | Closing remarks |

### Abstracts

#### Meena Mahajan, IMSc Chennai

__The quest for VP-completeness__

Most complexity classes have several "natural" complete problems, and this is often taken as evidence of the "reasonableness" of the class itself. There is a distressing paucity of polynomial families complete for the class VP. This talk describes the quest for natural complete families for VP.

#### Chris Umans, California Institute of Technology

__Approaches to bounding the exponent of matrix multiplication__

We begin by describing the ideas behind the state-of-the-art bounds on omega, the exponent of matrix multiplication.

We then present the "group-theoretic" approach of Cohn and Umans as an alternative to these methods, and we generalize this approach from group algebras to general algebras. We identify adjacency algebras of coherent configurations as a promising family of algebras in the generalized framework. We prove a closure property involving symmetric powers of adjacency algebras, which enables us to prove nontrivial bounds on $\omega$ using commutative coherent configurations, and suggests that commutative coherent configurations may be sufficient to prove $\omega = 2$.

Along the way, we introduce a relaxation of the notion of tensor rank, called s-rank, and show that upper bounds on the s-rank of the matrix multiplication tensor imply upper bounds on the ordinary rank. In particular, if the "s-rank exponent of matrix multiplication" equals 2, then the (ordinary) exponent of matrix multiplication, $\omega$, equals 2.

Finally, we will mention connections between several conjectures implying $\omega=2$, and variants of the classical sunflower conjecture of Erdos and Rado.

No special background is assumed.

Based on joint works with Noga Alon, Henry Cohn, Bobby Kleinberg, Amir Shpilka, and Balazs Szegedy.

#### Peter Bro Miltersen, Aarhus University

__Real algebraic geometry in structural complexity theory__

Real algebraic geometry is the study of semi-algebraic sets; i.e., sets that are unions of solution sets to systems of multivariate polynomial equations and inequalities over the real numbers. We present some recent applications of theorems of real algebraic geometry to (structural) computational complexity theory.

#### Michael Sagraloff, Max Planck Institute for Computer Science

__Near-optimal Algorithms for Computing Real Roots of a Polynomial__

In theory, the best algorithm known for approximating all complex roots of a polynomial is based on an almost optimal method for approximate polynomial factorization, introduced by V. Pan in 2002. Pan's factorization algorithm goes back to the splitting circle method from A. Schoenhage in 1982. The main drawback of Pan's method is that it is quite involved and that all roots have to be computed at the same time. For the important special case, where only the real roots have to be computed, much simpler methods are used in practice; however, they considerably lag behind Pan's method with respect to complexity.

In the first part of my talk, I will present a variant of the Descartes method, denoted ANEWDSC, that computes isolating intervals for the real roots of any real square-free polynomial, given by an oracle that provides arbitrary good approximations of the polynomial's coefficients. The algorithm can also be used to refine the isolating intervals to an arbitrary small size. The bit complexity of ANEWDSC matches the complexity of Pan's method and, in particular, it achieves near optimal complexity for computing arbitrary good approximations of all real roots. ANEWDSC derives its speed from the combination of the Descartes method with Newton iteration and approximate arithmetic. By comparison, the algorithm is considerably simpler than Pan's method, and it can be used to compute the roots in a given interval only.

In the second part of my talk, I will concentrate on sparse polynomials, that is, polynomials with a small number of non-vanishing coefficients. Using a subroutine from ANEWDSC, I will show how to isolate the real roots of a sparse integer polynomial with a number of arithmetic operations over the rationals that is polynomial in the input size of the sparse representation of the input polynomial. The bit complexity of the algorithm is by one magnitude better than that of ANEWDSC and Pan's method. Considering a family of Mignotte-like polynomials, one can show that the algorithm is optimal up to logarithmic factors in the degree of the polynomial and the bitsize of the coefficients.

#### Kristoffer Arnsfelt Hansen, Arhus University

__Circuit Complexity of Properties of Graphs with Constant Planar Cutwidth__

We study the complexity of several of the classical graph decision problems in the setting of bounded cutwidth and how imposing planarity affects the complexity. We show that for 2-coloring, for bipartite perfect matching, and for several variants of disjoint paths the straightforward NC^1 upper bound may be improved to AC^0[2], ACC^0, and AC^0 respectively for bounded planar cutwidth graphs. On the other hand we show that 3-coloring and Hamilton cycle remain hard for NC^1, analogous to the NP-completeness for general planar graphs. We also show that 2-coloring and (non-bipartite) perfect matching are hard for certain subclasses of AC^0[2]. In particular this shows that our bounds for 2-coloring are quite close.

#### Thomas Thierauf, Aalen University

__Counting the Number of Perfect Matchings in $K_5$-free Graphs__

We show that the number of perfect matchings in $K_5$-free graphs can be computed in polynomial time.

#### Pascal Koiran, ENS Lyon

__A $\tau$-conjecture for Newton polygons__

One can associate to any bivariate polynomial $P(X,Y)$ its Newton polygon. This is the convex hull of the points $(i,j)$ such that the monomial $X^i Y^j$ appears in $P$ with a nonzero coefficient. We conjecture that when $P$ is expressed as a sum of products of sparse polynomials, the number of edges of its Newton polygon is polynomially bounded in the size of such an expression. We show that this ``$\tau$-conjecture for Newton polygons,'' even in a weak form, implies that the permanent polynomial is not computable by polynomial size arithmetic circuits. We make the same observation for a weak version of an earlier ``real $\tau$-conjecture.'' Finally, we make some progress toward the $\tau$-conjecture for Newton polygons using recent results from combinatorial geometry.

This talk is based on joint work with Natacha Portier, Sébastien Tavenas and Stéphan Thomassé. I will present our results and conjectures, starting from the very basic properties of Newton polygons (and in particular the role of Minkowski sum).

#### Nitin Saxena, IIT Kanpur

__Towards hitting-sets for multilinear depth-3 circuits__

The depth-3 circuit model has emerged as a key step in understanding general circuits. In this talk we will focus on the question of testing whether a given *multilinear* depth-3 circuit is zero. In particular, we give nontrivial constructions of hitting-sets for *low-distance* multilinear depth-3. The main phenomena here is "low-support rank concentration"; naturally, we conjecture that it can be attained for general depth-3 circuits as well.

#### Neeraj Kayal, Microsoft Research India

__Lower Bounds for Homogeneous Low Depth Formulas__

A sequence of works on depth reduction for arithmetic circuits has shown that good enough lower bounds for low depth arithmetic formulas (of depth three or four) would yield superpolynomial lower bounds for general arithmetic circuits. In this talk, we will present some lower bounds for homogeneous depth four arithmetic formulas.

#### V Arvind, IMSc Chennai

__Lower bounds for multiplicative and linear circuits in noncommutative domains__

We will present some lower bounds for the size of multiplicative circuits computing multi-output functions in some noncommutative domains. Relatedly, we will also discuss lower bound questions for linear circuits where the goal is to compute a linear transform Mx, but M is a matrix with entries from a noncommutative ring. (This is joint work with S. Raja and A.V. Sreejith)

### Contributed Talks

#### Michael Forbes, Massachusetts Institute of Technology

__Hitting Sets for Multilinear Read-Once Algebraic Branching Programs, in any Order__

It is an important open question whether we can derandomize small space computation, that is, whether RL equals L. One version of this question is to construct pseudorandom generators for read-once oblivious branching programs. There are well-known results in this area (due to Nisan, and Impagliazzo-Nisan-Wigderson), but they fail to achieve optimal seed-length. Further, it has been observed that these pseudorandom generators depend strongly on the "order" of the "reads" of the branching program. When this order is allowed to vary, only much weaker results are known.

In this work, we consider an "algebraic" version of this question. That is, we seek to fool read-once algebraic branching programs, regardless of the variable order. By rephrasing and improving the techniques of Agrawal-Saha-Saxena, we are able to construct hitting sets for multilinear polynomials in this unknown-order model that have polylogarithmic "seed-length". This constitutes the first quasipolynomial-time, deterministic, black-box polynomial identity testing (PIT) algorithm for this model.

Joint work with Ramprasad Saptharishi (MSR India) and Amir Shpilka (Technion).

#### Ankit Gupta, Chennai Mathematical Institute

__Approaching the chasm at depth four__

Agrawal-Vinay'08 and Koiran'12 have recently shown that an $\exp(n^{1/2 + \epsilon})$ lower bound for depth four homogeneous circuits computing the permanent with bottom layer of x gates having fanin bounded by $n^{1/2}$ translates to $\exp(n^{\epsilon})$ lower bound for general arithmetic circuits computing the permanent. Motivated by this, we examine the complexity of computing the permanent via such restricted homogeneous depth four circuits.

We show here that any homogeneous depth four arithmetic circuit with bottom fanin bounded by $n^{1/2}$ computing the permanent must be of size $\exp(\Omega(n^{1/2}))$.

(joint work with Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi)