EPAC: Efficient approximation algorithms and circuit complexity

Papers

• P. Pudlák.
  On matrices potentially useful for tree codes.
  - Inf. Process. Lett. 174: 106180 (2022)
  
  
• S. Arunachalam, S. Chakraborty, M. Koucký, N. Saurabh, R. de Wolf.
  Improved Bounds on Fourier Entropy and Min-entropy.
  - ACM Trans. Comput. Theory 13(4): 22:1-22:40 (2021)
  
  
• V. Cohen-Addad, A.E. Feldmann, D. Saulpic.
  Near-linear Time Approximation Schemes for Clustering in Doubling Metrics.
  - J. ACM 68(6): 44:1-44:34 (2021)
  
  
• Y. Disser, A.E. Feldmann, M. Klimm, J. Könemann.
  Travelling on Graphs with Small Highway Dimension.
  - Algorithmica 83(5): 1352-1370 (2021)
  
  
• A.E. Feldmann, D. Saulpic.
  Polynomial time approximation schemes for clustering in low highway dimension graphs.
  - J. Comput. Syst. Sci. 122: 72-93 (2021)
  
  
• D. Gavinsky.
  Bare Quantum Simultaneity Versus Classical Interactivity in Communication Complexity.
  - IEEE Trans. Inf. Theory 67(10): 6583-6605 (2021)
  
  
• D. Gavinsky.
  The Layer Complexity of Arthur-Merlin-like Communication.
  - Theory Comput. 17: 1-28 (2021)
  
  
• D. Knop, M. Koutecký, A. Levin, M. Mnich, S. Onn.
  Parameterized complexity of configuration integer programs.
  - Oper. Res. Lett. 49(6): 908-913 (2021)
  
  
• M. Bienkowski, M. Böhm, J. Byrka, M. Chrobak, C. Dürr, L. Folwarczny, L. Jez, J. Sgall, N. Kim Thang, P. Veselý.
  New results on multi-level aggregation.
  - Theor. Comput. Sci. 861: 133-143 (2021)
  
  
• M. Koutecký, S. Onn.
  Uniform and monotone line sum optimization.
  - Discret. Appl. Math. 298: 165-170 (2021)
  
  
• M. Koucký, V. Rödl, N. Talebanfard.
  A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm.
  - Logical Methods in Computer Science, Volume 17, Issue 4, 2021, pp. 17:1–17:14
  
  
• P. Dvořák, A.E. Feldmann, D. Knop, T. Masarík, T. Toufar, P. Veselý.
  Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices.
  - SIAM J. Discret. Math. 35(1): 546-574 (2021)
  
  
• P. Dvořák, T. Valla.
  Automorphisms of the cube nd.
  - Discret. Math. 344(3): 112234 (2021)
  
  
• P. Pudlák.
  The canonical pairs of bounded depth Frege systems.
  - Ann. Pure Appl. Log. 172(2): 102892 (2021)
  
  
• P. Veselý.
  Packet Scheduling: Plans, Monotonicity, and the Golden Ratio.
  - SIGACT News 52(2): 72-84 (2021)
  
  
• R. Chitnis, A. E. Feldmann, P. Manurangsi.
  Parameterized Approximation Algorithms for Bidirected Steiner Network Problems.
  - ACM Trans. Algorithms 17(2): 12:1-12:68 (2021)
  
  
• S. Borgwardt, C. Brand, A. E. Feldmann, M. Koutecký.
  A Note on the Approximability of Deepest-Descent Circuit Steps.
  - Oper. Res. Lett. 49(3): 310-315 (2021)
  
  
• S. Buss, V. Kabanets, A. Kolokolova, M. Koucký.
  Expander construction in VNC1.
  - Ann. Pure Appl. Log. 171(7): 102796 (2020)
  
  
• A. E. Feldmann, Karthik C. S., E. Lee, P. Manurangsi.
  A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms.
  - Algorithms 13(6): 146 (2020)
  
  
• D. Gavinsky.
  The Communication Complexity of the Inevitable Intersection Problem.
  - Chicago Journal of Theoretical Computer Science, Article 3, 2020.
  
  
