# Seminar on limits of efficient computation (Seminář o limitech efektivních výpočtů)

Michal Koucký and Pavel Hubáček
<koucky@iuuk.mff.cuni.cz>

NTIN102 - 0/2 Z

Time: Wen 12:00-14:00.
Place: corridor, 3rd floor, Malá Strana.

A working seminar that aims to refer on ongoing research projects of participants and related issues within the scope of computational complexity and more broadly theoretical computer science. Attendees are expected to present their research, follow-up discussion is expected. Pizza will be provided for participants.

## Spring semester 2017/2018

This semester we plan to mix talks on our own research with presentations of various results by others. The first seminar will take place on February 21.

21. 2. 2018

Debarati Das: Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication

Abstract: I will define a model of combinatorial algorithms for Boolean matrix multiplication and show lower bounds for it.

## Winter semester 2017/2018

This semester we plan to focus on pebbling and its many applications in upper bounds, lower bounds and cryptography. The first seminar will take place on October 11th.

10.1. 2018

Martin Koutecký: Stealing elections

Abstract: Various bribery models are used to study campaigning in elections. We make these models more realistic with two extensions: an opinion diffusion process, and a back-and-forth game. I'll present our partial results. (Joint work with Piotr Faliszewski, Rica Gonen and Nimrod Talmon.)

13.12. 2017 and 3.1. 2018

Pavel Veselý: Beyond Hellman's Time-Memory Trade-Offs with Applications to Proofs of Space

Abstract: We will present a construction of hard to invert functions by Abusalah, Alwen, Cohen, Khilko, Pietrzak, and Reyzin which defeats Hellman's time-memory trade-off.

29. 11. and 6.12. 2017

Veronika Slívová: Scrypt is Maximally Memory-Hard

Abstract: We will show cryptographic applications of pebbling of Alwen, Chen, Pietrzak, Reyzin, and Tessaro.

22. 11. 2017

Pavel Dvořák: Network Information Flow

Abstract: I will present the seminal paper on network information flow of Ahlswede, Cai, Li, Yeung which generalizes pebbling and usual flows.

8. and 15. 11. 2017

Diptarka Chakraborty: Fractional pebbling

Abstract: I will introduce the notion of fractional pebbling of graphs of Cook, McKenzie, Wehr, Braverman and Santhanam.

1. and 8. 11. 2017

Nitin Saurabh: Pebling the pyramid by black and white pebbles

Abstract: I will present results on black and white pebbling of graphs by Klawe and their connection to the 'P vs LOG' question.

25. 10. 2017

Tomáš Toufar: On determinism versus non-determinism

Abstract: Insights of Paul, Pippenger, Szemeredi, and Trotter, and Santhanam on the 'P vs NP' question for linear time.

18. 10. 2017

Debarati Das: On Sparse Graphs with Dense Long Paths

Abstract: I will present a construction of hard to pebble graphs by Erdos, Graham and Szemeredi.

11. 10. 2017

Karel Král: On time versus space

Abstract: I will show a classic result by Hopcroft, Paul and Valiant that time O(t) can be simulated in space O(t/log t).

## Spring semester 2016/2017

This semester we plan to mix talks on our own research with presentations of various results by others. The first seminar will take place on March 1st.

24. 5. 2017

Abstract: We study cache behaviour of algorithms with caches of fluctuating sizes. We are motivated by the scenario when more algorithms run in pseudo-parallel. We will show that this case can be analyzed using existing techniques. Moreover we show that a large class of cache behaviours is cache constructible.

17. 5. 2017

Pavel Veselý: Packet Scheduling with Adversarial Jamming and Speedup

Abstract: In this problem an online algorithm transmits packets of arbitrary sizes over a channel prone to jamming errors which occur at times chosen by the adversary. The transmission taking place at the time of jamming is corrupt, the algorithm learns this fact immediately and it can retransmit the packet any time later. I will present a simple algorithm which is 1-competitive if it runs 4 times faster than an offline optimal algorithm. On the other hand, I will show that any deterministic 1-competitive algorithm needs speedup at least the golden ratio + 1 (approx. 2.618).
Joint work with M. Böhm, Ł. Jeż, and J. Sgall.

