(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.

**4. 3. 2020**

**CANCELED due to another event**

**Abstract:**
At 11:00am, László Lovász will receive the degree Doctor Honoris Causa of Charles University in Carolinum. All are welcome to attend.

**26. 2. 2020**

**Václav Rozhoň (ETH): Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization**

**Abstract:**
We will present a simple polylogarithmic-time deterministic distributed algorithm for network decomposition with applications to derandomization of distributed algorithms. Joint work with Mohsen Ghaffari, to appear at STOC 2020.

**18. 12. 2019**

**Pavel Veselý (Warwick University): Minimum spanning tree in dynamic geometric streams**

**Abstract:**
I will show a sampling-based streaming algorithm by Frahling, Indyk, and Sohler that estimates the weight of the Euclidean minimum spanning tree
for a set of points given by a dynamic geometric stream (i.e., a sequence of insertions and deletions of points in R^d).

**18. 12. 2019**

**Pavel Hubáček: A Minimal Model for Secure Computation**

**Abstract:**
I will show the Feige-Kilian-Naor secure computation scheme, where an untrusted server computes securely a function of client's inputs in one shot.

**4. and 18. 12. 2019**

**Tung Anh Vu: Distributed algorithms made secure: a graph theoretic approach**

**Abstract:**
I will present another result of Parter and Yogev on securing distributed computation.

**27. 11. 2019**

**Pankaj Kumar: Low congestion cycle covers and their applications**

**Abstract:**
I will present an algorithm for finding a cycle cover by Parter and Yogev.

**20. 11. 2019**

**Kristoffer Arnsfelt Hansen (Aarhus University): Computational Complexity of Proper Equilibrium**

**Abstract:**
In this presentation I will talk about computing *proper* Nash equilibrium.

**13. 11. 2019**

**Davis Issac: Local conflict coloring**

**Abstract:**
I will present an algorithm for breaking symmetry and coloring in the distributed setting by Fraigniaud, Heinrich and Kosowki.

**6. 11. 2019**

**Michal Koucký: Locality in Distributed Graph Algorithms**

**Abstract:**
I will present an lower and upper bounds for coloring in the distributed setting
by Linial.

**30. 10. 2019**

**Michal Opler: An Improved Distributed Algorithm for Maximal Independent Set**

**Abstract:**
I will present an algorithm for maximal independent set in the distributed setting
by Ghaffari.

**23. 10. 2019**

**Karel Král: Lower bounds for maximal matchings and maximal independent sets**

**Abstract:**
I will present a lower bound for maximal matching in the distributed setting
by Balliu,Brandt, Hirvonen, Olivetti, Rabie and Suomela.

**16. 10. 2019**

**Zdeněk Dvořák: The sensitivity conjecture**

**Abstract:**
I will present the proof of the Sensitivity conjecture by Hao Huang.

**9. 10. 2019**

**Pavel Hubáček: On the basics of fine-grained crypto**

**Abstract:**
I will describe how to build public-key cryptography against subquadratic adversaries based on Merkle puzzles and a more recent extension of these ideas based on the work of Biham, Goren, and Ishai.

- Zdeněk Dvořák - Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture, by Hao Huang

- Pavel Dvořák - Public-Key Cryptography in the Fine-Grained Setting, by Rio Lavigne and Andrea Lincoln and Virginia Vassilevska Williams
- Fine-grained cryptography, by Akshay Degwekar, Vinod Vaikuntanathan, Prashant Nalini Vasudevan
- Veronika Slívová - Average-case fine-grained hardness, by Marshall Ball, Alon Rosen, Manuel Sabin, Prashant Nalini Vasudevan
- Karel Král - Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning, by Ran Raz

- Karel Král - Lower bounds for maximal matchings and maximal independent sets, by Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, Jukka Suomela
- Davis Issac - Local conflict coloring, by P. Fraigniaud, M. Heinrich, A. Kosowki
- Michal Opler - An Improved Distributed Algorithm for Maximal Independent Set, by Mohsen Ghaffari
- The locality of distributed symmetry breaking, by Leonid Barenboim, Michael Elkin, Seth Pettie, Johannes Schneider
- Parallel Reachability in Almost Linear Work and Square Root Depth, by Arun Jambulapati, Yang P. Liu, Aaron Sidford
- Tung Anh Vu Distributed algorithms made secure: a graph theoretic approach, by Merav Parter, Eylon Yogev
- The Power of Distributed Verifiers in Interactive Proofs, by Moni Naor, Merav Parter, Eylon Yogev

- Secure communications over insecure channels, by Ralph C. Merkle
- Basing Weak Public-Key Cryptography on Strong One-Way Functions, by Eli Biham, Yaron J. Goren, and Yuval Ishai
- Pankaj Kumar - Low congestion cycle covers and their applications, by Merav Parter, Eylon Yogev
- An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model, by Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie.
- Distributed local approximation algorithms for maximum matching in graphs and hypergraphs, by David G. Harris

**22. 5. 2019**

**Davis Issac: Generalized Györi-Lovász Theorem and Spanning Tree Congestion**

**Abstract:**
I will give a proof a generalization of a classical theorem in the
area of graph connectivity known as Györi-Lovász theorem, and also show its
application to get bounds for a graph parameter called spanning tree
congestion.

**15. 5. 2019**

** Ashutosh Rai: FPT Algorithm for Mixed Cut and application to Strong Bipartite Deletion**

**Abstract:**
I will introduce a cut problem called Mixed Cut, where, given a source and a sink, one is allowed to delete both vertices and edges to separate them. I will give a short NP-completeness reduction and then I will show that the problem is FPT using the technique of Randomized Contractions given by Chitnis et al. [FOCS 2012]. If time permits, I will go into a problem called Strong Bipartite Deletion, the algorithm for which uses the FPT algorithm for Mixed Cut as a subroutine. This is based on joint work with M. S. Ramanujan and Saket Saurabh.

**24. 4. 2019**

**Andreas Feldmann: Travelling on Graphs with Small Highway Dimension**

**Abstract:**
We study the Travelling Salesperson (TSP) and the Steiner Tree problem (STP) in graphs of low highway dimension. This graph parameter was introduced by Abraham et al. [SODA 2010] as a model for
transportation networks, on which TSP and STP naturally occur for various applications in logistics. It was previously shown [Feldmann et al. ICALP 2015] that these problems admit a quasi-polynomial
time approximation scheme (QPTAS) on graphs of constant highway dimension. We demonstrate that a significant improvement is possible in the special case when the highway dimension is 1, for which we
present a fully-polynomial time approximation scheme (FPTAS). We also prove that STP is weakly NP-hard for these restricted graphs. For TSP we show NP-hardness for graphs of highway dimension 6, which
answers an open problem posed in [Feldmann et al. ICALP 2015].

Joint work with Yann Disser, Max Klimm, and Jochen Könemann.

**3. and 17. 4. 2019**

**Pavel Hubáček: Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir**

**Abstract:**
I will present a conditional lower bound for finding a Nash equilibrium
assuming that 1) the Fiat-Shamir heuristic is sound for the sumcheck
protocol and 2) there exists a worst-case hard problem in #P.
Based on joint work with A.R. Choudhuri, C. Kamath, K. Pietrzak, A. Rosen
and G. N. Rothblum.

