Computational Complexity

Publications

Teaching

Workshops

# 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:10Opening remarks
10:10 - 11:10Meena MahajanThe quest for VP-completeness.
11:10 - 11:40Coffee Break
11:40 - 12:40Chris UmansApproaches to bounding the exponent of matrix multiplication.
12:40 - 14:00Break
14:00 - 17:00Discussion session
17:00 - Welcome Reception

Tuesday, March 25
10:00 - 11:00Peter Bro MiltersenReal algebraic geometry in computational complexity.
11:00 - 11:30Coffee Break
11:30 - 12:30Michael SagraloffNear-optimal Algorithms for Computing Real Roots of a Polynomial
12:30 - 14:00Break
14:00 - 17:00Contributed TalksAnkit 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:00Kristoffer Arnsfelt HansenCircuit Complexity of Properties of Graphs with Constant Planar Cutwidth
11:00 - 11:30Coffee Break
11:30 - 12:30Thomas ThieraufCounting the number of perfect matchings in $K_5$-free graphs.
12:30 - 14:00Break
14:00 - 17:00Discussion Session

Thursday, March 27
10:00 - 11:00Pascal KoiranA $\tau$-conjecture for Newton polygons.
11:00 - 11:30Coffee Break
11:30 - 12:30Nitin SaxenaTowards hitting-sets for multilinear depth-3 circuits
12:30 - 14:00Break
14:00 - 17:00Discussion Session
19:00 - Workshop Dinner

Friday, March 28
10:00 - 11:00Neeraj KayalLower Bounds for Homogeneous Low Depth Formulas.
11:00 - 11:30Coffee Break
11:30 - 12:30V ArvindLower bounds for multiplicative and linear circuits in noncommutative domains
12:30 - 12:35Closing 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)