• D. Gavinsky, P. Pudlák:
  Santha-Vazirani sources, deterministic condensers and very strong extractors.
  - Theory of Computing Systems, 64(6): 1140-1154 (2020)
  
  
• P. Hrubeš.
  On the distribution of runners on a circle.
  - European Journal of Combinatorics, 89: 103137 (2020)
  
  
• P. Hrubeš.
  On \epsilon-sensitive monotone computations.
  - Computational Complexity 29(2): 6 (2020)
  
  
• P. Kolman, M. Koutecký, H. R. Tiwary.
  Extension Complexity, MSO Logic, and Treewidth.
  - Discret. Math. Theor. Comput. Sci. 22(4) (2020)
  
  
• D. Knop, M. Koutecký, M. Mnich.
  Voting and Bribing in Single-Exponential Time.
  - ACM Trans. Economics and Comput. 8(3): 12:1-12:28 (2020)
  
  
• T. Gavenčiak, D. Knop, M. Koutecký.
  Integer programming in parameterized complexity: Five miniatures.
  - Discrete Optimization (2020): 100596.
  
  
• D. Chakraborty, D. Das, E. Goldenberg, M. Koucký, M. E. Saks.
  Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time.
  - J. ACM 67(6): 36:1-36:22 (2020)
  
  
• D. Gavinsky.
  Quantum Versus Classical Simultaneity in Communication Complexity.
  - IEEE Trans. Information Theory 65(10): 6466-6483 (2019)
  
  

Conferences

• P. Dvořák, M. Koucký, K. Král, V. Slívová.
  Data Structures Lower Bounds and Popular Conjectures.
  - 29th Annual European Symposium on Algorithms, ESA 2021: 39:1-39:15
  
  
• A.E. Feldmann, A. Rai.
  On Extended Formulations For Parameterized Steiner Trees.
  - 16th International Symposium on Parameterized and Exact Computation, IPEC 2021: 18:1-18:16
  
  
• M. Bienkowski, M. Böhm, M. Koutecký, T. Rothvoß, J. Sgall, P. Veselý.
  Improved Analysis of Online Balanced Clustering.
  - 19th International Workshop on Approximation and Online Algorithms, WAOA 2021: 224-233
  
  
• P. Hubáček, J. Václavek.
  On Search Complexity of Discrete Logarithm.
  - 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021: 60:1-60:16
  
  
• P. Hrubeš, A. Yehudayoff.
  Shadows of Newton Polytopes.
  - Computational Complexity Conference, CCC 2021: 9:1-9:23
  
  
• A. Antoniadis, M. Englert, N. Matsakis, P. Veselý.
  Breaking the Barrier Of 2 for the Competitiveness of Longest Queue Drop.
  - 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021: 17:1-17:20
  
  
• M. Koucký, K. Král.
  Sorting Short Integers.
  - 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021: 88:1-88:17
  
  
• G. Cormode, A. Mishra, J. Ross, P. Veselý.
  Theory meets Practice at the Median: A Worst Case Comparison of Relative Error Quantile Algorithms.
  - 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2021: 2722-2731
  
  
• V. Blažej, P. Dvořák, M. Opler.
  Bears with Hats and Independence Polynomials.
  - 47th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2021: 283-295
  
  
• P. Dvořák, M. Koucký.
  Barrington Plays Cards: The Complexity of Card-Based Protocols.
  - 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021: 26:1-26:17
  
  
• C. Brand, M. Koutecký, S. Ordyniak.
  Parameterized Algorithms for MILPs with Small Treedepth.
  - Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021: 12249-12257
  
  
• M. Koutecký, N. Talmon.
  Multi-Party Campaigning.
  - Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021: 5506-5513
  
  
• M. Koutecký, J. Zink.
  Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines.
  - 31st International Symposium on Algorithms and Computation, ISAAC 2020: 18:1-18:17, 2020.
  
  
• D. Issac, A. E. Feldmann, A. Rai
  Fixed-Parameter Tractability of the Weighted Edge Clique Partition Problem.
  - 15th International Symposium on Parameterized and Exact Computation, IPEC 2020: 17:1-17:16, 2020.
  
  
