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

Michal Koucký and Pavel Hubáček

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 2019/2020

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

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.

Winter semester 2019/2020

This semester we plan to focus on distributed algorithms and fine-grained complexity in cryptography. We will present several results in those directions. The first seminar will be held on Oct. 9.

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.

List of possible papers to present

Fine-Grained Cryptography
Distributed computation

Spring semester 2018/2019

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

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.

Winter semester 2018/2019

This semester we plan to focus on Probabilistically Checkable Proofs (PCPs) and their many applications in hardness of approximation, fine-grained complexity and cryptography. We will present several results in those directions.

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.

Assigned papers

List of further possible papers


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.

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.

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

List of possible papers

Additional resources

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

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

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

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.

List of assigned papers

List of more papers

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

Further papers

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