|
|
Close Help | ||||||||||||||
Předchozí program semináře [Previous program]
7. 4., 14. 4. 2009 (úterý [Tuesday], 14:30, MÚ Žitná 25, posluchárna v přízemí zadní budovy)
Ran Raz: Elusive Functions and Lower Bounds for Arithmetic Circuits. STOC 2008.
Abstract: A basic fact in linear algebra is that the image of the curve f(x)=(x1,x2,x3,...,xm), say over C, is not contained in any m-1 dimensional affine subspace of Cm. In other words, the image of f is not contained in the image of any polynomial-mapping Γ:Cm-1 → Cm of degree~1 (that is, an affine mapping). Can one give an explicit example for a polynomial curve f:C → Cm, such that, the image of f is not contained in the image of any polynomial-mapping Γ:Cm-1 → Cm of degree 2? In this paper, we show that problems of this type are closely related to proving lower bounds for the size of general arithmetic circuits. For example, any explicit f as above (with the right notion of explicitness) implies super-polynomial lower bounds for computing the permanent over C. More generally, we say that a polynomial-mapping f:Fn → Fm is (s,r)-elusive, if for every polynomial-mapping Γ:Fs → Fm of degree r, Im(f) ⊄ Im(Γ). We show that for many settings of the parameters n,m,s,r, explicit constructions of elusive polynomial-mappings imply strong (up to exponential) lower bounds for general arithmetic circuits. Finally, for every r < log n, we give an explicit example for a polynomial-mapping f:Fn → Fn2, of degree O(r), that is (s,r)-elusive for s = n1+Ω(1/r). We use this to construct for any r, an explicit example for an n-variate polynomial of total-degree O(r), with coefficients in {0,1,}such that, any depth r arithmetic circuit for this polynomial (over any field) is of size ≥ n1+Ω(1/r). In particular, for any constant r, this gives a constant degree polynomial, such that, any depth r arithmetic circuit for this polynomial is of size ≥ n1+Ω(1). Previously, only lower bounds of the type Ω(n • λr (n)), where λr (n) are extremely slowly growing functions (e.g., λ5(n) = log n, and λ7(n) = log* log*n), were known for constant-depth arithmetic circuits for polynomials of constant degree.
(referuje Pavel Pudlák)
31. 3. 2009 (úterý [Tuesday], 14:30, MÚ Žitná 25, posluchárna v přízemí zadní budovy)
Stasys Junka: Representing (0,1)-matrices by depth-2 circuits with arbitrary gates
(referuje Michal Koucký)
Abstract: A boolean circuit represents an n by n (0,1)-matrix A if it correctly computes the linear transformation y = Ax over GF(2) on all n unit vectors. If we only allow linear boolean functions as gates, then some matrices cannot be represented using fewer than O(n^2/ln n) wires. We first show that using non-linear gates one can save a lot of wires: Any matrix can be represented by a depth-2 circuit with O(n ln n) wires using multilinear polynomials over GF(2) of relatively small degree as gates. We then show that this cannot be substantially improved: If any two columns of an n by n (0,1)-matrix differ in at least d rows, then the matrix requires Omega(d ln n/ln ln n) wires in any depth-2 circuit, even if arbitrary boolean functions are allowed as gates.24. 3. 2009 (úterý [Tuesday], 14:30, MÚ Žitná 25, posluchárna v přízemí zadní budovy)
Pavel Pudlák: On convex complexity measures III
(joint work with P. Hrubeš, S. Jukna, and A. Kulikov)
Abstract: I talked about this subject already twice. Now we are preparing the final version so it will be helpful to talk about it again. I will repeat some stuff, but we view the results from a different perspective now and there are some new results not covered in previous talks. I will also mention some observations and problems that will not be in the paper.3. 3. 2009 (úterý [Tuesday], 14:30, MÚ Žitná 25, posluchárna v přízemí zadní budovy)
Ketan Mulmuley: On P vs NP, Geometric Complexity Theory, and the Riemann Hypothesis
(video from Institute for Advanced Study, February 9, 2009, http://video.ias.edu/csdm/pvsnp)
Abstract: This series of three talks will give a nontechnical, high level overview of geometric complexity theory (GCT), which is an approach to the P vs. NP problem via algebraic geometry, representation theory, and the theory of a new class of quantum groups, called nonstandard quantum groups, that arise in this approach. In particular, GCT suggests that the P vs. NP problem in characteristic zero is intimately linked to the Riemann Hypothesis over finite fields. No background in algebraic geometry, representation theory or quantum groups would be assumed.
