- P. Dvořák, D. Knop, T. Toufar.
**Target Set Selection in Dense Graph Classes**

-*The 29th International Symposium on Algorithms and Computation*, ISAAC'18, pp. 18:1-18:13, 2018.

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

**D. Das.****New Bounds for Combinatorial Problems and Quasi-Gray Codes.**

- PhD Thesis, Charles University, submitted 2019.

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