10. 5. 2017

Zdeněk Dvořák: Thinness of graph classes and approximation algorithms

Abstract: Baker(1994) found a technique to design polynomial-time approximation algorithms for many problems on planar graphs. This technique also works for graphs avoiding a fixed apex graph as a minor, and with significant extra effort some of the power of the technique can be extended to all proper minor-closed classes. We describe a novel graph decomposition that makes the generalization much easier and more natural, and show that all proper minor-closed graph classes, as well as subgraph-closed classes with strongly sublinear separators and bounded maximum degree admit this decomposition.

3. 5. 2017

Navid Talebanfard: The exact complexity of k-SAT

Abstract: I will discuss the complexity k-SAT with an emphasis on the asymptotics of k in the running time of existing algorithms.

26. 4. 2017

Petr Gregor: What is the best way to represent integers for counting?

Abstract: The standard binary representation of integers has its advantages but for increment and decrement operations it requires to read and write all bits in the worst case. We survey old and new results on space optimal counters with better worst case performance in the bit probe model. This has applications in various data structures.

19. 4. 2017

Tomáš Gavenčiak: Resilient algorithms and data structures

Abstract: Computer hardware errors are increasingly common in large scale computation and there are several approaches to countering them. While today mostly low-level approach (ECC and data-path reinforcement) is sufficient, algorithms adapted to these conditions can have better results and higher efficiency. I will present an informal introduction to the motivation, problems and selected algorithms resilient to hardware errors or even adversarial sabotage.

12. 4. 2017

Martin Koutecký: {Dodgson,Young}-Swap Bribery via ∃∀∃-Integer Programming

Abstract: The R-Swap Bribery problem asks to find a bribery of an election (described by swaps in preferences of voters) such that a preferred candidate wins under voting rule R. While this problem was known to be FPT for most voting rules R, there were two exceptions. I will show how to close this gap using a new result in integer programming. Several open problems remain, which I will review.

5. 4. 2017

Open session

Abstract: We are meeting at 12:15pm to go for lunch and discuss mathematics.

29. 3. 2017

Nitin Saurabh: Fourier Entropy-Influence Conjecture

Abstract: I will discuss Fourier Entropy-Influence Conjecture, present known results and open problems.

15. 3. 2017

Igor Carboni Oliveira: Complexity theory beyond deterministic exponential time and applications

Abstract: 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.

8. 3. 2017

Diptarka Chakraborty: Computing edit distance without suffix trees space

Abstract: Edit distance between two strings can be computed in $O(n+k^2)$ time where $k$ is the edit distance. However this algorithm involves construction of a suffix tree which is practically inefficient. Here we will discuss an $O(n + n^{1/2} k^{3/2})$ time algorithm for edit distance which does not use suffix trees. We believe its running time is actually $O(n+k^2)$. Can anyone prove it?

1. 3. 2017

Nicola Galesi: Refuting random 3-CNFs using polynomials requires large proof space

Abstract: A main tool in proving (space) lower bounds​ for refuting random k-CNF formulas is the well-known expansion property of incidence graph of the formula. Nevertheless, for k=3 the (1+eps)-expansion factor of the graph is no longer sufficient to prove proof space lower for Polynomial Calculus (PCR), a proof system working with polynomials.  In the talk we first give an overview of space complexity for PCR and a general technique for proving prove space lower bounds for random CNFs. Then we present a variant of Hall’s theorem stating that in bipartite graphs G= (L, R) with left-degree at most 3, L can be covered by certain families of disjoint paths, provided that L expands in R by a factor of (2-eps), for eps<1/5.  With this tool in hand we can capture the space lower bound for the case k=3 for random k-CNFs.
Joint work with P. Bennet, I. Bonacina. T. Huyn. M.Molloy, P. Wollan

## Winter semester 2016/2017

