Papers from the LBCAD project

• 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

• Srinivasan A., S. Chakraborty, M. Koucký, N. Saurabh, R. de Wolf
  Improved bounds on Fourier entropy and Min-entropy.
  - arXiv:1809.09819, 2018.
  
  
• 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.
  
  

Funding info

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.