- D. Chakraborty, D. Das, E. Goldenberg, M. Koucký, M. Saks.
**Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time.**rev 0

-*59th Annual IEEE Symposium on Foundations of Computer Science*, FOCS'18, pp. 979-990, 2018,*best paper award*.

- D. Chakraborty, D. Das, M. Koucký, N. Saurabh.
**Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity**

-*26th Annual European Symposium on Algorithms*, ESA'18, 12:1-12:15, 2018.

- arXiv:1712.01834, 2017.

- B. Gärtner, T. Dueholm Hansen, P. Hubáček, K. Král, H. Mosaad, and V. Slívová
**ARRIVAL: Next Stop in CLS.**

-*45th International Colloquium on Automata, Languages and Programming, Part I,*ICALP'18, 60:1-60:13, 2018.

- A. Chattopadhyay, M. Koucký, B. Loff and S. Mukhopadhyay.
**Simulation Beats Richness: New Data-Structure Lower Bounds.**

-*50th Annual ACM Symposium on the Theory of Computing*, STOC'18, pp. 1013-1020, 2018.

- ECCC Tech Rep. TR17-170, 2017.

- D. Chakraborty, L. Kamma, and K. G. Larsen.
**Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication.**

-*50th Annual ACM Symposium on the Theory of Computing*, STOC'18, 1297-1306, 2018.

- D. Chakraborty and D. Das.
**Sparse Weight Tolerant Subgraph for Single Source Shortest Path.**

-*16th Scandinavian Symposium and Workshops on Algorithm Theory*, SWAT'18, 15:1-15:15, 2018.

- S. Chakraborty, S. Karmalkar, S. Kundu, S. V. Lokam, N. Saurabh
**Fourier Entropy-Influence Conjecture for Random Linear Threshold Functions.**

-*13th Latin American Theoretical Informatics Symposium*LATIN'18, pp. 275-289, 2018.

- D. Das, M. Koucký, and M. Saks.
**Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication.**

-*35th Symposium on Theoretical Aspects of Computer Science*, STACS'18, pp. 23:1-23:14, 2018.

- P. Dvořák, A. E. Feldmann, D. Knop, T. Masařík, T. Toufar and P. Veselý.
**Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices.**

-*35th Symposium on Theoretical Aspects of Computer Science*, STACS'18, pp. 26:1-26:15, 2018.

- Z. Dvořák.
**Thin graph classes and polynomial-time approximation schemes.**

-*29th Annual ACM-SIAM Symposium on Discrete Algorithms*, SODA'18, pp. 1685-1701, 2018.

- P. Dvořák and D. Knop.
**Parameterized complexity of length-bounded cuts and multi-cuts.**

-*Algorithmica*, pp. 1-21, 2018.

- Z. Dvořák, L. Yepremyan.
**Complete graph immersions and minimum degree.**

-*Journal of Graph Theory*, 88(1), pp. 211-221, 2017.

- arXiv::1512.00513, 2015.

- A. Chattopadhyay, P. Dvořák, M. Koucký, B. Loff and S. Mukhopadhyay
**Lower Bounds for Elimination via Weak Regularity.**

-*34th Symposium on Theoretical Aspects of Computer Science*, STACS'17, pp. 21:1-21:14, 2017.

- Z. Dvořák and B. Lidický
**Independent sets near the lower bound in bounded degree graphs.**

-*34th Symposium on Theoretical Aspects of Computer Science*, STACS'17, pp. 28:1-28:13, 2017.

- D. Chakraborty, S. Nandakumar, and H. Shukla.
**On resource-bounded versions of the van Lambalgen theorem.**

-*14th Theory and Applications of Models of Computation*, TAMC'17, pages 129-143, 2017.

- R. David, E. Goldenberg, and R. Krauthgamer.
**Local reconstruction of low‐rank matrices and subspaces.**

-*Random Structures & Algorithms*, 51(4), pp. 607-630, 2017.

- ECCC Tech Rep. TR15-128, 2015.

- P. Dvořák, E. Eiben, R. Ganian, D. Knop, and S. Ordyniak.
**Solving Integer Linear Programs with a Small Number of Global Variables and Constraints.**