This semester we plan to focus on fine-grained complexity, that is reductions among problems in P and its relationship to P vs NP. The first seminar will take place on October 5th. (There will be no seminar on October 12th.)

10. 1. 2017

Open problems

Abstract: We will review the most interesting open problems we had encoutered this semester and try to solve some of them. Bring your own problems!

21. 12. 2016

Tomáš Toufar: Higher Lower Bounds from the 3SUM Conjecture

Abstract: We will present an improved reduction of 3SUM to triangle finding by Kopelowitz, Pettie and Porat.

7. and 14. 12. 2016

Abstract: We will present a paper by Amir Abboud and Virginia Williams, that shows various reductions to dynamic data-structure problem. It will turn out that fairly good lower-bounds on such problems follow from SETH, $n^{1 + \delta}$-time lower-bounds for triangle finding, $n^{2-\eps}$-time lower-bounds for 3SUM, and $n^{3-\eps}$-time lower-bounds for all-pairs shortest-paths.

23. and 30. 11. 2016

Veronika Slívová: Faster all-pairs shortest paths via circuit complexity

Abstract: We will show an algorithm for All-Pairs Shortest Path running in sub-cubic time.

9. and 16. 11. 2016

Abstract: We will show the use of polynomial method for design of fast algorithms. In the second lecture we will finish the calculations and show Coppersmith's rectangular matrix multiplication method.

2. 11. 2016

Martin Loebl: Parity Matching

Abstract: Given a graph G and p disjoint pairs of edges of G, a perfect matching of G is PARITY MATCHING if it has an even number of edges from each pair. Also given are 0,+1-1 weights on edges. I conjecture that no algorithm finds max weight of a parity matching in asymptotically less than 2^g steps. 2^g poly(n) is easy: use weighted perfect matching. The parity matching problem is hard: max-cut for graphs with g crossings can be reduced to parity matching with p= 2g pairs.

19. and 26. 10. 2016

Nitin Saurabh: Simulating Branching Programs with Edit Distance and Friends

Abstract: We will look at the reduction from SAT on branching programs to Longest Common Subsequence.  The reduction shows that obtaining a truly sub-quadratic algorithm for LCS of two sequences of length n implies that SAT on branching programs over n variables and polynomial size can be solved in (2-\delta)^n time for some \delta > 0.

5. 10. 2016

Diptarka Chakraborty: Introduction to fine-grained complexity

Abstract: Brief introduction into the fine-grained complexity: problems, ETH, SETH and friends.

## Spring semester 2015/2016

This semester we plan to mix talks on our own research with presentations of various results by others. The first seminar will take place on March 9th.

25. 5. 2016

Pavel Dvořák: Automorphism of the Cube n^d

Abstract: In this talk I will characterize all automorphisms of a hypergraph H(n,d) where the vertices are points of d-dimensional combinatorial cube n^d and the edges are all geometric lines of n^d. Moreover, I will show that the problem whether two partially colored copies of H(n,d) are automorphic is GI-complete.

18. 5. 2016

Bruno Loff: Regularity and path-extensions

Abstract: We will show two interesting pseudo-random properties of the inner product function: The regularity property is a generalization of discrepancy, which says that a sufficiently large rectangle is roughly equally split among 0s and 1s. The path-extension property provides a random-distribution over 1- or 0-monochromatic rectangles which fools large rectangles, in the sense that any large rectangle R will, with high probability, have the same density inside the monochromatic rectangle as it does in the entire space. We will then discuss some applications of these two properties.

11. 5. 2016

Matas Šileikis: Concentration of Extension Counts in G(n,p)

Abstract: Given a graph H, let X_R be the number of extensions of a fixed vertex subset R⊂[n] to a copy of H in the random graph G(n,p). In 1990 Spencer showed that with high probability for every R⊂[n] random variables X_R are concentrated in a small interval, if E (X_R) > C log n, for sufficiently large C. We study the relation between C and the size of the interval.

4. 5. 2016

Classes canceled because of rector's day.

27. 4. 2016

Hans Raj Tiwary: Extension complexity of formal languages

