(Seminář o limitech efektivních výpočtů)

Michal Koucký`<koucky@iuuk.mff.cuni.cz>`

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

**29. 3. 2017 **

**Nitin Saurabh: Fourier Entropy-Influence Conjecture**

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

**15. 3. 2017 **

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

**Abstract:**
I'll survey a variety of connections between non-uniform circuit
lower bounds, non-trivial proof systems, non-trivial learning algorithms,
and variants of natural properties. In particular, I plan to discuss how one
can prove new unconditional lower bounds for standard complexity classes
such as REXP, ZPEXP, BPEXP, and NEXP by designing algorithms with a
non-trivial running time, and to present some open problems.

**8. 3. 2017 **

**Diptarka Chakraborty: Computing edit distance without suffix trees
space**

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

**1. 3. 2017 **

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

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

Joint work with P. Bennet, I. Bonacina. T. Huyn. M.Molloy, P. Wollan

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