•  
    • Pavel Pudlak
    • On the power of linear queries
    • Abstract:
    • We will consider the problem to distinguish strings of 0s and 1s from strings of 0s,1s and 2s. We will prove a lower bound on the number of linear queries in Z_3 needed to solve the problem.
    • 12.12.14   13:30
    • Igor Shinkar
    • (Weizmann Institute)
    • Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball
    • Abstract:
    • We construct a bi-Lipschitz bijection from the Boolean cube to the Hamming ball of equal volume. More precisely, we show that for all even n there exists an explicit bijection f from the n-dimensional Boolean cube to the Hamming ball of equal volume embedded in (n+1)-dimensional Boolean cube, such that for all x and y it holds that distance(x,y) / 5 leq distance(f(x),f(y)) leq 4 distance(x,y) , where distance(,) denotes the Hamming distance. In particular, this implies that the Hamming ball is bi-Lipschitz transitive. This result gives a strong negative answer to an open problem of Lovett and Viola (CC 2012), who raised the question in the context of sampling distributions in low-level complexity classes. The conceptual implication is that the problem of proving lower bounds in the context of sampling distributions will require some new ideas beyond the sensitivity-based structural results of Boppana (IPL 97). We also study the mapping f further and show that it (and its inverse) are computable in DLOGTIME-uniform TC0, but not in AC0. Moreover, we prove that f is "approximately local" in the sense that all but the last output bit of f are essentially determined by a single input bit. Joint work with Itai Benjamini and Gil Cohen.
    • 12.05.14   10:30
    • Pavel Pudlak
    • title: On a new paper of J. Grochow and T. Pitassi
    • Abstract:
    • In their recent paper " Circuit Complexity, Proof Complexity and Polynomial Identity Testing" (in ECCC) Grochow and Pitassi proved a nuber of interesting results about an algebraic proof system IPS. I will give a presentation of the main result that says that lower bounds on the size of proofs of Boolean tautologies in IPS imply lower bounds on on the size of arithmetic circuits computing functions in VNP; so a superpolynomial lower bound would imply VPneq VNP.
    • 28.04.14   10:30
    • Bruno Bauwens
    • (Universite de Lorraine, Nancy)
    • Short lists containing short descriptions in short time
    • Abstract:
    • Given a machine U, a c-short program for x is a string p such that U(p)=x and the length of p is bounded by c + (the length of a shortest program for x). Generating a short program for a string is a fundamental problem for example in learning theory. We show that for any universal machine, it is possible to compute in polynomial time on input x a list of polynomial size guaranteed to contain a O(log |x|)-short program for x. This result has been improved to obtain lists containing O(1)-short programs by Teutsch and by Zimand. If we consider computable lists rather than polynomial time computable lists, we obtain tight bounds for the list sizes: * There exist computable functions that map every x to a list of size O(|x|^2) containing a O(1)-short program for x. * Every computable function generating lists containing c-short programs for all x, computes infinitely often lists of size at least Omega(|x|^2/c^2). The quadratic lower bound can be beaten using probabilistic computation: there exist a randomized algorithm that on input x computes a list of size |x| that with probability 1-delta contains a O(log |x|/delta)-short program for x. Moreover, there is a randomized polynomial time algorithm that on input x computes in polynomial time such a list containing an Oleft( (log |x|/delta)^2 right)-short program for x. This task is a rather unexpected example of a task that is not computably solvable but solvable in probabilistic polynomial time. Joint work with A. Makhlin, N. Vereshchagin, and M. Zimand
    • 07.04.14   10:30

    Michal Koucky, Pavel Pudlak
    organizers

  •