**27. 3. 2019**

**Pavel Hrubeš: Compression schemes and the Continuum Hypothesis**

**Abstract:**
The Continuum Hypothesis is a conjecture about the cardinality of the set of real numbers. As such, it is a classical problem known to be undecidable from the usual ZFC axioms. We will show that some problems arising in the context of machine learning are equivalent to variants of CH - and hence undecidable over ZFC. (Based on joint work with S. Ben-David, S. Moran, A. Shpilka, A. Yehudayoff)

**13. 3. 2019**

**Navid Talebanfard (Math Inst.): A Separator Theorem for Hypergraphs and DPLL Refutations of CSPs**

**Abstract:**
I will show how to remove a small set of edges of a hypergraph to break it into small connected components and how to use it to refute unsatisfiable CSPs in which no variable occurs in too many constraints.
This is joint work with Vojtěch Rödl.

**6. 3. 2019**

**Karel Král: Stronger lower bounds for oblivious RAM**

**Abstract:**
I will present stronger lower bounds for oblivious RAM than the recently proved bounds of Larsen and Nielsen.

**20. & 27. 2. 2019 **

**Dima Gavinsky (Math Inst.): 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. We study 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.

**9. 1. 2019 **

**Matej Lieskovský: Counting t-cliques: Worst-Case to Average-Case Reductions**

