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