Seminář z výpočetní složitosti

Michal Koucký, Pavel Pudlák

Předchozí program semináře

27. 10. 2011 (středa [Wednesday], 14:30, MÚ Žitná 25)

Pavel Pudlák: Extracting computations from propositional proofs.

Abstract: I will present a new computational model that generalizes boolean circuits. This model characterizes a certain computational problem concerning the proof systems that use DNF's (depth 2 Frege systems). The problem is important mainly for proof complexity, but potentially can also be used to classify the complexity of combinatorial games. There is also a new combinatorial game associated with it.

This model was presented by Neil on the logic seminar, but I will say a little more. I will use my slides from the lecture that I gave in Chennai last month.

1. 12. and 8.12. 2010 (středa [Wednesday], 14:30, MÚ Žitná 25)

Ryan Williams: Non-Uniform ACC Circuit Lower Bounds
(referuje Michal Koucký)

Abstract: The class ACC consists of circuit families with constant depth over unbounded fan-in AND, OR, NOT, and MOD_m gates, where m > 1 is an arbitrary constant. We prove:

  1. NTIME(2^n) does not have polynomial size ACC circuits.
  2. EXP^NP does not have ACC circuits of size 2^{n^o(1)}.
These results finally make progress on some notorious problems in circuit complexity. (It was not known whether EXP^NP had depth-3 polynomial size circuits made out of only MOD_q gates.) The highlevel strategy is to design faster algorithms for the circuit satisfiability problem over ACC circuits, then prove that such algorithms entail the above lower bounds. The algorithm combines known properties of ACC with fast rectangular matrix multiplication, while the second step requires a subtle strengthening of the author's prior work [STOC'10].

10. 11. 2010 (středa [Wednesday], 14:30, MÚ Žitná 25)

Michal Koucký: Computing Error Correcting Codes in Bounded Depth

Abstract: In this talk I will explain some of the recent work we did with A. Gál, K. Hansen, P. Pudlák, E. Viola on computing error-correcting codes by bounded depth circuits.

The work aims to answer the following question: For codes of constant rate and constant relative minimal distance what is the number of wires in constant depth circuits computing the code, i.e., computing the encoding function. We show surprising almost linear bounds.

27. 10. and 3.11. 2010 (středa [Wednesday], 14:30, MÚ Žitná 25)

R.A. Moser, A constructive proof of Lovasz Local Lemma
(referuje Pavel Pudlák)

Abstract: This is a nice new (2008) and constructive proof of the useful lemma.

20. 10. 2010 (středa [Wednesday], 14:30, MÚ Žitná 25)

Kristoffer Arnsfelt Hansen (Aarhus University): Exact threshold functions and Boolean circuits

Abstract: In this talk we will cover exact threshold functions from a number of perspectives. First a brief survey of research on constant depth threshold circuits is given followed by a detailed introduction of exact threshold functions and corresponding pure circuit classes they give rise to. Relationships between threshold circuits and exact threshold counterparts are covered. A major open problem in Boolean circuit complexity is to provide an explicit super-polynomial lower bound for depth two threshold circuits. We identify the class of depth two exact threshold circuits as a natural subclass of these where also no explicit lower bounds are known.

Next exact threshold functions are studied as models of representing Boolean functions, specifically by linear equations and in general degree d polynomials. We give upper and lower bounds on the maximum magnitude (absolute value) of the coefficients required to represent such functions. These bounds are very close and in the linear case in particular they are almost matching. In the process we construct new families of ill-conditioned matrices

Finally is given a short overview of other uses of exact threshold functions in Boolean circuit complexity.

The talk is based on joint work Laci Babai, Vladimir Podolskii and Xiaoming Sun.