**Abstract:**
I will present a result on worst-case hardness to average-case hardness reductions.

**19. 12. 2018 **

**Sagnik Mukhopadhyay: Equality alone does not simulate randomness**

**Abstract:**
I will present a fresh result of Chattopadhyay, Lovett and Vinyals that randomness in communication protocols cannot be replaced by an oracle for equality.

**12. 12. 2018 **

**Raul Gonzalez: A proof of the GM-MDS conjecture**

**Abstract:**
We will show the recent result of
Shachar Lovett on the existence of matrices with lots of zeros generating good codes.

**28. 11. 2018 **

**Jakub Tětek: Derandomizing Local Distributed Algorithms**

**Abstract:**
I will show a recent technique of Ghaffari, Harris and Kuhn on how to derandomize local distributed algorithms.

**21. 11. 2018 **

**Pavel Hubáček: Oblivious RAM construction**

**Abstract:**
I will present an oblivious RAM construction by Goldreich and Ostrovsky.

**7. and 14. 11. 2018 **

**Veronika Slívová: Yes, There is an Oblivious RAM Lower Bound!**

**Abstract:**
We will see a lower bound on the time overhead for Oblivious RAM (i.e. a model of computation in which you are trying to hide the memory access pattern).
This is based on work of Kasper Green Larsen and Jesper Buus Nielsen.

**31. 10. 2018 at 6pm (Prague time)**

**Michal Koucky: Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time**

**Abstract:**
I will talk about a sub-quadratic constant factor approximation algorithm for edit distance. Notice the time change.

**24. 10. 2018 **

**Karel Král: Conditional Information Inequalities and Combinatorial Applications**

**Abstract:**
I will present non-Shannon type information inequalities and their applications in combinatorics by Kaced, Romashchenko and Vereshchagin.

**17. 10. 2018 **

**Pavel Hubáček: Introduction to PCP**