• P. Dvořák, B. Loff.
  Lower Bounds for Semi-adaptive Data Structures via Corruption.
  - 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2020: 20:1-20:15, 2020.
  
  
• P. Hubáček, C. Kamath, K. Král, V. Slívová.
  On Average-Case Hardness in TFNP from One-Way Functions.
  - 18th International Conference on Theory of Cryptography, TCC 2020: 614-638, 2020.
  
  
• A. E. Feldmann, D. Saulpic.
  Polynomial Time Approximation Schemes for Clustering in Low Highway Dimension Graphs.
  - 28th Annual European Symposium on Algorithms, ESA 2020: 46:1-46:22, 2020.
  
  
• Lin Chen, M. Koutecký, Lei Xu, Weidong Shi.
  New Bounds on Augmenting Steps of Block-Structured Integer Programs.
  - 28th Annual European Symposium on Algorithms, ESA 2020: 33:1-33:19, 2020.
  
  
• D. Scheder, N. Talebanfard.
  Super Strong ETH is true for PPSZ with small resolution width.
  - 35th Computational Complexity Conference, CCC 2020: 3:1-3:12, 2020.
  
  
• T. F. N. Chan, J. W. Cooper, M. Koutecký, D. Král', K. Pekárková.
  Matrices of Optimal Tree-Depth and Row-Invariant Parameterized Algorithm for Integer Programming.
  - 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020: 26:1-26:19, 2020.
  
  
• S. Datta, P. Kumar, A. Mukherjee, A. Tawari, N. Vortmeier, T. Zeume:
  Dynamic Complexity of Reachability: How Many Changes Can We Handle?
  - 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020: 122:1-122:19, 2020.
  
  
• D. Gavinsky.
  Bare Quantum Simultaneity Versus Classical Interactivity in Communication Complexity.
  - 52nd Symposium on Theory of Computing, STOC 2020, 401-411, 2020.
  
  
• M. Koucký, M. E. Saks.
  Constant factor approximations to edit distance on far input pairs in nearly linear time.
  - 52nd Symposium on Theory of Computing STOC 2020, 699-712, 2020.
  
  
• P. Dvořák, A. E. Feldmann, A. Rai, P. Rzążewski.
  Parameterized Inapproximability of Independent Sets in H-Free Graphs.
  - 46th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2020: 40-53, 2020.
  
  
• S. Arunachalam, S. Chakraborty, M. Koucký, N. Saurabh, R. de Wolf.
  Improved Bounds on Fourier Entropy and Min-Entropy.
  - 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, 45:1-45:19, 2020.
  
  
• D. Gavinsky, T. Lee, M. Santha, and S. Sanyal.
  A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity.
  - 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019: 64:1-64:13
  
  
• D. Chakraborty, D. Das, and M. Koucký.
  Approximate Online Pattern Matching in Sublinear Time.
  - 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS'19, pp. 10:1-10:15, 2019.
  
  
• P. Hubáček, M. Koucký, K. Král, and V. Slívová.
  Stronger Lower Bounds for Online ORAM.
  - 17th Theory of Cryptography Conference, TCC 2019, pp. 264-284, 2019.
  
  
• P. Hrubeš, S.N. Ramamoorthy, A. Rao, and A. Yehudayoff.
  Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits.
  - 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019: 72:1-72:14
  
  
• R. Chitnis and A.E. Feldmann.
  FPT Inapproximability of Directed Cut and Connectivity Problems.
  - 14th International Symposium on Parameterized and Exact Computation, IPEC 2019: 8:1-8:20.
  
  

Preprints

• P. Frankl, S. Gryaznov, N. Talebanfard.
  A Variant of the VC-dimension with Applications to Depth-3 Circuits.
  - arXiv CoRR abs/2111.09671 (2021)
  
  
• C. Brand, M. Koutecký, A. Lassota, S. Ordyniak.
  Sometimes, Convex Separable Optimization Is Much Harder than Linear Optimization, and Other Surprises.
  - arXiv CoRR abs/2111.08048 (2021)
  
  
