Rutgers University Counting classes and arithmetic circuits

This survey talk presents the motivation for studying arithmetic circuits in a particular framework that highlights the connection between arithmetic circuits and various Boolean complexity classes such as #P, #L, #NC^1, and #AC^0. Many of the most basic questions in this framework have only recently been resolved. I will survey the progress that has been made, and point out areas where further progress may be expected.

University of California, Berkeley Non-closure properties of #AC0

Abstract: The talk will continue the previous two talks by Eric Allender and Samir Datta. It will focus on non-closure properties of #AC0 and GapAC0. In particular, non-closure of #AC0 and GapAC0 under division by p where p is not a power of 2 an non-closure of #AC0 under division by 2 will be shown.

Harvard University

On Arithmetic Branching Programs

The power of basic algebraic operations is a fundamental question. For example, if we can efficiently compute the rank of a matrix then we can efficiently check if the rows of the matrix are dependent. Can we efficiently compute the rank of a matrix using an oracle for dependency? Since both computations can be performed in polynomial time, this question should be addressed in weaker models of computation. In this work we study algebraic models which supply an arena to study such questions. We focus on arithmetic branching programs which are an algebraic model of computation generalizing modular branching programs. We show that, up to a polynomial factor in size, arithmetic branching programs are equivalent to complements of dependency programs, a model introduced by Pudlak and Sgall. Using this equivalence we prove that dependency programs are closed under conjunction over every field, answering an open problem of Pudlak and Sgall. Furthermore, we show that span programs, an algebraic model of computation introduced by Karchmer and Wigderson, are at least as strong as arithmetic programs; every arithmetic program can be simulated by a span program of size not more than twice the size of the arithmetic program. Using the above results we give a new proof that NL/poly is contained in L/poly, first proved by Wigderson. Our simulation of NL/poly is more efficient, and it holds for logspace counting classes over every field. This is a joint work with Anna Gal.

Rutgers University

Closure properties of #AC0

Abstract: The talk will be about some of the closure properties of #AC^0 and the related class GapAC^0. Specifically, it will focus on the closure of #AC^0 under the "choose k" operation (a.k.a. binomial coefficient with base k) for some constant k and the closure of GapAC^0 under the "div 2" operation.

Eotvos University and the University of Chicago

On circuits with modular gates

Modular gates are known to be immune from the random restriction techniques of Ajtai; Furst, Saxe, Sipser; and Yao and Hastad. By our present knowledge, we cannot rule out the possibility that depth-2, linear size circuits, with MOD 6 gates only, compute an NP-hard function. We will demonstrate a random clustering technique which is capable to prove generalizations of several known modular circuit lower bounds of Barrington, Straubing, Therien; Krause and Pudlak; and others, characterizing symmetric functions computable by small (MOD_p, AND_t, MOD_m) circuits. Applying a degree-decreasing technique together with random restriction methods for the AND gates at the bottom level, we also prove a hard special case of the Constant Degree Hypothesis of Barrington, Straubing, Therien, and some other related lower bounds for certain (MOD_p, MOD_m, AND) circuits. We also point out the connection between a MOD 6 circuit problem and a method of explicit Ramsey-graph constructions. (Joint work with Gabor Tardos)

Algebraic circuits and polynomial replacement systems

This paper addresses the problems of counting proof trees (as introduced by Venkateswaran and Tompa) and counting proof circuits, a related but seemingly more natural question. These problems lead to a common generalization of straight-line programs which we call polynomial replacement systems. We suggest a classification of these systems and we consider the complexity of relevant computational problems. This is work in progress, joint with Heribert Vollmer and Klaus Wagner.

Algebraic proof degrees and permutation modules

The talk will report progress in studying the degree of algebraic proofs of membership in polynomial ideals that are uniformly generated by a symmetric closure operation. In particular, we report results on natural, but nontraditional questions about uniformly generated submodules of permutation modules. These questions fall into 3 types: dimension, decomposition and equivalence. (This is joint work with Soren Riis).

The number of functions defined by formulae of a given size

Consider formulas constructed from propositional variables and negated variables using a total of L binary AND and OR connectives. Let B(n,L) denote the number of distinct Boolean functions of a given collection of n variables, which can be defined by such formulas. Since a given function may be defined by many different formulas, a challenging question is: What exactly is B(n,L)? Joint work with Petr Savicky has provided a reasonably good estimate for B(n,L) which holds over a large range of values of L. This study was initially motivated by the problem of comparing the computational ability of polynomial size circuits with that of polynomial size formulas. The talk will concentrate on the ideas, including generating series methods, which underly the estimate. In the process an interesting constant, which seems to have been first noticed by the 19th century logician Ernst Schroder, will make an appearance. One can also ask analogous questions for algebraic formulas constructed using L binary + and . operations. Many of the techniques apply there too.