•  
    • Ramamohan Paturi
    • (University of California, San Diego, USA)
    • On Extremal Properties of k-CNF: Capturing Threshold Functions
    • Abstract:
    • We consider a basic question on the expressiveness of k-CNF formulas: How well can k-CNF formulas capture threshold functions? Specifically, what is the largest number of assignments (of Hamming weight t) accepted by a k-CNF formula that only accepts assignments of weight at least t? We discuss the following results: We present optimal solutions for t<= n/k. For t > n/k. we formulate a (monotone) version of the problem as an extremal hypergraph problem and show that for t = n ? k, the problem is exactly the Turán problem. For t = ?n with constant ?, we provide a construction and show its optimality for 2-CNF. Optimality of the construction for k > 2 would give improved lower bounds for depth-3 circuits.  
    • 29.04.22   14:00
    • Navid Talebanfard
    • (IM CAS)
    • Towards stability arguments in circuit lower bounds
    • Abstract:
    • Stability theorems in extremal combinatorics generalize uniqueness of extremal instances. For example, it is well-known that triangle-free graphs with many edges structurally resemble the Turan graph, which is the unique triangle-free with maximum number of edges. Does a similar phenomenon hold in circuit complexity? Do small circuits computing a particular function have to have a specific structure? We will show that in some situations regarding depth-3 circuits, this seems to be the only way to prove a lower bound. We will also show a theorem which makes some progress with this flavor towards settling the exact complexity of the inner product function.  
    • 08.04.22   14:00
    • Pavel Pudlak
    • (IM CAS)
    • Read-once linear branching programs and the regular Res(lin) proof system, Part II
    • Abstract:
    • In this talk I will show the connection of a certain type of read-once linear branching programs and a certain type of the Res(lin) proof system. Further, I will present a construction of directional-derivative affine extractors.
    • 01.04.22   14:00
    • Pavel Pudlak
    • (IM, CAS)
    • Read-once linear branching programs and the regular Res(lin) proof system
    • Abstract:
    • We consider a version of read-once branching programs where queries are parities of the input bits. We define two kinds of these branching programs. For the more restricted version, we prove exponential lower bounds. For the less restricted version, we show that such a branching program finds a falsified clause in an unsatisfiable CNF iff there exists a Res(lin) refutation that has essentially the same size and satisfies a the same condition as read-once branching programs. Joint work with Svyatoslav Gryaznov and Navid Talebanfard.  
    • 25.03.22   14:00
    • Pavel Hrubes
    • (IM CAS)
    • Linear separation complexity of a random function
    • Abstract:
    • Linear separation complexity of a Boolean function is a measure of how hard it is to distinguish accepting and rejecting inputs by means of a linear program. I will discuss nontrivial upper and lower bounds on separation complexity of a random function. Joint work with Navid Talebanfard
    • 18.03.22   14:00
    • Michal Koucký
    • (MFF UK)
    • Data structure lower bounds and popular conjectures
    • Abstract:
    • We investigate the relative power of several conjectures that attracted recently lot of interest. We establish a connection between the Network Coding Conjecture (NCC) of Li and Li and several data structure like problems such as non-adaptive function inversion of Hellman and the well-studied problem of polynomial evaluation and interpolation. In turn these data structure problems imply super-linear circuit lower bounds for explicit functions such as integer sorting and multi-point polynomial evaluation.  
    • 11.03.22   14:00
    • Ivan Mihajlin
    • (Steklov Institute, Saint Petersburg)
    • XOR-KRW conjecture and composition of universal relation and a function
    • Abstract:
    • One of the major open problems in theoretic computer science is showing the existence of a problem that could be solved in polynomial time but not by a logarithmic depth circuit (P vs NC_1). One approach that has a lot of progress in the last several years is to prove Karchmer, Raz, and Wigderson conjecture. It states that there is no better way to compute the composition of two functions than applying them one by one. In this talk, we will discuss the modification of KRW conjecture called XOR-KRW. We will look at some partial results about the composition of a universal relation with a function. We will also discuss reasons to be optimistic about actually separating P and NC_1.
    • 04.06.21   14:30
    • n/a
    • (n/a)
    • CANCELLED
    • Abstract:
    • Apologies for the inconvenience.
    • 19.02.21   14:30
    • Navid Talebanfard
    • (Institute of Mathematics, CAS)
    • Interlude: how many error correcting codes are there?
    • Abstract:
    • We continue our journey through the landscape of extremal combinatorics. This time we will acquaint ourselves briefly with the powerful technique of (hyper)graph containers which is used to bound the number of independent sets in various graphs and hypergraphs. Specifically, possibly of interest of complexity theorists, we will see a result of Balogh, Treglown and Wagner which gives a close to tight bound on the number of possible error correcting codes of a given relative distance.
    • 11.12.20   14:30
    • Pavel Hrubeš
    • (Institute of Mathematics, CAS)
    • Tau conjectures
    • Abstract:
    • Tau conjectures of Koiran and Poitier are an approach towards proving arithmetic circuit lower bounds. Besides that, they are related to some interesting mathematics. I will explain the background and whatever I feel like at the moment. 
    • 27.11.20   14:30
    • Susanna F. de Rezende
    • (Institute of Mathematics, CAS)
    • KRW Composition Theorems via Lifting
    • Abstract:
    • Proving super-logarithmic lower bounds on the depth of circuits (i.e., P \neq NC^1) is one of the main frontiers of circuit complexity.  In 1991, Karchmer, Raz and Wigderson observed that we could resolve this question by proving the following conjecture: Given two non-constant boolean functions f, g, the depth complexity of their composition is approximately equal to the sum of their individual depth complexities.    Several works have made progress towards resolving this conjecture by proving it for every outer function f, but only when composed with two specific inner functions g. In this talk, I will present a recent result that extends the range of inner functions that can be handled to include any function g whose depth complexity can be lower bounded via a certain lifting theorem. Based on a joint work with Or Meir, Jakob Nordstrom, Toniann Pitassi, and Robert Robere. 
    • 20.11.20   14:30
    • Navid Talebanfard
    • (Institute of Mathematics, CAS)
    • Combinatorial miniatures from low depth complexity, chapter two
    • Abstract:
    • Motivated by proving lower bounds for affine dispersers, in this chapter we will see a graph theoretic characterization of affine spaces accepted by 2-CNFs.
    • 13.11.20   14:30
    • Navid Talebanfard
    • (Institute of Mathematics, CAS)
    • Combinatorial miniatures from low depth complexity, chapter one
    • Abstract:
    • In what is hopefully going to be a series of talks, I will survey very natural extremal combinatorial questions arising from complexity theory. I will point out several questions and report some progress. In the first chapter we will look at a relaxation of VC dimension and prove a Sauer-Shelah type theorem.
    • 23.10.20   14:30
    • Pavel Pudlak
    • (IM)
    • Tree codes - recent progress
    • Abstract:
    • The problem of finding an explicit construction of good tree codes over a constant size alphabet is still open. In this talk I will explain the problem and mention some recent results and proposed approaches to this problem.
    • 16.10.20   14:30
    • Dmitry Gavinsky
    • (IM, CAS)
    • Bare quantum simultaneity versus classical interactivity in communication complexity
    • Abstract:
    • We shall see a relational problem that is easy for the weakest quantum model of communication – simultaneous message passing (without shared resources); at the same time, the problem is difficult for the strongest classical model – interactive (two-way) communication.
    • 02.10.20   14:30
    • Navid Talebanfard
    • (IM, CAS)
    • Super Strong ETH is true for strong PPSZ
    • Abstract:
    • Super Strong ETH states that there is no k-SAT algorithm with running time 2^(1 - f_k)m where f_k >> 1/k. We prove that this hypothesis is true for the strong version of the PPSZ algorithm. Previously such a bound was known only for the weak version of PPSZ. Our construction is based on a modification of satisfiable Tseitin formulas over a certain class of high girth graphs. This is joint work with Dominik Scheder.
    • 24.04.20   13:30
    • Navid Talebanfard
    • (IM, CAS)
    • A tutorial on character sums and Paley graphs
    • Abstract:
    • We recall the famous of problem explicit constructions of Ramsey graphs. One of the early non-trivial constructions is Paley graphs defined using quadratic residues in finite fields. We will see nice tools from analytic number theory to study properties of this graph.  
    • 27.03.20   13:30
    • Stanislav Žák
    • (Institute of Computer Science, CAS)
    • A Logical Characteristic of Read-Once Branching Programs
    • Abstract:
    • We present a mathematical model of the intuitive notions such as the knowledge or the information arising at different stages of computations on branching programs (b.p.). The model has two appropriate properties: i) The "knowledge" arising at a stage of computation in question is derivable from the "knowledge" arising at the previous stage according to the rules of the model and according to the local arrangement of the b.p. ii) The model confirms the intuitively well-known fact that the knowledge arising at a node of a computation depends not only on it but in some cases also on a "mystery" information. (I. e. different computations reaching the same node may have different knowledge(s) arisen at it.) We prove that with respect to our model no such information exists in read-once b.p.`s but on the other hand in b. p.`s which are not read-once such information must be present. The read-once property forms a frontier. More concretely, we may see the instances of our models as a systems $S=(U,D)$ where $U$ is a universe of knowledge and $D$ arederivation rules. We say that a b.p. $P$ is compatible with a system $S$ iff along each computation in $P$ $S$ derives $F$ ($false$) or $T$ ($true$) at the end correctly according to the label of the reached sink. This key notion modifies the classic paradigm according to which the computational complexity is defined with respect to different classes of restricted b.p.`s (e.g. read-once b.p.`s, k-b.p.`s, b.p.`s computing in limited time etc.). Now, the restriction is defined by a subset of systems and only these programs are taken into account which are compatible with at least one of the chosen systems. Further  we may understand the sets $U$ of knowledge(s) as a sets of admissible logical formulae.  More rich  sets $U$`s imply the larger (= more free) restrictions on b.p.`s and consequently the smaller complexities of Boolean functions are detected. More rich logical equipment implies stronger computational effectiveness.
    • 31.01.20   13:30
    • Alexander Belov
    • (University of Latvia )
    • Some Results in Property Testing
    • Abstract:
    • The field of property testing deals with the following question. Given an object, detect whether it satisfies some property or is far from doing so. Usually, the object is modelled as a bit-string, and the distance is (relative) Hamming distance. The goal is to develop an algorithm whose complexity is very small: much smaller than the size of the object.  
    • 20.12.19   13:30
    • Erfan Khaniki
    • (IM)
    • Does the existence of a complete problem for TFNP class imply the existence of an optimal proof system or vice versa? Part II.
    • Abstract:
    • In this lecture we will construct an oracle with respect to which:      a. There is no optimal proof system for propositional tautologies.      b. TFNP=FP. The existence of this oracle and the one constructed in the previous lecture shows that TFNP_c and CON^N are independent of each other in relativized worlds.  
    • 13.12.19   13:30
    • Erfan Khaniki
    • (IM)
    • Does the existence of a complete problem for TFNP class imply the existence of an optimal proof system or vice versa? 
    • Abstract:
    • In this talk, we will investigate the relationship between proof complexity conjectures that are mentioned in the "Incompleteness in the finite domain" paper. In particular, we are interested in the relationship between the nonexistence of a complete problem for TFNP class (TFNP_c)  and the nonexistence of an optimal proof system for propositional tautologies (CON^N). For this matter,  we will construct two oracles V and W such that: 1. With respect to the V      a. There is no complete problem for disjoint NP-pairs.      b. E=NE. 2. With respect to the W      a. There is no optimal proof system for propositional tautologies.      b. TFNP=FP. The existence of these oracles shows that TFNP_c and CON^N are independent of each other in the relativized worlds.  
    • 06.12.19   13:30
    • Cornelius Brand
    • (MFF)
    • Grassmann meets Macaulay: From Algebra to Algorithms and back
    • Abstract:
    • In this talk, I will give an introduction to two recent algebraic techniques in (parameterized) algorithms for hard problems: One is the exterior-algebra based approach of Brand, Dell and Husfeldt (STOC'18) and Brand (ESA'19), the other is the one by Pratt (FOCS'19) and Brand and Pratt (submitted), based on a symbolic calculus of differential operators. Both techniques will be gently introduced in the context of their flagship application problem: Detecting squarefree monomials in polynomials computed by arithmetic circuits, where they each yield the state-of-the-art in certain settings. I then proceed to show how these seemingly unrelated algorithmic techniques both arise from an underlying isomorphism of algebraic structures. This is of independent interest, and gives lower bounds on the symmetric rank of a specific symmetric tensor, namely the determinant of generic Hankel matrices, and extends recent work in commutative algebra (Shafiei 2015, J. Commut. Alg.).  
    • 29.11.19   13:30
    • Lukáš Folwarczný
    • (IM CAS)
    • Adventures in Monotone Complexity and TFNP
    • Abstract:
    • In this talk, I present the main ideas from the paper Adventures in Monotone Complexity and TFNP by Mika Göös, Pritish Kamath, Robert Robere, and Dmitry Sokolov. The main focus of the talk will be on the relations between monotone computational models and communication complexity (going from Karchmer-Wigderson (formulas) and Razborov (circuits) to this paper (span programs)).  
    • 15.11.19   13:30
    • Martin Koutecký
    • (IUUK MFF UK)
    • Presburger meets Cambridge Analytica
    • Abstract:
    • Cambridge Analytica is an infamous and now bankrupt (but sure to survive in some other way) company which helped manipulate elections all over the world (including the Brexit and Trump campaigns) through targeted advertising on social networks. We want to analyze such tasks and events from the perspective of computational complexity, asking questions such as: what is the cheapest bribery which makes my candidate win? what if opinion diffusion happens in the underlying social network? what if manipulation happens simultaneously by multiple agents? Answering these questions is helpful not only to a potential briber, but also to observers wishing to detect bribery or have meaningful measures of the (surprisingly elusive) notion of margin of victory. Presburger arithmetic (PrA) is the first-order theory of the natural numbers with addition, named in honor of Moj?esz Presburger who introduced it in 1929 and proved its decidability. While the questions posed above are hard in general, we show that when the number of candidates and/or voter types is small, the problems can be formulated as model checking of short PrA sentences, and already Presburger's proof gives a fixed-parameter tractable algorithm. In this talk, I will present Cooper's algorithm from the 1970's which is faster than Presburger's original procedure. Still, many interesting questions remain open.  
    • 01.11.19   13:30
    • Jan Pich
    • (IM)
    • Beyond Natural Proofs
    • Abstract:
    • Hardness magnification reduces major complexity separations to proving lower bounds for some natural problem Q against weak circuit models. Several recent works have established results of this form. In the most intriguing cases, the required lower bound is known for problems that appear to be significantly easier than Q, while Q itself is susceptible to lower bounds but these are not yet sufficient for magnification. In this work, we provide more examples of this phenomenon, and investigate the prospects of proving new lower bounds using this approach. In particular, we consider the following essential questions associated with the hardness magnification program: - Does hardness magnification avoid the natural proofs barrier of Razborov and Rudich? - Can we adapt known lower bound techniques to establish the desired lower bound for Q? We establish that some instantiations of hardness magnification overcome the natural proofs barrier in the following sense: slightly superlinear-size circuit lower bounds for certain versions of the minimum circuit size problem MCSP imply the non-existence of natural proofs. As a corollary of our result, we show that certain magnification theorems not only imply strong worst-case circuit lower bounds but also rule out the existence of efficient learning algorithms. Hardness magnification might sidestep natural proofs, but we identify a source of difficulty when trying to adapt existing lower bound techniques to prove strong lower bounds via magnification. This is captured by a locality barrier: existing magnification theorems unconditionally show that the problems Q considered above admit highly efficient circuits extended with small fan-in oracle gates, while lower bound techniques against weak circuit models quite often easily extend to circuits containing such oracles. This explains why direct adaptations of certain lower bounds are unlikely to yield strong complexity separations via hardness magnification. This is a joint work with Lijie Chen, Shuichi Hirahara, Igor C. Oliveira, Ninad Rajgopal and Rahul Santhanam.
    • 18.10.19   13:30
    • Pavel Hrubes
    • (IM)
    • On the distribution of runners on a circle
    • Abstract:
    • I will discuss the following problem: consider runners on a circular track, running with constant speeds such that k of the speeds are distinct. Does it have to be the case that, at some point in time, their distribution on the circle is far from uniform? I will give an almost optimal solution, as a function of k. This has an interesting application to the distribution of complex arguments of roots of univariate polynomials, and the Real Tau Conjecture in arithmetic circuit complexity.
    • 11.10.19   13:30
    • Anish Mukherjee
    • (MFF UK)
    • Solving connectivity problems via basic Linear Algebra
    • Abstract:
    • We consider some classical graph connectivity problems like reachability, shortest path and disjoint paths in this talk. For the first two problems, we show efficient parallel (dynamic AC^0) algorithms in the dynamic model, confirming a conjecture of Patnaik and Immerman ’94 for directed reachability. Recently, we have been able to extend this for batch updates also. For the optimization version of the disjoint paths problem, we show efficient sequential and parallel algorithms in planar graphs where all the terminals lie on a single face. This partly answers an open question of Colin De Verdičre and Schrijver ’08. Interestingly the basic idea behind these algorithms is to compute some linear algebraic property of the matrix associated with the given graph, which I shall try to convey in this talk. Based on joint works with Samir Datta, Raghav Kulkarni, Siddharth Iyer, Thomas Schwentick, and Thomas Zeume.  
    • 04.10.19   13:30
    • Yuri Gurevich
    • (University of Michigan)
    • Who needs category theory?
    • Abstract:
    • Mathematicians use category theory, at least some of them do. In fact category theory is instrumental in some branches of mathematics, e.g. algebraic topology. But what about computer scientists or physicists? Do they need category theory? If category theory is your hammer, some computing problems look like appropriate nails. However the speaker was not impressed and remained skeptical about the use of category theory in computer science. When he learned that the generally accepted mathematical basis for topological quantum computing is sophisticated category theory, he proposed to his long-time collaborator Andreas Blass to "decategorize" topological quantum computing. It turned out, surprisingly, that category theory or something like it is necessary for topological quantum computing. Moreover the root cause of the necessity is not specific to topological quantum computing. There should be numerous other computing problems where something like category theory is necessary. Understanding the root cause allowed us to simplify the mathematical basis for the topological quantum computing and to decategorize it to the extent possible. In the main part of the talk, without assuming any knowledge of category theory or quantum computing, we illustrate, on a simplified example, why category theory or something like it is necessary for topological quantum computing.  
    • 13.09.19   13:30
    • Makrand Sinha
    • (CWI Amsterdam)
    • Exponential Separation between Quantum Communication and Logarithm of Approximate Rank
    • Abstract:
    • Chattopadhyay, Mande and Sherif (to appear in STOC 2019) recently exhibited a total Boolean function, the sink function, that has polynomial approximate rank and polynomial randomized communication complexity. This gives an exponential separation between randomized communication complexity and logarithm of the approximate rank, refuting the log-approximate-rank conjecture. We show that even the quantum communication complexity of the sink function is polynomial, thus also refuting the quantum log-approximate-rank conjecture. Our lower bound is based on the fooling distribution method introduced by Rao and Sinha (Theory of Computing 2018) for the classical case and extended by Anshu, Touchette, Yao and Yu (STOC 2017) for the quantum case. We also give a new proof of the classical lower bound using the fooling distribution method. Joint work with Ronald de Wolf.
    • 07.06.19   13:30
    • Pavel Hubacek
    • (MFF UK)
    • Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir
    • Abstract:
    • The Fiat-Shamir heuristic transforms a public-coin interactive proof into a non-interactive argument, by replacing the verifier’s random coins with a cryptographic hash function that is applied to the protocol's transcript. Constructing hash functions for which this transformation is sound is a central and long-standing open question in cryptography. We show that solving the End-Of-Metered-Line problem is no easier than breaking the soundness of the Fiat-Shamir transformation when applied to the sumcheck protocol. In particular, if the transformed protocol is sound, then any hard problem in #P gives rise to a hard distribution in the class CLS. Since CLS is contained in PPAD for which the problem of finding a Nash equilibrium is complete, our results show existence of a distribution of strategic games for which it is not possible to find a Nash equilibrium in polynomial time. Our main technical contribution is a stateful incrementally verifiable procedure that, given a SAT instance over n variables, counts the number of satisfying assignments. This is accomplished via an exponential sequence of small steps, each computable in time poly(n). Incremental verifiability means that each intermediate state includes a sumcheck-based proof of its correctness, and the proof can be updated and verified in time poly(n). Joint work with Arka Rai Choudhuri, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen and Guy N. Rothblum.  
    • 24.05.19   13:30
    • Michal Koucky
    • (MFF UK)
    • Constant factor approximations to edit distance on far input pairs in nearly linear time
    • Abstract:
    • We will present an algorithm that runs in time n^{1+eps} and computes a constant factor approximation to edit distance of two input strings, given that their edit distance is at least n^{1-delta} for some delta>0 dependening on eps>0. Joint work with Mike Saks.
    • 17.05.19   13:30
    • Pavel Hrubes
    • (IM CAS)
    • Lower bounds on balancing families
    • Abstract:
    • A family of proper non-empty subsets S1, . . . , Sk ? [n] is called balancing if for every subset X ? [n] of size n/2, there is i ? [k] so that                 |Si ? X| = |Si|/2. I will show that, for n even, the size of a balancing family must be at least n(1-o(1))/2. A similar reasoning can be applied to prove lower bounds on certain types of depth-two circuits computing the majority function.  Joint work with S.Ramamoorthy, A. Rao, and A. Yehudayoff.
    • 03.05.19   13:30
    • Navid Talebanfard
    • (IM)
    • A separator theorem for hypergraphs and a CSP-SAT algorithm
    • Abstract:
    • I'll show how to remove a small number of edges from a uniform hypergraph of small vertex degree to break it into small connected components. I'll use it to give a CSP-SAT algorithm for CSPs with small variable frequency. This is joint work with Vojtěch Rödl.
    • 12.04.19   13:30
    • Hoeteck Wee
    • (CNRS and ENS)
    • Attribute-Based Encryption and Information-Theoretic Crypto
    • Abstract:
    • Can we encrypt data while enabling fine-grained access control, as is necessary to protect big, complex data? In this talk, we will survey how addressing this question led to new lower and upper bounds in information-theoretic cryptography and secret sharing, which in turn came from building new connections to communication complexity and private information-retrieval.
    • 29.03.19   13:30
    • Pavel Hrubeš
    • (IM CAS)
    • Circuit lower bounds via non-negative rank
    • Abstract:
    • The non-negative rank of a matrix is a quantity which has found several applications in communication complexity and extension complexity of polytopes. We will show that certain lower bounds on non-negative rank imply, at least in principle, circuit lower bounds. With a Boolean function $f$ and $\epsilon>0$, we associate an explicit matrix $M_\epsilon(f)$ so that the circuit size of $f$ is at least the non-negative rank of $M_{\epsilon}(f)$, for $\epsilon$ sufficiently small. We also discuss continuity properties of the non-negative rank.    
    • 15.03.19   13:30
    • Veronika Slivova
    • (MFF UK)
    • Stronger Lower Bounds for Online ORAM
    • Abstract:
    • Oblivious RAM (ORAM), introduced in the context of software protection by Goldreich and Ostrovsky [JACM’96], aims at obfuscating the memory access pattern induced by a RAM computation. We will show that every implementation of Online Oblivious RAM has logarthmic overhead. Joint work with P. Hubacek, M. Koucky and K. Kral.  
    • 01.03.19   13:30
    • Dmitri Gavinsky
    • (IM)
    • Deterministic indeterminacy of CHSH-solving protocols
    • Abstract:
    • How unpredicatble is the behaviour of efficient entagled players in the CHSH game? We will discuss this question from both qualitative and quantitative point viewpoints.
    • 15.02.19   13:30
    • Pavel Hrubeš
    • (IM)
    • How to compute random Boolean function over the reals.
    • Abstract:
    • We consider the problem of defining a Boolean function by means of a first-order formula over the reals. We discuss the connection of this problem with other questions in computational complexity. We also outline some bounds on the size of formulas computing a random Boolean function.    
    • 01.02.19   13:30
    • Pavel Pudlák
    • (IM)
    • Entropy extractors for small zero-fixing sources, part III
    • Abstract:
    • I will finish the first construction by presenting the skeleton-fixing procedure and start the second construction.
    • 25.01.19   13:30
    • Pavel Pudlák
    • (IM )
    • Entropy extractors for small zero fixing sources, part II
    • Abstract:
    • I will continue with the construction of an extractor for zero fixing sources of triple logarithmic size.  
    • 18.01.19   13:30
    • Pavel Pudlák
    • (IM)
    • Entropy extractors for small zero fixing sources
    • Abstract:
    • A (k,n)-zero fixing source X is given by a subset S of [n] of size k. The source X produces 0-1 vectors that are zero outside of S each with probability 2^{-k}. An extractor for a (k,n)-zero fixing source is a mapping F:{0,1}^n\to {0,1}^l such that F(X) is close to the uniform distribution on {0,1}^l. Such extractors are known for k down to log log n with l=k-O(1). In this talk we will show some constructions for k
    • 11.01.19   13:30
    • Dmitry Gavinsky
    • (IM CAS)
    • The layer complexity of Arthur-Merlin-like communication
    • Abstract:
    • In communication complexity the Arthur-Merlin (AM) model is the most natural one that allows both randomness and non-determinism. Presently we do not have any super-logarithmic lower bound for the AM-complexity of an explicit function. Obtaining such a bound is a fundamental challenge to our understanding of communication phenomena. In this work we explore the gap between the known techniques and the complexity class AM. In the first part we define a new natural class Small-advantage Layered Arthur-Merlin (SLAM) that have the following properties:     - SLAM is (strictly) included in AM and includes all previously known sub-AM classes with non-trivial lower bounds.     - SLAM is qualitatively stronger than the union of those classes.     - SLAM is a subject to the discrepancy bound: in particular, the inner product function does not have an efficient SLAM-protocol. Structurally this can be summarised as SBP ? UAM ? SLAM ? AM ? PP. In the second part we ask why proving a lower bound of ?(?n) on the MA-complexity of an explicit function seems to be difficult. Both of these results are related to the notion of layer complexity, which is, informally, the number of “layers of non-determinism” used by a protocol. We believe that further investigation of this concept may lead to better understanding of the communication model AM and to non-trivial lower bounds against it.
    • 04.01.19   13:30
    • Jan Pich
    • (Oxford University)
    • Hardness magnification near state-of-the-art lower bounds
    • Abstract:
    • We continue the development of hardness magnification, a strategy for deriving strong circuit lower bounds by reducing them to a refined analysis of weaker models proposed by Oliveira and Santhanam (2018). Specifically, we consider a gap version of the meta-computational problem MCSP which asks to distinguish truth-tables of Boolean functions of small circuit complexity from truth-tables of a slightly larger complexity and establish that a small improvement over the state-of-the-art lower bounds in a variety of computational models for the gap version of MCSP would imply explicit super-polynomial lower bounds. This talk is based on a joint work with Igor C.Oliveira and Rahul Santhanam.
    • 14.12.18   13:30
    • Navid Talebanfard
    • (IM)
    • An exposition of R. Williams' "Strong ETH Breaks with Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation".
    • Abstract:
    • Variants are the Strong Exponential Time Hypothesis have been proposed. In this talk I sketch Williams' result which asserts that Strong ETH fails when we have both non-determinism and randomization. The proof uses arithmetization and polynomial arguments.
    • 07.12.18   13:30
    • Debarati Das
    • (Charles University)
    • Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time
    • Abstract:
    • Edit distance is a measure of similarity of two strings based onthe minimum number of character insertions, deletions, and substitutions required to transform one string into the other. The edit distance can be computed exactly using a dynamic programming algorithm that runs in quadratic time. Andoni, Krauthgamer and Onak (2010) gave a nearly linear time algorithm that approximates edit distance within approximation factor $\text{poly}(\log n)$. In this talk, I will describe an algorithm with running time $\tildeO(n^{2-2/7})$ that approximates the edit distance within a constant factor. This is a joint work with Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky, Michael Saks
    • 23.11.18   13:30
    • Pavel Hubáček
    • (MFF UK)
    • The Journey from NP to TFNP Hardness
    • Abstract:
    • The complexity class TFNP is the search analogue of the class NP with the additional guarantee that any instance has a solution. TFNP has attracted extensive attention due to its natural syntactic subclasses that capture the computational complexity of important search problems from algorithmic game theory, combinatorial optimization and computational topology. Thus, one of the main research objectives in the context of TFNP is to search for efficient algorithms for its subclasses, and at the same time proving hardness results where efficient algorithms cannot exist. In my talk, I will show that hard-on-average TFNP problems exist under the weak assumption that there exists a hard-on-average language in NP. In terms of techniques, our results demonstrate an interesting interplay between problems in TFNP, derandomization techniques, and zero-knowledge proofs. Based on joint work with Moni Naor and Eylon Yogev.
    • 08.06.18   13:30
    • Diptarka Chakraborty
    • (Charles University)
    • Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication
    • Abstract:
    • The conjectured hardness of Boolean matrix-vector multiplication has been used with great success to prove conditional lower bounds for numerous important data structure problems, see Henzinger et al. [STOC'15]. In recent work, Larsen and Williams [SODA'17] attacked the problem from the upper bound side and gave a surprising cell probe data structure (that is, we only charge for memory accesses, while computation is free). Their cell probe data structure answers queries in $\tilde{O}(n^{7/4})$ time and is succinct in the sense that it stores the input matrix in read-only memory, plus an additional $\tilde{O}(n^{7/4})$ bits on the side. In this talk, we present a new cell probe data structure with query time $\tilde{O}(n^{3/2})$ storing just $\tilde{O}(n^{3/2})$ bits on the side. We then complement our data structure with a matching lower bound showing that any data structure storing $r$ bits on the side, with $n < r < n^2$ must have query time $t$ satisfying $t r = \tilde{\Omega}(n^3)$. For $r \leq n$, any data structure must have $t = \tilde{\Omega}(n^2)$. Since lower bounds in the cell probe model also apply to classic word-RAM data structures, the lower bounds naturally carry over. This talk will be based on a joint work with Lior Kamma and Kasper Green Larsen (to appear in STOC'18).
    • 25.05.18   13:30
    • Pavel Pudlák
    • (IM, CAS)
    • Matroids, 3-regular graphs and random restrictions
    • Abstract:
    • I will show some connections between matroids and random restrictions of Tseitin tautologies on 3-regular graphs. In particular I will show that the domains of the restrictions are flats in a matroid that is dual to a bicircular matroid. I will pose several problems concerning how these facts can be generalized to other kinds of restrictions and other graphs. This talk will be a sort of a continuation of Navid's, but I will recall everything that is needed.
    • 11.05.18   13:30
    • Alexander V. Smal
    • (Steklov Math. Inst., St. Petersburg)
    • Half-duplex communication complexity
    • Abstract:
    • Suppose Alice and Bob are communicating bits to each other in order to compute some function f but instead of a classical communication channel they have a pair of walkie-talkie devices. They can use some classical communication protocol for f where each round one player sends bit and the other one receives it. The question is whether talking via walkie-talkie gives them more power? Using walkie-talkie instead of a classical communication channel allows players two extra possibilities: to speak simultaneously (but in this case they do not hear each other) and to listen at the same time (but in this case they do not transfer any bits). We show that for some definitions this non-classical communication model is in fact more powerful than the classical one as it allows to compute some functions in smaller number of rounds. We also introduce round elimination technique for proving lower bounds in this setting and use it to prove lower bounds for some Boolean functions. Join work with  Kenneth Hoover, Russell Impagliazzo and Ivan Mihajlin
    • 04.05.18   13:30
    • Eric Allender
    • (Rutgers University)
    • Complexity meets Computability: Connections between Computational Complexity Theory and the Kolmogorov Random Strings
    • Abstract:
    • In this talk, I will survey some results (some dating back more than a decade) indicating that certain computational complexity classes can be characterized in terms of efficient reducibility to the (undecidable) set of Kolmogorov-random strings.  There have been a few new developments, and there are a lot of open questions. Some of the main results in this line of research: Let U be a universal Turing machine, and let R_U be {x : K_U(x) is at least |x|}.  That is, R_U is the set of Kolmogorov-random strings, when K-complexity is defined using universal machine U. When we write "R" instead of "R_U" in statement, it will mean that the statement holds for EVERY universal machine U.  Let P_tt(A) denote the class of sets that are polynomial-time non-adaptively reducible to A (also known as the class of sets that are polynomial-time truth-table reducible to A).  Let P(A) denote the class of sets that are poly-time Turing-reducible to A. Theorem: BPP is contained in P_tt(R), which is contained in PSPACE, which is contained in P(R). NEXP is contained in NP(R), which is contained in EXPSPACE(R).
    • 27.04.18   13:30
    • Navid Talebanfard
    • (IM CAS)
    • Random 3-regular graphs from random 3-regular graphs
    • Abstract:
    • Given a 3-regular graph we define a natural process which gives a random topological minor of this graph. We show that if the original graph is uniformly distributed, so is the resulting topological minor over the space of 3-regular graphs of the same size. Based on ongoing work with Pavel Pudlák and Neil Thapen.
    • 23.03.18   13:30
    • Jan Hladký
    • (IM CAS)
    • Graphons as weak* limits
    • Abstract:
    • Around 2004, Lovasz and Szegedy came up with a certain compactification of the space of finite graphs. More precisely, they proved that there exists a metric - now called the cut-distance - which yields a compact topology. Their proof of compactnes relies on the Szemeredi regularity lemma. An entire theory, with applications in extremal graph theory and random graphs, developed from this statement. I will talk about approaching the cut-norm topology via the weak* topology. This approach gives a new view of many properties, and in particular yields a quick and elementary proof of the Lovasz-Szegedy theorem. The talk will be self-contained. Various bits of this are joint work with Martin Dolezal, Jan Grebik, Jon Noel, Diana Piguet, Israel Rocha, Vaclav Rozhon, Maria Saumell.
    • 19.01.18   13:30
    • Navid Talebanfard
    • (IM CAS)
    • Prediction, partial information and hindsight
    • Abstract:
    • Let X be a random variable distributed over n bit strings with entropy at least n - k. Subaddativity implies that the average coordinate has entropy close to 1 if k is small. Meir and Wigderson recently showed that the same remains true even if we are allowed to non-deterministically query around n/k other coordinates. I will present an alternative proof of this fact which quantitatively tightens this result. Furthermore I will show how Meir and Wigderson used to this to develop a top-down argument for depth-3 circuit lower bounds.  Based on join work with Alexander Smal.
    • 12.01.18   13:30
    • Alexander Belov
    • (University of Latvia)
    • Quantum Adversary Bound
    • Abstract:
    • In this talk, I will briefly describe the quantum adversary bound, which is an intriguing way of characterising quantum query complexity, and sketch some of its applications. No prior knowledge of quantum computation is required.
    • 15.12.17   13:30
    • Martin Böhm
    • (IUUK)
    • Nested Convex Bodies are Chaseable
    • Abstract:
    • In the Convex Body Chasing problem, we are given an initial point v in R^d and an online sequence of n convex bodies F_1,...,F_n. When we receive F_i, we are required to move inside F_i. Our goal is to minimize the total distance travelled. This fundamental online problem was first studied by Friedman and Linial (DCG 1993). They proved an Omega(sqrt(d)) lower bound on the competitive ratio, and conjectured that a competitive ratio depending only on d is possible. However, despite much interest in the problem, the conjecture remains wide open. In this work, we give a simple f(d)-competitive algorithm for chasing *nested* convex bodies in R^d, i.e. when F_2 lies inside F_1, F_3 lies inside F_2 and so on. Among other consequences, this indicates that the problem is considerably more difficult when the optimal path visits several points, as opposed to just moving to a single globally feasible position. Joint work with Nikhil Bansal, Marek Eliáš, Grigorios Koumoutsos, and Seeun William Umboh.
    • 24.11.17   13:30
    • Chethan Kamath
    • (IST Austria)
    • Adaptively-secure secret sharing
    • Abstract:
    • A secret-sharing scheme is used to distribute a secret between a set of participants so that a subset of the participants that satisfy certain conditions can reconstruct the secret. In the computational setting, it is relatively easy to achieve selective security (where the adversary commits a-priori to the set of corrupt participants), but appears difficult to achieve the more natural notion of adaptive security (where the adversary can corrupt participants as the attack progresses). It is well known that selective security, where the adversary has to commit to n-bits of information about his future choices, automatically implies adaptive security at the cost of amplifying the adversary’s advantage by a factor of up to 2^n. In this talk we will see how one can, in certain cases, achieve better bounds than 2^n by using techniques from graph pebbling.  (Based on joint work with Zahra Jafargholi, Karen Klein, Ilan Komargodski, Krzysztof Pietrzak, and Daniel Wichs.)
    • 20.10.17   13:30
    • Dmitri Gavinsky
    • (IM CAS)
    • Quantum versus classical simultaneity in communication complexity
    • Abstract:
    • We will see a bipartite partial function, which has no efficient solution in the model of randomised simultaneous message passing (with shared randomness), but has an efficient protocol in the model of quantum simultaneous message passing – even without shared randomness. This can be interpreted as the strongest known ? as of today ? example of "super-classical" capabilities of the weakest studied model of quantum communication.
    • 02.06.17   13:30
    • Klim Efremenko
    • (Tel-Aviv University)
    • Testing Equality in Communication Graphs
    • Abstract:
    • Let $G=(V,E)$ be a connected undirected graph with $k$ vertices. Suppose that on each vertex of the graph there is a player having an $n$-bit string. Each player is allowed to communicate with its neighbors according to a (static) agreed communication protocol and the players must decide, deterministically, if their inputs are all equal. What is the minimum possible total number of bits transmitted in a protocol solving this problem? We determine this minimum up to a lower order additive term in many cases (but not for all graphs).   In particular, we show that it is $kn/2+o(n)$ for any Hamiltonian $k$-vertex graph, and that for any $2$-edge connected  graph with $m$ edges containing no two adjacent vertices of degree exceeding $2$ it is $mn/2+o(n)$. The proofs combine graph theoretic ideas with tools from additive number theory.
    • 19.05.17   13:30
    • Filip Šedivý
    • (Faculty of Mathematics and Physics, Charles Univ.)
    • Cluster Planarity
    • Abstract:
    • This thesis studies the problem of clustered planarity and follows two directions. First direction deals with computational complexity, where we show how clustered planarity can be solved in linear nondeterministic time in terms of the number of vertices of the input graph. Second directions is characterization of restricted versions of clustered planarity using minimal non-clustered-planar instances. For this purpose we introduce a notion of clustered minor using several operations reducing clustered graphs. We show that these operations preserve clustered planarity. We show that in the case of clustered graphs where clusters have size 2 and the graph is a cycle or a path, there are only finitely many minimal non-clustered-planar minors. We also mention known results about the computational complexity of clustered planarity.
    • 07.04.17   13:30
    • Igor Carboni Oliveira
    • (MFF, UK)
    • Complexity theory beyond deterministic exponential time and applications Parts II
    • Abstract:
    • Part I. (this will be on the Seminar on limits of efficient computation on Marh 15) I'll survey a variety of connections between non-uniform circuit lower bounds, non-trivial proof systems, non-trivial learning algorithms, and variants of natural properties. In particular, I plan to discuss how one can prove new unconditional lower bounds for standard complexity classes such as REXP, ZPEXP, BPEXP, and NEXP by designing algorithms with a non-trivial running time, and to present some open problems.  Part II. I'll focus on a recent application of some of the complexity-theoretic techniques behind these results. I'll describe in more detail recent progress on the problem of efficiently generating large canonical prime numbers, via pseudodeterministic pseudorandomness. If there is enough time and interest, we will also discuss some non-constructive aspects of the result, and connections to derandomization. Based on joint work with Rahul Santhanam.
    • 17.03.17   13:30
    • Anup Rao
    • (Univ. of Washington, Seattle, USA)
    • Lower bounds on Non-adaptive Data Structures for Median and Predecessor search
    • Abstract:
    • What is the best way to maintain a subset of {1,2,...,m} so that the median of the set can be easily recovered? We are interested in the algorithms that access the fewest memory locations when adding an element to the set and computing the median of the set. We prove the first lower bounds for such algorithms. We say that the algorithm handles insertions non-adaptively if the locations of memory accessed depend only on the element being inserted, and not on the contents of the memory. If the algorithm handles insertions non-adaptively, then our lower bounds imply that Binary Search Trees are essentially optimal (our results give a more general tradeoff between the parameters of the algorithm). In addition, we investigate the predecessor search problem, where the algorithm is required to compute the predecessor of any element in the set. Here we prove that if computing the predecessors can be done non-adaptively, then again Binary Search Trees are essentially optimal. Our results follow from a novel application of the Sunflower Lemma to these questions. This is joint work with Siva Ramamoorthy
    • 10.03.17   13:30
    • 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
    • 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
    • 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

  •