• A.E. Feldmann, A. Mukherjee, E. Jan van Leeuwen.
  The Parameterized Complexity of the Survivable Network Design Problem.
  - arXiv CoRR abs/2111.02295 (2021)
  
  
• M. Englert, N. Matsakis, P. Veselý.
  Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios.
  - arXiv CoRR abs/2111.03968 (2021)
  
  
• P. Hrubeš, N. Talebanfard.
  On the extension complexity of polytopes separating subsets of the Boolean cube.
  - arXiv CoRR abs/2105.11996 (2021)
  
  
• A. Czumaj, S. H.-C. Jiang, R. Krauthgamer, P. Veselý.
  Streaming Algorithms for Geometric Steiner Forest.
  - arXiv CoRR abs/2011.04324 (2020)
  
  
• P. Pudlák:
  On matrices potentially useful for tree codes.
  - arXiv CoRR abs/2012.03013 (2020)
  
  
• S. Borgwardt, C. Brand, A. E. Feldmann, M. Koutecký.
  A Note on the Approximability of Deepest-Descent Circuit Steps.
  - arXiv CoRR abs/2010.10809 (2020)
  
  
• P. Dvořák, M. Koucký.
  Barrington Plays Cards: The Complexity of Card-based Protocols.
  - arXiv CoRR abs/2010.08445 (2020)
  
  
• P. Hrubeš, A. Yehudayoff.
  Shadows of Newton polytopes.
  - Electronic Colloquium on Computational Complexity (ECCC) Tech Rep. TR20-189 (2020)
  
  
• P. Pudlák
  Reflection principles, propositional proof systems, and theories.
  - arXiv CoRR abs/2007.14835 (2020)
  
  
• E. Khaniki.
  On Proof complexity of Resolution over Polynomial Calculus.
  - Electronic Colloquium on Computational Complexity (ECCC) Tech Rep. TR20-034 (2020)
  
  
• E. Khaniki.
  Not all Kripke models of HA are locally PA.
  - arXiv CoRR abs/2006.11910 (2020)
  
  
• M. Koutecký, Nimrod Talmon.
  Multi-Party Campaigning.
  - arXiv CoRR abs/2005.04455 (2020)
  
  
• D. Knop, M. Koutecký.
  Scheduling Kernels via Configuration LP.
  - arXiv CoRR abs/2003.02187 (2020)
  
  
• C. Brand, M. Koutecký, S. Ordyniak.
  Parameterized Algorithms for MILPs with Small Treedepth.
  - arXiv CoRR abs/1912.03501 (2019)
  
  
• D. Gavinsky.
  Bare quantum simultaneity versus classical interactivity in communication complexity.
  - arXiv CoRR abs/1911.01381, 2019.
  
  
• D. Gavinsky, and P. Pudlák.
  Santha-Vazirani sources, deterministic condensers and very strong extractors.
  - arXiv CoRR abs/1907.04640, 2019.
  
  
• P. Hrubeš.
  On the distribution of runners on a circle.
  - arXiv CoRR abs/1906.02511, 2019.
  
  
• P. Hrubeš.
  On $\epsilon$-sensitive monotone computations.
  - Electronic Colloquium on Computational Complexity (ECCC) Tech Rep. TR19-034, 2019.
  
  
• P. Hrubeš.
  On the complexity of computing a random Boolean function over the reals.
  - Electronic Colloquium on Computational Complexity (ECCC) Tech Rep. TR19-036, 2019.
  
  
• M. Koucký, V. Rödl, and N. Talebanfard.
  A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm.
  - Electronic Colloquium on Computational Complexity (ECCC) Tech Rep. TR19-181, 2019.
  
  
• M. Koucký and M. Saks.
  Constant factor approximations to edit distance on far input pairs in nearly linear time.
  - arXiv CoRR abs/1904.05459, 2019.
  
  
• P. Pudlák.
  The canonical pairs of bounded depth Frege systems.
  - arXiv CoRR abs/1912.03013, 2019.
  
  
• P. Pudlák and V. Rödl.
  Extractors for small zero-fixing sources.
  - arXiv CoRR abs/1904.07949, 2019.
  
  

---

This project is funded by the Grant Agency of the Czech Republic under the grant agreement no. 19-27871X.