•  
    • Ariel Gabizon
    • (Technion - Israel Institute of Technology, Haifa)
    • Interactive Oracle Proofs
    • Abstract:
    • We investigate the Interactive Oracle Proof (IOP) model that generalizes both Probabilistically Checkable Proofs  (PCPs) and classical Interactive Proofs (IPs). An IOP is an interactive protocol where the prover sends long ``oracles'' as messages, of which the verifier only reads a small number of locations. The main justification for the model is that, similarly to PCPs, an IOP can be compiled into a short computationally sound proof whose length depends almost solely on the number of bits actually read by the verifier. We show this added interaction is beneficial. For instance, we obtain - a perfect Zero-Knowledge IOP for #P languages, whereas for standard IPs only computational Zero-Knowledge is known. - A linear proof size IOP for circuit satisfiability with constant verifier query complexity, whereas for PCPs only quasilinear proof size is known.
    • 02.12.16   13:30
    • Dmitry Gavinsky
    • (IM)
    • Communication complexity of syntactically-guaranteed intersection search
    • Abstract:
    • We define a new 2-party version of the (unstructured) intersection-search problem, where the input comes from certain bipartite product distribution, but at the same time every possible pair of input subsets share at least one element. In other words, the existence of a target element is guaranteed syntactically for every possible instance of the problem, and thus its complexity analysis cannot be based on the hardness of "recognising" disjoint pairs. The known methods for proving communicational hardness of unstructured search that we are aware of can be viewed as arguing the discrepancy of one form or another with respect to the disjointness predicate, and therefore these methods are not directly applicable to our problem (where such predicate is always a contradiction). To analyse the complexity of the proposed problem, we investigate the global "rectangular structure" of a communication protocol and identify such properties of large rectangles that make it impossible to partition the input matrix into a small number of even "nearly-monochromatic" rectangles, in spite of the fact that it can be covered by very few "perfectly-monochromatic" ones. Besides being able to capture the complexity of our communication problem, this technique provides new insight into the "origin of hardness" of other well-known "search-like" problems, like set disjointness.
    • 18.11.16   13:30
    • Pavel Pudlák
    • (IM)
    • On monotone real circuits
    • Abstract:
    • We will prove that every monotone real circuit can be efficiently simulated by a circuit that only uses additions and unary monotone functions.
    • 11.11.16   13:30
    • Jan Hladký
    • (Inst. of Math., CAS)
    • Matchings in graphons
    • Abstract:
    • Tools that emerged with the theory of dense graph limits (a.k.a. graphons) have been immensely useful in connection with those parts of extremal graph theory, random graphs, property testing and others that deal with relations between subgraph density. However, these fields are much richer and it is natural to seek limit counterparts to other classical concepts. We introduce a counterpart to the notion of vertex disjoint tilings by copy of a fixed graph F to the setting of graphons. The case F=K_2 gives the notion of matchings in graphons. We give a transference statement that allows us to switch between the finite and limit notion, and derive several favorable properties, including the LP-duality counterpart to the classical relation between the fractional vertex covers and fractional matchings/tilings. This seems to be the first version of the LP duality which works in the setting of functional analysis (as opposed to finite-dimensional vector spaces).  This theory has applications in random graphs, extremal graph theory and property testing, and I hope to have time to present some of these. The talk will be self-contained; no previous knowledge of graph limits is needed. Based on joint work with Ping Hu and Diana Piguet, and with Martin Dolezal.
    • 29.04.16   13:30
    • Mateus de Oliveira Oliveira
    • (Mathematical Institute, CAV)
    • On the Satisfiability of Smooth Pictures
    • Abstract:
    • A picture is a matrix whose entries are drawn from some finite set of symbols. Let $\pi:\Sigma\rightarrow \Gamma$ be a function between finite sets of symbols and $V,H\subseteq \Sigma\times \Gamma$ be binary relations over $\Gamma$. Given a picture $N$ over $\Gamma$ the picture satisfiability problem consists in determining whether there exists a picture $M$ over $\Sigma$ such that $\pi(M)=N$, and such that the vertical and horizontal constraints imposed by $V$ and $H$ respectively are satisfied. This problem can be easily shown to be NP-complete. In this work we introduce the notion of $s$-smooth picture. Our main result states the satisfiability problem for $s$-smooth pictures can be solved in time polynomial on $s$ and on the size of the input picture. With each picture $N$, one can naturally associate a CNF formula $F(N)$ which is satisfiable if and only if $N$ is satisfiable. In our second result, we define an infinite family of unsatisfiable pictures which intuitively encodes the pigeonhole principle. We show that this family of pictures is polynomially smooth. In contrast we show that the formulas which naturally arise from these pictures are hard for bounded-depth Frege proof systems. This shows that there are families of pictures for which our algorithm for the satisfiability for smooth pictures performs exponentially better than pure CDCL based SAT solvers.
    • 15.04.16   13:30
    • Pavel Pudlak
    • (Institute of Mathematics)
    • Computing Boolean functions by linear programs
    • Abstract:
    • We represent Boolean function using linear programs. We focus on monotone Boolean functions, because only for these, there there is a chance to prove lower bounds. Such monotone linear programs are stronger than monotone Boolean circuits, as shown by P. Hrubes. The motivation for this research is to prove exponential lower bounds for a certain proof system based on integer linear programing (Lovasz-Schrijver), which is still an open problem. (Joint work with M. de Oliveira Oliveira)
    • 18.03.16   13:30
    • Raheleh Jalali Keshavarz
    • (MI)
    • Polynomial time algorithm for primality, part II
    • Abstract:
    • We will give a presentation of the AKS polynomial time algorithm for primality.
    • 15.01.16   13:30
    • Raheleh Jalali Keshavarz
    • Polynomial time algorithm for primality
    • Abstract:
    • We will give a presentation of the AKS polynomial time algorithm for primality.
    • 08.01.16   13:30

    Michal Koucky, Pavel Pudlak
    organizers

  •