**Abstract:**
I will make a brief overview of Probabilistically Checkable Proofs (PCP's) and their applications.

**10. and 17. 10. 2018 **

**Pavel Dvořák: Distributed PCP Theorems for Hardness of Approximation in P**

**Abstract:**
We will discuss how Strong exponential time hypothesis relates with approximations in P. In particular, we will show a reduction from SAT to Bichromatic Max-IP, where there are two sets A and B of
vectors at the input and we want to find a pair x in A and y in B such that they maximize the inner product. The core of the reduction is an effective MA-protocol for Disjointness, which is interesting by
its own.

- Matej Lieskovský: Counting t-cliques: Worst-Case to Average-Case Reductions and Direct Interactive Proof Systems, by Oded Goldreich, Guy N. Rothblum.

- How NP got a new definition: a survey of probabilistically checkable proofs, by Sanjeev Arora.
- The PCP theorem by gap amplification, by Irit Dinur.
- Simple PCPs with poly-log rate and query complexity, by Eli Ben-Sasson, Madhu Sudan.
- Locally testable codes and PCPs of almost-linear length, Oded Goldreich, Madhu Sudan.

- SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge, by Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, Madars Virza.
- Scalable, transparent, and post-quantum secure computational integrity, by Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, Michael Riabzev.
- Interactive proofs of proximity: delegating computation in sublinear time, by Guy N. Rothblum, Salil P. Vadhan, Avi Wigderson.
- Constant-round interactive proofs for delegating computation, by Omer Reingold, Guy N. Rothblum, Ron D. Rothblum.
- Efficient Batch Verification for UP, by Omer Reingold, Guy N. Rothblum, Ron D. Rothblum.
- Delegating Computations with (almost) Minimal Time and Space Overhead, by Justin Holmgren and Ron D. Rothblum.

- Distributed PCP Theorems for Hardness of Approximation in P, by Amir Abboud, Aviad Rubinstein, Ryan Williams.
- Fine-grained Complexity Meets IP = PSPACE, by Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy N. Rothblum, Aviad Rubinstein.

- Deterministic Document Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors, by Kuan Cheng, Zhengzhong Jin, Xin Li, Ke Wu.
- PanORAMa: Oblivious RAM with Logarithmic Overhead, by Sarvar Patel, Giuseppe Persiano, Mariana Raykova and Kevin Yeo.

**16. 5. 2018 **

**Pavel Dvořák: Parameterized approximation scheme for Steiner Tree Problem**

**Abstract:**
We will discuss parameterized approximation scheme of Steiner Tree parameterized by the number of Steiner vertices in the optimal solution. I will talk about complexity of several version of this problem - unweighted/weighted and undirected/directed. The main presented result will be parameterized approximation scheme for Weighted Undirected Steiner Tree.

**9. 5. 2018 **

**Pavel Veselý: Online bounded-delay packet scheduling**

**Abstract:**
We will discuss online algorithms for scheduling unit-length packets with weights and deadlines, which are arriving over time to a buffer. In particular, we will show some progress on the open question, whether there is a deterministic algorithm with competitive ratio equal to the golden ratio (approx. 1.618), or not.

**18. 4. 2018 **

**Navid Talebanfard (Math Inst.): Cops-robber games and the resolution of Tseitin formulas**

**Abstract:**
We connect game characterizations of several complexity measures in resolution to cops-robber games on graphs. We use this to show that with respect to these measures (e.g., width, variable space) regular resolution is optimal. This answers a question of Urquhart. Joint work with Nicola Galesi and Jacobo Toran.

**11. 4. 2018 **

**Andreas Feldmann: Parametrized complexity of k-center problem**

**Abstract:**
I will present our new results on parameterized hardness of the k-center problem in transportation networks.

**4. 4. 2018 **

**Miloš Chromý: Biclique Satisfiability**

**Abstract:**
The talk will be about biclique satisfiability. This problem is closely related to covering incidence (bipartite) graph of a CNF formula by bounded
bicliques. We will compare two encodings to SAT and show a heurisic algorithm for this problem.

**21. 3. 2018 **

**Diptarka Chakraborty: Quasi-Gray Code: Efficient Generation and Optimality**

**Abstract:**
We will discuss a lower bound on read complexity of generating space-optimal quasi-Gray code and also see a construction of a near-optimal code.

**7. 3. 2018 **

**Pavel Hubáček: Constant-round protocols for statistical zero-knowledge**

**Abstract:**
We will show how to overcome technical issues when designing constant-round protocols for statistical zero-knowledge.

**28. 2. 2018 **

**Veronika Slívová: Reachability problems on switch graphs**

**Abstract:**
The talk will explain our recent results on the reachability problem on switch graphs.

**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.

**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).

- On the Complexity of Scrypt and Proofs of Space in the Parallel Random Oracle Model, by Alwen, Chen, Kamath, Kolmogorov, Pietrzak, and Tessaro.
- Be Adaptive, Avoid Overcommitting, by Jafargholi, Kamath, Klein, Komargodski, Pietrzak, and Wichs.