-*Twenty-Sixth International Joint Conference on Artificial Intelligence*, IJCAI'2017, pp. 607-613, 2017.

- S. Buss, V. Kabanets, A. Kolokolova, and M. Koucký.
**Expanders in VNC^1**

-*Conference on Innovations in Theoretical Computer Science*, ITCS'2017, pp. 31:1-31:26, 2017.

- J. Gilmer, M.Koucký, M. Saks.
**A Communication Game Related to the Sensitivity Conjecture.**

-*Theory of Computing*13(1), pp. 1-18, 2017.

-*Preliminary version:*A New Approach to the Sensitivity Conjecture.*Conference on Innovations in Theoretical Computer Science*, ITCS'2015, pp. 247-254, 2015.

- K. Arnsfelt Hansen, R. Ibsen-Jensen, M. Koucký.
**The Big Match in Small Space.**

-*9th International Symposium on Algorithmic Game Theory*, SAGT'2016, pp. 64-76, 2016,*best paper award*.

- D. Chakraborty, E. Goldenberg, M. Koucký.
**Streaming algorithms for embedding and computing edit distance in the low distance regime.**

-*48th Annual ACM Symposium on Theory of Computing*, STOC'16, pp. 712-725.

- P. Dvořák and T. Valla.
**Automorphisms of the Cube.**

-*22nd International Conference on Computing and Combinatorics*, COCOON'2016, pp. 405-416, 2016.

- M. Koucký.
**Catalytic computation.**

-*Bulletin of the EATCS*118 (2016).

- Z. Dvořák, S. Norin.
**Strongly sublinear separators and polynomial expansion.**

- SIAM J. Discrete Math. 30 (2016), 1095-1101.

- H. Buhrman, M. Koucký, B. Loff, F. Speelman.
**Catalytic Space: Non-determinism and Hierarchy.**

-*Theory Comput. Syst.*62(1): 116-135, 2018. (special issue for STACS'16)

-*33rd Symposium on Theoretical Aspects of Computer Science*, STACS'16, pp. 24:1-24:13, 2016.

- J. Bulánek, M. Koucký, and M. Saks.
**Tight lower bounds for the online labeling problem.**

-*SIAM Journal on Computing*, 44(6):1765-1797, 2015.

- M. Agrawal, D. Chakraborty, D. Das, S. Nandakumar.
**Dimension, Pseudorandomness and Extraction of Pseudorandomness.**

-*35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science*, FSTTCS 2015, pp. 221-235, 2015.

- H. Buhrman, E. Cleve, M. Koucký, B. Loff, F. Speelman.
**Computing with a full memory: Catalytic space.**

-*46th Annual ACM Symposium on Theory of Computing*, STOC'14, pp. 857-866, 2014.

### Preprints

- Z. Dvořák, X. Hu.
**Planar graphs without cycles of length 4 or 5 are (11:3)-colorable.**

- arXiv:1802.04179, 2018.

- A. Chattopadhyay, M. Koucký, B. Loff and S. Mukhopadhyay
**Simulation Theorems via Pseudorandom Properties.**

- arXiv:1704.06807, 2017.

- earlier version: ECCC Tech Rep. TR17-14, 2017.

- D. Chakraborty, E. Goldenberg, M. Koucký.
**Streaming Algorithms For Computing Edit Distance Without Exploiting Suffix Trees.**

- arXiv:1607.03718, 2016.

- V. Girard, M. Koucký, P. McKenzie.
**Nonuniform catalytic space and the direct sum for space.**

- ECCC Tech Rep. TR15-138,2015.

- D. Chakraborty.
**Information Complexity for Multiparty Communication.**

- ECCC Tech Rep. TR14-132, 2015.

### Thesis

- K. Král.
**Data structure behavior with variable cache size.**

- Master Thesis, Charles University, 2017.

- F. Hlásek.
**Bounds on existence of odd and unique expanders.**

- Master Thesis, Charles University, 2016.

The research leading to these results has received funding from the European Research Council under the European Union's Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement n. 616787. |