•  
    • Pavel Pudlak
    • On algorithms for k-SAT
    • Abstract:
    • In 1998 Paturi, Pudlak, Saks and Zane proposed a probabilistic algorithm for k-SAT. The algorithm combines random assignments with resolution. With an improvement of Hertli this algorithm has the best provable upper bound on the time (or probability). An exponential lower bound was proved only recently by Chen, Scheder, Talebanfard and Tang, but it does not match the upper bound. We will explain one approach to proving lower bouns to the PPSZ algorithm.
    • 11.12.15   13:30
    • Mateus de Oliveira Oliveira
    • Size-Treewidth Tradeoffs for Circuits Computing the Element Distinctness Function
    • Abstract:
    • In this work we study the relationship between size and treewidth of circuits computing variants of the element distinctness function. First, we show that for each $n$, any circuit of treewidth $t$ computing the element distinctness function $edfunction:{0,1}^nrightarrow {0,1}$ must have size at least $Omega(frac{n^2}{2^{O(t)} log n})$. This result provides a non-trivial generalization of a super-linear lower bound for the size of boolean formulas (treewidth $1$) due to Nev{c}iporuk. Subsequently, we turn our attention to read-once circuits, which are circuits where each variable labels at most one input vertex. For each $n$, we show that any read-once circuit of treewidth $t$ and size $s$ computing a variant $evenedfunction:{0,1}^nrightarrow {0,1}$ of the element distinctness function must satisfy the inequality $tlog s geq Omega(frac{n}{log n})$. This inequality has three consequences. First it implies that for each $t$, if there exists a read-once circuit of treewidth $t$ computing $evenedfunction$ then this circuit must have size at least $2^{Omega(n/tlog n)}$. Second, it implies that polynomial sized read-once circuits computing $evenedfunction$ must have treewidth $Omega(n/log n)$. This lower bound is at most tight, since there is a circuit of size $O(n^2)$ and treewidth $O(n)$ computing $evenedfunction$. Finally, using a connection between treewidth and the theory of minors, our result implies that any read-once circuit computing $evenedfunction$, whose underlying graph belongs to a minor closed family $mathcal{F}$, must have size at least $Omega(n^{2}/log^{3} n)$. This result generalizes a  super-linear lower bound for the size of read-once planar circuits due to Lipton and Tarjan.
    • 22.05.15   13:30
    • Pavel Pudlak
    • Fully homomorphic encryption
    • Abstract:
    • Fully homomorphic encryption is a type of secure encryption that enables one to delegate computations on data to a party that only has encrypted data. This is perhaps the most interesting concept in theoretical cryptography with potential useful applications. My exposition will be based on Craig Gentry's survey "Computing on the edge of chaos: Structure and randomness in encrypted computations" http://eccc.hpi-web.de/report/2014/106/.
    • 15.05.15   13:30
    • Consider the computational model "CL", where you have O(log n) bits of free memory, and n^O(1) bits of full memory. A CL
    • Quantum Branching Programs. QBPs for Quantum Hashing
    • Abstract:
    • In the talk we present a concept of Quantum Branching Program (for short: quantum BP or just QBP) as a generalization of classical deterministic and stochastic BPs. We present topological lower bound technique for QBP and as a corollary show that $NC^1=QBP_2$ (2005). Here $NC^1$ is a known circuit complexity class and $QBP_2$ is a class of Boolean functions computable by bounded error width 2 QBPs of polynomial size. As an important (practically oriented) application of QBPs, we show that read-once QBPs based on a constant number of qubits are important computational models for presenting quantum cryptographic hash functions (2014-2015). The talk is based on the following papers: 1. Ablayev, F., Gainutdinova, A. and Karpinski, M., Moore, C., and Pollette C.: On the computational power of probabilistic and quantum branching programs of constant width. Information and Computation, 2005. 2. F. Ablayev, A. Vasiliev: Quantum Hashing. arXiv:1310.4922v1 [quant-ph] 2013. 3. F. Ablayev, M. Ablayev: Quantum Hashing via Classical $?$-universal Hashing Constructions. arXiv:1404.1503v2 [quant-ph] 2015.
    • 10.04.15   13:30
    • Bruno Loff
    • Deterministic and non-deterministic algorithms for computing on a full memory
    • Abstract:
    • Consider the computational model "CL", where you have O(log n) bits of free memory, and n^O(1) bits of full memory. A CL algorithm may use the full-memory as it pleases, provided that by the end of its execution, it has returned the memory to its initial state. Previously in the seminar, Michal Koucký talked about our result showing that TC^1 and NL is in CL, implying that there are non-trivial ways of making use of a full memory (neither TC^1 nor NL are known to be in L). More recently, we have been studying NCL - a non-deterministic version of CL. I will give a general introduction to the model in case you didn't see it before, and then go through an interesting adaptation of the Immerman and Szelepcsenyi's result, to show that NCL is closed under complement.
    • 03.04.15   13:30
    • Elazar Goldenberg
    • Embedding edit distance into Hamming distance
    • Abstract:
    • The Hamming and the edit distance are two common notions of measuring distances between pairs of strings x,y lying in the hypercube. The edit distance between x and y, is defined as the minimum number of character insertion, deletion, and bit flips needed for converting x into y. The Hamming distance between x and y is the number of bit flips needed for converting x to y. In this talk I would discuss the question of randomized injective embedding the edit distance into the Hamming distance preserving a small distortion between input edit distance and output Hamming distance. Such an embedding is motivated by several questions in communication complexity. During the talk I will describe the embedding and analyze its performance by connecting it to some question regarding random walk on the integers line.
    • 27.03.15   13:30
    • Jan Hladký
    • Property testing and limits of sparse graphs
    • Abstract:
    • I will show that the formalism of limits of sparse graphs due to Benjamini and Schramm (and implicit in earlier work of Gromov) is essentially equivalent to the theory property testing in the bounded-degree model. This connection is fruitful. In particular, I will show how things can end up if you allow an analyst to design algorithms. The talk will be self-contained.
    • 20.03.15   13:30
    • Mateus de Oliveira Oliveira
    • Width Based Circuit-Size Lower Bounds
    • Abstract:
    • In this work we study the relation between size and treewidth of circuits computing explicit boolean functions. First, for each $n$, we construct a function $f:{0,1}^nrightarrow {0,1}$ such that any circuit of treewidth $t$ computing $f$ must have size at least $Omega(frac{n^2}{2^t * log n})$. Our result provides a non-trivial generalization of a superlinear lower bound for the size of boolean formulas (treewidth $0$) due to Nechiporuk. Subsequently, we turn our attention to read once circuits, which are circuits in which each variable labels at most one input vertex. For each $n$, we construct a function $g:{0,1}^nrightarrow {0,1}$ such that any read-once circuit computing $g$ must have treewidth at least $Omega(n/log n)$. This implies that each read-once circuit computing g, whose underlying graph belongs to a minor closed family $F$, must have size at least $Omega(n^{2} / log n)$. This result generalizes a super-linear lower bound for the size of planar read-once circuits due to Lipton and Tarjan.
    • 13.03.15   13:30

    Michal Koucky, Pavel Pudlak
    organizers

  •