Abstract: In this talk I will describe a natural way to talk about extension complexity of formal languages. We will define the  class of languages that admit small extended formulations. I will mention some closure properties of this class and a sufficient machine characterization.

20. 4. 2016

Zdeněk Dvořák: Coloring H-minor-free graphs

Abstract: We will discuss the complexity of coloring graphs avoiding some (fixed) graph H as a minor.

13. 4. 2016

Elazar Goldenberg: Short random walk on regular graphs

Abstract: I will discuss our results on behaviour of short random walks on regular graphs.

30. 3. 2016

Martin Koutecký: Integer programming via Graver bases: overview, application, and open problems

Abstract: In the past 20 years, a rich theory of integer programming using Graver bases has been developed by Onn et al. I will give an overview of this theory, show an application in fixed-parameter tractability and state several interesting open problems. The talk will be self-contained; for reference see Onn's book.

23. 3. 2016

Vojta Vorel: Uncertainty and synchronization in transition systems

Abstract: I will discuss lower and upper bounds on minimum length of input sequences that avoid state uncertainty in finite-state transition systems. Several basic questions in this field remain open for a long time.

16. 3. 2016

Diptarka Chakraborty: Improved Space-Time Bound for Reachability in Directed Layered Planar Graphs

Abstract: Given a graph G and two vertices s and t in it, graph reachability is the problem of checking whether there exists a path from s to t in G. We show that reachability in directed layered planar graphs can be decided in polynomial time and O(n^eps) space, for any eps > 0. The previous best known space bound for this problem with polynomial time was approximately O(n^1/2) space.

9. 3. 2016

Pavel Hrubeš: Non-commutative circuits and the sums-of-squares problem

Abstract: I will discuss the open problem of proving lower-bounds for non-commutative arithmetic circuits. I will focus on the approach via sum-of-squares composition formulas.

## Winter semester 2015/2016

This semester we plan to organize the seminar as a reading group focused on information and communication complexity. The first meeting will take place on October 14th.

14. 10. 2015

Michal Koucky: The elements of information theory

Abstract: I will review the elementary stuff from information theory.

21. 10. 2015

Bruno Loff: The set disjointness

Abstract: I will prove a lower bound for communication complexity of disjointness via the information complexity. Notes

28. 10. 2015

Public holiday

4. 11. 2015

Bruno Loff: Pinsker inequality and its applications.

Abstract: I will prove the Pinsker inequality and show its application for correlated sampling. Notes

11. and 18. 11. 2015

Elazar Goldenberg: The communication complexity of correlation

25. 11. and 2. 12. 2015

Pavel Dvořák: Information equals amortized communication

16. 12. 2015

Karel Král: Public vs private coin in bounded-round information

13. 1. 2016

Igor Carboni Oliveira: Connections between information complexity and circuit lower bounds

### Tentative plan

1. Elazar Goldenberg - The communication complexity of correlation, by Prahladh Harsha, Rahul Jain, David McAllester, Jaikumar Radhakrishnan
2. Pavel Dvořák - Information equals amortized communication, by Mark Braverman, Anup Rao1
3. Karel Král - Public vs private coin in bounded-round information, by Mark Braverman, Ankit Garg
4. Debarati Das - How to compress interactive communication, by Boaz Barak, Mark Braverman, Xi Chen, Anup Rao
5. Martin Loebl - How to Compress Asymmetric Communication, by Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao
6. Igor Carboni Oliveira - Simplified Separation of Information and Communication, by Anup Rao, Makrand Sinha

## Summer semester 2014/2015

4. 3. 2015

Elazar Goldenberg: Local reconstructing low rank matrices

Abstract: Suppose we are given a large data matrix M and we guaranteed that it can be decomposed as: M =L+ N, where L is a low-rank matrix, and N is sparse. Can we reconstruct L efficiently? Can we do it locally (without accessing the entire matrix M)?

In this talk I'll focus on the case when the input matrix M is over a finite field F and the noise is adversarial, and the goal is to reconstruct a low-rank matrix M that (approximately) minimizes the Hamming distance to the input matrix.

