•  
    • 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

    Michal Koucky, Pavel Pudlak
    organizers

  •