## Předchozí program semináře [Previous program]

26. 5. 2009(úterý [Tuesday],14:30, MÚ Žitná 25, posluchárna v přízemí zadní budovy)

Ronald de Wolf: Error-Correcting Data Structures.STACS'09.

(referuje Ondřej Zajíček)

Abstract:We study data structures in the presence of adversarial noise. We want to encode a given object in a succinct data structure that enables us to efficiently answer specific queries about the object, even if the data structure has been corrupted by a constant fraction of errors. This new model is the common generalization of (static) data structures and locally decodable error-correcting codes. The main issue is the tradeoff between the space used by the data structure and the time (number of probes) needed to answer a query about the encoded object. We prove a number of upper and lower bounds on various natural error-correcting data structure problems. In particular, we show that the optimal length of error-correcting data structures for the Membership problem (where we want to store subsets of size s from a universe of size n) is closely related to the optimal length of locally decodable codes for s-bit strings.

12. 5. 2009(úterý [Tuesday],14:30, MÚ Žitná 25, posluchárna v přízemí zadní budovy)

E. Mossel, R. O'Donnell, and R. Servedio: Learning functions of k relevant variables.(referuje Michal Koucky)

Abstract:We consider a fundamental problem in computational learning theory: learning an arbitrary Boolean function which depends on an unknown set of $k$ out of $n$ Boolean variables. We give an algorithm for learning such functions from uniform random examples which runs in time roughly $(n^k)^{{\frac \omega {\omega + 1}}},$ where $\omega < 2.376$ is the matrix multiplication exponent. We thus obtain the first polynomial factor improvement on the naive $n^k$ time bound which can be achieved via exhaustive search. Our algorithm and analysis exploit new structural properties of Boolean functions.

5. 5. 2009(úterý [Tuesday],14:30, MÚ Žitná 25, posluchárna v přízemí zadní budovy)

Benjamin Rossman:On the Constant-Depth Complexity of k-Clique

(referuje Phuong Nguyen)

Abstract:I will present a recent paper by Rossman showing a lower bound w(n^k/4) for constant-depth circuits that compute k-CLIQUE, for every fixed constant k. This is only a polynomial lower bound, but it doesn't depend on the depth of the circuits. The result implies that the variable fragments of first order logic (FO) on ordered graphs form a strict hierarchy, thus resolving a long standing problem in Finite Model Theory.

Abstract:We study theit static membership problem:^{ }Given a setSof at mostnkeys drawn^{ }from a universeUof sizem, store it so^{ }that queries of the form "IsuinS?" can^{ }be answered by making few accesses to the memory. We^{ }study schemes for this problem that use space close to^{ }the information theoretic lower bound of $\Omega(n\log(\frac{m}{n}))$ bits and yet^{ }answer queries by reading a small number of bits of^{ }the memory.^{ }We show that, for $\epsilon > 0$, there is

^{ }a scheme that stores $O(\frac{n}{\epsilon^2}\log m)$ bits and answers membership^{ }queries using a randomized algorithm that reads just one bit^{ }of memory and errs with probability at most $\epsilon$. We^{ }consider schemes that make no error for queries inS^{ }but are allowed to err with probability at most $\epsilon$^{ }for queries not inS. We show that there exist^{ }such schemes that store $O((\frac{n}{\epsilon})^2 \log m)$ bits and answer^{ }queries using just one bitprobe. If multiple probes are allowed,^{ }then the number of bits stored can be reduced to^{ }$O(n^{1+\delta}\log m)$ for any $\delta > 0$. The schemes mentioned^{ }above are based on probabilistic constructions of set systems with^{ }small intersections.^{ }We show lower bounds that come close to our

We also consider deterministic schemes for the static^{ }upper bounds (for a large range ofnand $\epsilon$):^{ }Schemes that answer queries with just one bitprobe and error^{ }probability $\epsilon$ must use $\Omega(\frac{n}{\epsilon\log(1/\epsilon)} \log m)$ bits of storage;^{ }if the error is restricted to queries not inS,^{ }then the scheme must use $\Omega(\frac{n^2}{\epsilon^2 \log (n/\epsilon)}\log m)$ bits^{ }of storage.^{ }^{ }membership problem and show tradeoffs between space and the number^{ }of probes.

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.

(referuje Pavel Pudlák)

Abstract:A basic fact in linear algebra is that the image of the curve f(x)=(x^{1},x^{2},x^{3},...,x^{m}), say over C, is not contained in any m-1 dimensional affine subspace of C^{m}. In other words, the image of f is not contained in the image of any polynomial-mapping Γ:C^{m-1}→ C^{m}of degree~1 (that is, an affine mapping). Can one give an explicit example for a polynomial curve f:C → C^{m}, such that, the image of f is not contained in the image of any polynomial-mapping Γ:C^{m-1}→ C^{m}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:F^{n}→ F^{m}is(s,r)-elusive, if for every polynomial-mapping Γ:F^{s}→ F^{m}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:F^{n}→ F^{n2}, of degree O(r), that is (s,r)-elusive for s = n^{1+Ω(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 ≥ n^{1+Ω(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 ≥ n^{1+Ω(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.

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.