11. 3. 2015

Bruno Loff: An approach towards proving n^epsilon-time data-structure lower bounds for dynamic directed-graph reachability

Abstract: We will present Mihai Patrascu's approach towards proving data-structure lower bounds for dynamic graph-reachability problems, and related communication complexity problems that arises from this approach.

18. 3. 2015

Peter Zeman: Automorphism Groups of Geometrically Represented Graphs

Abstract: We describe a technique to determine the automorphism group of a geometrically represented graph, by understanding the induced action on the structure of all geometric representations. We apply this technique to interval graphs, which are intersection graphs of closed intervals, and to circle graphs, which are intersection graphs of chords of a circle. We combine techniques from group theory (semidirect and wreath products) with data structures from computer science (PQ-trees and split trees), which encode all representations of interval and circle graphs.

25. 3. 2015

Martin Koutecký: Extended Formulation for CSP that is Compact for Instances of Bounded Treewidth

Abstract: I will present an extended formulation for a class of constraint satisfaction problems whose constraint graph has bounded treewidth. We prove that this extended formulation has polynomial size. This implies new upper bounds on extension complexity of several important NP-hard problems on graphs of bounded treewidth.

1. 4. 2015

Filip Hlásek: Explicit construction of expanders

Abstract: An expander graph is a sparse graph with strong connectivity properties. We will focus on a specific classes called unique-neighbor and odd-neighbor expanders. The ?second eigenvalue? method, which has been the main tool used in guaranteeing the expansion properties of explicitly constructed graphs, does not appear to be strong enough to prove that an infinite family of bounded-degree graphs are unique-neighbor or odd-neighbor expanders

8. 4. 2015

Dušan Knop: The structure of Hamilton paths in Interval graphs

Abstract: We present structural results about Hamilton paths in Interval graphs. It was known that it is possible to find a Hamilton path in an interval graph in linear time. By exploiting the structure, we show that it is possible to find a Hamilton path in an unit and proper interval graph in linear time even if the end vertices are specified in the input.

15. 4. 2015

Mateus de Oliveira Oliveira: The Zig-Zag number of a Digraph

Abstract: In this talk I will define the notion of zig-zag number of a digraph. I will show that many combinatorial problems that are hard on general digraphs become feasible in polynomial time on digraphs of constant zig-zag number. Subsequently, I will compare this new measure with other well know width measures for digraphs, such as directed pathwidth and directed treewidth. During the talk I will state some open problems in the field.

22. 4. 2015

Morteza Monemizadeh: Finding Large Matchings in Semi-Streaming

Abstract: In this talk we will show 2- and 3-pass semi-streaming algorithms for the problem of approximating a maximum matching in bipartite graphs. Our result is one of the first works toward resolving the space complexity of approximating the maximum matching in the semi-streaming model.

29. 4. 2015

Karel Král: Complexity of using a Memory of a Fluctuating Size

Abstract: In the external-memory model we have a main memory and a cache of a fixed size and we want to minimize both the time complexity and the number of input/output operations of an algorithm. Programs often share resources on modern computers. This leads to a natural generalization of the external-memory model where the size of allocated memory to a process may fluctuate. I will present both history of these models and our observations and ideas.

6. 5. 2015

Zdeněk Dvořák: On Planar Boolean CSP

Abstract: We give a partial classification of the complexity of Planar Boolean CSP, including a complete dichotomy for templates containing only relations of arity at most 5. (joint work with Martin Kupec)

13. 5. 2015

"Rektorský den" - classes are cancelled

20. 5. 2015

Jiří Sgall: Online Algorithms for Multi-Level Aggregation

Abstract: We study online algorithms for problems where aggregation can occur at multiple levels. Requests arrive at the nodes of a weighted tree. At any time, the algorithm may serve (transmit) all the requests in some subtree. The objective is to minimize the total waiting cost of all requests plus the weight of all transmitted subtrees. We give an algorithm for trees of depth $D$ which is $2^{O(D)}$-competitive. Previously constant-competitive algorithms were known only for $D=1,2$.