- New Wine into Old Wineskins: A Survey of Some Pebbling Classics with Supplemental Results, by Nordstrom.
- Network Coding: An Introduction, by Ho, Lun.
- Network Coding Fundamentals, by Fragouli, Soljanin.

**24. 5. 2017 **

**Karel Král: Cache adaptive algorithms**

**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 (Math Inst.): 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 (Sapienza, University of Rome): 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

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

**Bruno Loff: Popular conjectures imply strong lower bounds for dynamic problems**

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

**Karel Král: More Applications of the Polynomial Method to Algorithm Design**

**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.

- Nitin Saurabh (19. & 26.10.): Simulating Branching Programs with Edit Distance and Friends or: A Polylog Shaved is a Lower Bound Made, by Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Ryan Williams.
- Karel Král (cca 9.11.): More Applications of the Polynomial Method to Algorithm Design, by Amir Abboud, Ryan Williams, Huacheng Yu.
- Veronika Slívová (cca 16.11.): Faster all-pairs shortest paths via circuit complexity, by Ryan Williams.
- Bruno Loff (7.12): Popular conjectures imply strong lower bounds for dynamic problems, by Amir Abboud, Virginia Vassilevska Williams.
- Tomáš Toufar (cca 21.12.): Higher Lower Bounds from the 3SUM Conjecture, by Tsvi Kopelowitz, Seth Pettie, Ely Porat.

- Faster Online Matrix-Vector Multiplication, by Kasper Green Larsen, Ryan Williams.
- Quadratic-Time Hardness of LCS and other Sequence Similarity Measures, by Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams.
- Subcubic Equivalences Between Path, Matrix, and Triangle Problems, by Virginia Vassilevska Williams, Ryan Williams.
- Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter, by Amir Abboud, Fabrizio Grandoni, Virginia Vassilevska Williams.
- On a class of O(n^2) problems in computational geometry, by Anka Gajentaan, Mark H. Overmars.
- Finding a Heaviest Triangle is not Harder than Matrix Multiplication, by Artur Czumaj, Andrzej Lingas.
- Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture, by Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, Thatchaphol Saranurak.
- Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility, by Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mikhailin, Ramamohan Paturi, Stefan Schneider.
- Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation, by Ryan Williams.
- Towards Polynomial Lower Bounds for Dynamic Problems, by Mihai Patrascu.
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false), by Arturs Backurs, Piotr Indyk.
- Finding Orthogonal Vectors in Discrete Structures, by Ryan Williams, Huacheng Yu.
- Better approximation algorithms for the graph diameter, by Shiri Chechik, Daniel Larkin, Liam Roditty, Grant Schoenebeck, Robert Endre Tarjan, and Virginia Vassilevska Williams.
- Quadratic conditional lower bounds for string problems and dynamic time warping, by Karl Bringmann, Marvin Künnemann.

**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.

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

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

- An interactive information odometer with applications. Mark Braverman, Omri Weinstein
- Interactive information complexity. Mark Braverman
- Relative Discrepancy does not separate Information and Communication Complexity. Lila Fontes, Rahul Jain, Iordanis Kerenidis, Mathieu Lauriere, Sophie Laplante, and Jeremie Roland
- Lower bounds on information complexity via zero-communication protocols and applications. Iordanis Kerenidis, Sophie Laplante, Virginie Lerays, Jérémie Roland, David Xiao
- From Information to Exact Communication. Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein
- Lower Bounds for Clique vs. Independent Set. Mika Göös
- The Landscape of Communication Complexity Classes. Mika Göös, Toniann Pitassi, Thomas Watson
- Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication. Mika Göös, Toniann Pitassi, Thomas Watson
- Reliable Communication over Highly Connected Noisy Networks. Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler
- Tribes Is Hard in the Message Passing Model. Arkadev Chattopadhyay, Sagnik Mukhopadhyay

**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 (Math Inst.): 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$.