Skip to main content Skip to navigation

Department of Computer Science

Theory and Foundations Publications and Research Projects

This gives an overview of our publications and projects. You can also refer to the webpages of individual members.

  • Lokshtanov, Daniel, Misra, Pranabendu, Panolan, Fahad, Ramanujan , M.S., Saurabh, Saket, Zehavi, Meirav, 2024. Meta-theorems for parameterized streaming algorithms. ACM-SIAM Symposium on Discrete Algorithms (SODA24), Virginia, USA, 7-10 Jan 2024, Published in Proceedings of SODA 2024
  • Inamdar, Tanmay, Kundu, Madhumita, Parviainen, Pekka, Ramanujan, Maadapuzhi Sridharan, Saurabh, Saket, 2024. Exponential-time approximation schemes via compression. 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), Berkeley, CA, USA, 30 Jan - 2 Feb 2024, Published in 5th Innovations in Theoretical Computer Science Conference (ITCS 2024), pp. 64:1-64:22
  • Bhattacharya, Sayan, Costa, Martin, Panski, Nadav, Solomon, Shay, 2024. Nibbling at long cycles : dynamic (and static) edge coloring in optimal time. 35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), Virginia, USA, 7-10 Jan 2024
  • Coy, Sam, Czumaj, Artur, Davies-Peck, Peter, Mishra, Gopinath, 2024. Parallel derandomization for coloring. 38th IEEE International Parallel & Distributed Processing Symposium (IPDPS), San Francisco, 27-31 May 2024, Published in Proceedings of the 38th IEEE International Parallel & Distributed Processing Symposium (IPDPS)
  • Gupta, Sushmita, Sridharan, Ramanujan, Strulo, Peter, 2023. An exercise in tournament design : when some matches must be scheduled. Thirty-Eighth AAAI Conference on Artificial Intelligence, AAAI 2024, Vancouver, Canada, 20-27 Feb 2024, Published in Proceedings of Thirty-Eighth AAAI Conference on Artificial Intelligence, AAAI 2024
  • Inamdar, Tanmay, Kanesh, Lawqueen, Kundu, Madhumita, Ramanujan, M. S., Saurabh, Saket, 2023. FPT approximations for packing and covering problems parameterized by elimination distance and even less. 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023), pp. 28:1-28:16
  • Agrawal, Akanksha, Ramanujan, M. S., 2023. Approximately interpolating between uniformly and non-uniformly polynomial kernels. 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023), pp. 36:1-36:17
  • Eiben, Eduard, Majumdar, Diptapriyo, Ramanujan, M. S., 2023. Finding a highly connected Steiner subgraph and its applications. 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), Published in Leibniz International Proceedings in Informatics (LIPIcs), pp. 45:1-45:15
  • Bhattacharya, Sayan, Kiss, Peter, Saranurak, Thatchaphol, 2023. Sublinear algorithms for (1.5+\epsilon)-approximate matching. STOC 2023: 55th Annual ACM Symposium on Theory of Computing, Orlando, Florida, 20-23 Jun 2023, Published in STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pp. 254-266
  • Bhattacharya, Sayan, Buchbinder, Niv, Levin, Roie, Saranurak, Thatchaphol, 2023. Chasing positive bodies. 64th IEEE Symposium on Foundations of Computer Science (FOCS) 2023, Santa Cruz, CA, USA, 6-9 Nov 2023
  • Bhattacharya, Sayan, Kiss, Peter, Saranurak, Thatchaphol, 2023. Dynamic (1+\epsilon) : approximate matching size in truly sublinear update time. 64th IEEE Symposium on Foundations of Computer Science (FOCS), Santa Cruz, USA, 06-09 Nov 2023, Published in Annual Symposium on Foundations of Computer Science
  • Bhattacharya, Sayan, Costa, Martin, Lattanzi, Silvio, Parotsidis, Nikos, 2023. Fully dynamic k-Clustering in O(k) update time. 37th Conference on Neural Information Processing Systems (NeurIPS 2023), New Orleans, USA, 10-16 Dec 2023, Published in Advances in Neural Information Processing Systems, pp. 18633-18658
  • Chen, Megan, Chiesa, Alessandro, Gur, Tom, O?Connor, Jack, Spooner, Nicholas, 2023. Proof-carrying data from arithmetized random oracles. 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, 23?27 Apr 2023, Published in Advances in Cryptology ? EUROCRYPT 2023, pp. 379-404
  • Cardinal, Jean, Hoang, Hung, Merino, Arturo, Micka, Ondrej, Mutze, Torsten, 2023. Zigzagging through acyclic orientations of graphs and hypergraphs. 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), Florence, Italy, 22-25 Jan 2023, Published in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 3029-3042
  • Merino, Arturo, Mutze, Torsten, 2023. Traversing combinatorial 0/1-polytopes via optimization. IEEE Symposium on Foundations of Computer Science (FOCS), Santa Cruz, CA, USA, 06-09 Nov 2023, Published in 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1282-1291
  • Chistikov, Dmitry, Englert, Matthias, Lazic, Ranko, 2023. Learning a neuron by a shallow ReLU network : dynamics and implicit bias for correlated inputs. 37th Conference on Neural Information Processing Systems (NeurIPS 2023), New Orleans, USA, 10-16 Dec 2023
  • Coy, Sam, Czumaj, Artur, Mishra, Gopinath, 2023. On parallel k-center clustering. SPAA '23: 35th ACM Symposium on Parallelism in Algorithms and Architectures, Orlando, Florida, USA, 16-19 Jun 2023, Published in Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 65-75
  • Coy, Sam, Czumaj, Artur, Davies, Peter, Mishra, Gopinath, 2023. Optimal (degree+1)-coloring in congested clique. ICALP 2023: 50th EATCS International Colloquium on Automata, Languages and Programming, Paderborn, Germany, 10-14 Jul 2023, Published in Leibniz International Proceedings in Informatics (LIPIcs), pp. 45:1-45:16
  • Czumaj, Artur, 2023. Modern parallel algorithms. 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), Published in Leibniz International Proceedings in Informatics (LIPIcs), pp. 3:1-3:2
  • Englert, Matthias, Matsakis, Nicolaos, Veselý, Pavel, 2023. Approximation guarantees for shortest superstrings : simpler and better. 34th International Symposium on Algorithms and Computation (ISAAC 2023), Kyoto, Japan, 3?6 Dec 2023, Published in Proceedings of the 34th International Symposium on Algorithms and Computation (ISAAC 2023), pp. 29:1-29:17
  • Cavalar, Bruno P., Oliveira, Igor C., 2023. Constant-depth circuits vs. monotone circuits. 38th Computational Complexity Conference (CCC 2023), Warwick, UK, 17?20 Jul 2023, Published in 38th Computational Complexity Conference (CCC 2023), pp. 29:1-29:37
  • Chen, Lijie, Lu, Zhenjian, Oliveira, Igor C., Ren, Hanlin, Santhanam, Rahul, 2023. Polynomial-time pseudodeterministic construction of primes. 64th IEEE Symposium on Foundations of Computer Science (FOCS) 2023, Santa Cruz, CA, USA, 06-09 Nov 2023, Published in 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)
  • Benedikt, Michael, Chistikov, Dmitry, Mansutti, Alessio, 2023. The complexity of Presburger arithmetic with power or powers. 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), Paderborn, Germany, 10-14 Jul 2023, Published in Leibniz International Proceedings in Informatics (LIPIcs), pp. 112:1-112:18
  • Chistikov, Dmitry, Czerwinski, Wojciech, Hofman, Piotr, Mazowiecki, Filip, Sinclair-Banks, Henry, 2023. Acyclic Petri and workflow nets with resets. 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023), Hyderabad, India, 18-20 Dec 2023, Published in Leibniz International Proceedings in Informatics (LIPIcs), pp. 16:1-16:18
  • 'Agrawal, Akanksha, 'Kanesh, Lawqueen, 'Lokshtanov, Daniel, 'Panolan, Fahad, 'Ramanujan, Maadapuzhi Sridharan, 'Saurabh, Saket, 'Zehavi , Meirav, 2022. 'Deleting, eliminating and decomposing to hereditary classes are all FPT-equivalent. ACM-SIAM Symposium on Discrete Algorithms (SODA22), Virginia, U.S. (virtual conference), 9-12 Jan 2022, Published in Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1976-2004
  • Lokshtanov, Daniel, Panolan, Fahad, Ramanujan, Maadapuzhi Sridharan, 2022. Backdoors to nowhere dense SAT. 49th EATCS International Colloquium on Automata, Languages and Programming (ICALP), Paris, France ; Virtual, 4-8 Jul 2022, Published in 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), pp. 91:1-91:20
  • Lisowski, Grzegorz, Ramanujan, M. S., Turrini, Paolo, 2022. Equilibrium computation for knockout tournaments played by groups. 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2022), Virtual, 9?13 May 2022, Published in Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2022), pp. 807-815
  • Lokshtanov, Daniel, Panolan, Fahad, Ramanujan, M. S., 2022. Backdoor sets on nowhere dense SAT. 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), Paris, France, 4-8 Jul 2022, Published in 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), pp. 91:1-91:20
  • 'Bera, Suman, 'Bhattacharya, Sayan, 'Choudhari, Jayesh, 'Ghosh, Prantar, 2022. 'A new dynamic algorithm for densest subhypergraphs. WWW '22: The ACM Web Conference, Online, hosted Lyon, France, 25?29 Apr 2022, Published in WWW '22: The ACM Web Conference Proceedings
  • Bhattacharya, Sayan, Saranurak, Thatchaphol, Sukprasert, Pattara, 2022. Simple dynamic spanners with near-optimal recourse against an adaptive adversary. 30th Annual European Symposium on Algorithms (ESA 2022), Germany, 5-9 Sep 2022, Published in Leibniz International Proceedings in Informatics (LIPIcs) series, pp. 17:1-17:19
  • 'Gur, Tom, 'Lifshitz, Noam, 'Liu, Siqi, 2022. 'Hypercontractivity on high dimensional expanders. The 54th ACM Symposium on Theory of Computing (STOC 2022), Rome, Italy, 20-24 Jun 2022, Published in STOC 2022 : Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 176-184
  • 'Asadi, Vahid R., 'Golovnev, Alexander, 'Gur, Tom, 'Shinkar, Igor, 2022. 'Worst-case to average-case reductions via additive combinatorics. The 54th ACM Symposium on Theory of Computing (STOC 2022), Rome, Italy, 20-24 Jun 2022, Published in STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1566-1574
  • Gregor, Petr, Mutze, Torsten, Merino, Arturo, 2022. Star transposition Gray codes for multiset permutations. 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), Marseille, 15-18 Mar 2022, Published in Proceedings of STACS 2022
  • 'Merino, Arturo, 'Mutze, Torsten, 'Williams, Aaron, 2022. 'All your bases are belong to us : listing all bases of a matroid by greedy exchanges. 11th International Conference on Fun with Algorithms (FUN 2022), Sicily, Italy, 30 May - 03 Jun 2022, Published in 11th International Conference on Fun with Algorithms (FUN 2022), pp. 22:1-22:28
  • 'Cardinal, Jean, 'Merino, Arturo, 'Mutze, Torsten, 2022. 'Efficient generation of elimination trees and graph associahedra. 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), Virtual Conference, 09-12 Jan 2022, Published in Proceedings of SODA 2022, pp. 2128-2140
  • 'Czumaj, Artur, 'Jiang, Shaofeng H.-C., 'Krauthgamer, Robert, 'Vesel?, Pavel, 2022. 'Streaming algorithms for geometric Steiner forest. 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), Paris, France, 04-08 Jul 2022, Published in Proceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), pp. 1-20
  • 'Czumaj, Artur, 'Jiang, Shaofeng H.-C., 'Krauthgamer, Robert, 'Vesely, Pavel, 'Yang, Mingwei, 2022. 'Streaming facility location in high dimension via geometric hashing. The 63rd IEEE Symposium on Foundations of Computer Science (FOCS 2022), Denver, CO, USA, 31 Oct - 03 Nov 2022, Published in Proceedings of the 63rd IEEE Symposium on Foundations of Computer Science (FOCS 2022)
  • Coy, Sam, Czumaj, Artur, Feldmann, Michael, Hinnenthal, Kristian, Kuhn, Fabian, Scheideler, Christian, Schneider, Philipp, Struijs, Martijn, 2022. Near-shortest path routing in hybrid communication networks. 25th International Conference on Principles of Distributed Systems (OPODIS 2021), Strasbourg, France, 13?15 Dec 2021, Published in 25th International Conference on Principles of Distributed Systems (OPODIS 2021), pp. 11:1-11:23
  • 'Englert, Matthias, 'Matsakis, Nicolaos, 'Vesel?, Pavel, 2022. 'Improved approximation guarantees for shortest superstrings using cycle classification by overlap to length ratios. STOC 2022: 54th Annual ACM Symposium on Theory of Computing, Rome, Italy, 20-24 Jun 2022, Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC ?22), pp. 317-330
  • 'Goldberg, Halley, 'Kabanets, Valentine, 'Lu, Zhenjian, 'Oliveira, Igor C., 2022. 'Probabilistic Kolmogorov complexity with applications to average-case complexity. Computational Complexity Conference (CCC), Philadelphia, PA, USA, 21?23 Jul 2022, Published in 37th Computational Complexity Conference (CCC 2022), pp. 16:1-16:60
  • 'Carmosino, Marco, 'Kabanets, Valentine, 'Kolokolova, Antonina, 'Carboni Oliveira, Igor, 2022. 'LEARN-uniform circuit lower bounds and provability in bounded arithmetic. Symposium on Foundations of Computer Science (FOCS), Denver, Colorado, 7-10 Feb 2022, Published in 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)
  • 'Chistikov, Dmitry, 'Haase, Christoph, 'Mansutti, Alessio, 2022. 'Geometric decision procedures and the VC dimension of linear arithmetic theories. 37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2022), Haifa, Israel, 02?05 Aug 2022, Published in 37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2022)
  • 'Chistikov, Dmitry, 'Haase, Christoph, 'Hadizadeh, Zahra, 'Mansutti, Alessio, 2022. 'Higher-order quantified Boolean satisfiability. 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), Vienna, Austria, 22-26 Aug 2022, Published in Proceedings of the International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
  • Chistikov, Dmitry, Majumdar, Rupak, Schepper, Philipp, 2022. Subcubic certificates for CFL reachability. ACM SIGPLAN Symposium on Principles of Programming Languages (POPL 2022), Philadelphia, Pennsylvania, United States, 16-22 Jan 2022, Published in Proceedings of the ACM on Programming Languages
  • Chistikov, Dmitry, Haase, Christoph, Mansutti, Alessio, 2022. Quantifier elimination for counting extensions of Presburger arithmetic. 25th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS 2022), Munich, Germany, 2-7 Apr 2022, Published in Foundations of Software Science and Computation Structures, pp. 225-243
  • Harrenstein, Paul, Lisowski, Grzegorz, Sridaran, Ramanujan, Turrini, Paolo, 2021. A hotelling-downs framework for party nominees. 20th International Conference on Autonomous Agents and Multiagent Systems, London (Virtual), 3-7 May 2021, Published in Proceedings of the 20th International Conference on Multiagent Systems (AAMAS 2021), pp. 593-601
  • Lokshtanov, Daniel, Misra, Pranabendu, Sridharan, Ramanujan, Saurabh, Saket, Zehavi, Meirav, 2021. FPT-approximation for FPT problems. ACM-SIAM Symposium on Discrete Algorithms (SODA) 2021, Virtual, 10-13 Jan 2021, Published in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)
  • Kozachinskiy, Alexander, 2021. Continuous positional payoffs. 32nd International Conference on Concurrency Theory (CONCUR'21), Online, 23-27 Aug 2021, Published in Proceedings of the 32nd International Conference on Concurrency Theory (CONCUR'21), pp. 10:1-10:17
  • Bhattacharya, Sayan, Grandoni, Fabrizio, Wajc, David, 2021. Online edge coloring algorithms via the nibble method. ACM-SIAM Symposium on Discrete Algorithms (SODA21), Virtual, 10-13 Jan 2021, Published in SODA '21: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2830-2841
  • Bhattacharya, Sayan, Henzinger, Monika, Nanongkai, Danupon, Wu, Xiaowei, 2021. Dynamic set cover : improved amortized and worst-case update time. ACM-SIAM Symposium on Discrete Algorithms (SODA21), Virtual, 10-13 Jan 2021, Published in Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2537-2549
  • Bhattacharya, Sayan, Kiss, Peter, 2021. Deterministic rounding of dynamic fractional matchings. 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Virtual, 12-16 Jul 2021, Published in 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), pp. 27:1-27:14
  • 'Arunachalam, Srinivasan, 'Grilo, Alex B., 'Gur, Tom, 'Carboni Oliveira, Igor, 'Sundaram, Aarthi, 2021. 'Quantum learning algorithms imply circuit lower bounds. The 62nd Annual Symposium on Foundations of Computer Science (FOCS 2021), Denver, Colorado, 7-10 Feb 2022, Published in 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)
  • Dall'Agnol, Marcel, Gur, Tom, Wajc, David, Lachish, Oded, 2021. A structural theorem for local algorithms with applications to testing, coding, and privacy. ACM-SIAM Symposium on Discrete Algorithms (SODA21), Virtual, 10-13 Jan 2021, Published in SODA '21: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1651-1665
  • Merino, Arturo, Micka, Ondrej, Mutze, Torsten, 2021. On a combinatorial generation problem of Knuth. 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, Virtual Conference, 10-13 Jan 2021, Published in Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 735-743
  • Merino, Arturo, Mutze, Torsten, 2021. Efficient generation of rectangulations via permutation languages. 37th International Symposium on Computational Geometry, University at Buffalo, The State University of New York, USA, 07-11 Jun 2021, Published in 37th International Symposium on Computational Geometry (SoCG 2021), pp. 1-18
  • Dixon, Alex, Lazic, Ranko, Murawski, Andrzej S., Walukiewicz, Igor, 2021. Verifying higher-order concurrency with data automata. ACM/IEEE LICS 2021 : 36th Annual Symposium on Logic in Computer Science, Virtual conference, 29 Jun - 2 Jul 2021, Published in 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
  • Dixon, Alex, Lazic, Ranko, Murawski, Andrzej S., Walukiewicz, Igor, 2021. Leafy automata for higher-order concurrency. FoSSaCS 21, Virtual conference, 27 Mar-1 Apr 2021, Published in FOSSACS 2021: Foundations of Software Science and Computation Structures, pp. 184-204
  • Czumaj, Artur, Kontogeorgiou, George, Paterson, Michael S., 2021. Haystack hunting hints and locker room communication. 48th International Colloquium on Automata, Languages and Programming (ICALP 2021), Virtual, Scotland, 12-16 Jul 2021, Published in 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), pp. 58 : 1-58: 20
  • Czumaj, Artur, Davies, Peter, Parter, Merav, 2021. Component stability in low-space massively parallel computation. 40th Annual ACM Symposium on Principles of Distributed Computing (PODC 2021), Virtual, Italy, 26-30 Jul 2021, Published in PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, pp. 481-491
  • Czumaj, Artur, Davies, Peter, Parter, Merav, 2021. Improved deterministic (? + 1)-coloring in low-space MPC. 40th Annual ACM Symposium on Principles of Distributed Computing (PODC 2021), Virtual, Italy, 26-30 Jul 2021, Published in PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, pp. 469-479
  • Antoniadis, Antonios, Englert, Matthias, Matsakis, Nicolaos, Veselý, Pavel, 2021. Breaking the barrier of 2 for the competitiveness of longest queue drop. 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Virtual, 12-16 Jul 2021, Published in 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), pp. 17:1-17:20
  • Lu, Zhen Jian, Oliveira, Igor C., Santhanam, Rahul, 2021. Pseudodeterministic lagorithms and the structure of probabilistic time. STOC 2021: 53rd Annual ACM Symposium on Theory of Computing, Virtual conference, 21-25 Jun 2021, Published in STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 303-316
  • Lu, Zhenjian, Oliveira, Igor C., 2021. An efficient coding theorem via probabilistic representations and its applications. International Colloquium on Automata, Languages and Programming (ICALP), Virtual conference, 12-16 Jul 2021, Published in 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), pp. 94:1-94:20
  • Chen, Lijie, Lu, Zhenjian, Lyu, Xin, Oliveira, Igor C., 2021. Majority vs. approximate linear sum and average-case complexity below NC1. International Colloquium on Automata, Languages and Programming (ICALP), Virtual conference, 12-16 Jul 2021, Published in 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), pp. 51:1-51:20
  • Lu, Zhenjian, Oliveira, Igor C., Santhanam, Rahul, 2021. Pseudodeterministic algorithms and the structure of probabilistic time. 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual conference, 21-25 June 2021, Published in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
  • Lokshtanov, Daniel, Sridharan, Ramanujan, Saurabh, Saket, Zehavi, Meirav, 2020. Parameterized complexity and approximability of directed odd cycle transversal. ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), Salt Lake City, Utah, 5-8 Jan 2020, Published in Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2181-2200
  • Bhattacharya, Sayan, Nanongkai, Danupon, Saranurak, Thatchaphol, 2020. Coarse-grained complexity for dynamic algorithms. 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Salt Lake City, Utah, U.S., 5-8 Jan 2020, Published in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 476-494
  • Bhattacharya, Sayan, Kulkarni, Janardhan, 2020. An improved algorithm for incremental cycle detection and topological ordering in sparse graphs. 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Salt Lake City, Utah, U.S., 5-8 Jan 2020, Published in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2509-2521
  • Bhattacharya, Sayan, Henzinger, Monika, Nanongkai, Danupon, 2020. A new deterministic algorithm for dynamic set cover. FOCS 2019 60th Annual IEEE Symposium on Foundations of Computer Science, Baltimore, Maryland, 9-12 Nov 2019, Published in 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
  • Chiesa, Alessandro, Gur, Tom, Shinkar, Igor, 2020. Relaxed locally correctable codes with nearly-linear block length and constant query complexity. 31st ACM-SIAM Symposium on Discrete Algorithms (SODA20), Salt Lake City, Utah, U.S., 5-8 Jan 2020, Published in Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1395-1411
  • Gur, Tom, Lachish, Oded, 2020. On the power of relaxed local decoding algorithms. 31st ACM-SIAM Symposium on Discrete Algorithms (SODA20), Salt Lake City, Utah, U.S., 5-8 Jan 2020, Published in Proceedings of ACM-SIAM Symposium on Discrete Algorithms, pp. 1377-1394
  • Gregor, Petr, Micka, Ondrej, Mutze, Torsten, 2020. On the central levels problem. 47th International Colloquium on Automata, Languages, and Programming, Saarbrücken, 8-11 Jul 2020, Published in 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), pp. 60:1-60:17
  • Hartung, Elizabeth, Hoang, Hung, Mutze, Torsten, Williams, Aaron, 2020. Combinatorial generation via permutation languages. 31st Annual ACM-SIAM Symposium on Discrete Algorithms, Salt Lake City, United States, 5-8 Jan 2020, Published in SODA '20: Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1214-1225
  • Czerwinski, Wojciech, Lasota, Slawomir, Lazic, Ranko, Leroux, Jerome, Mazowiecki, Filip, 2020. Reachability in fixed dimension vector addition systems with states. 31st International Conference on Concurrency Theory (CONCUR 2020), Virtual conference, 01-04 Sep 2020, Published in Leibniz International Proceedings in Informatics (LIPIcs)
  • Czumaj, Artur, Sohler, Christian, 2020. Sublinear time approximation of the cost of a metric k-nearest neighbor graph. Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'2020), Salt Lake City, Utah, USA, January 5-8, 2020, Salt Lake City, Utah, USA, 5-8 Jan 2020, Published in Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, pp. 2973-2992
  • Czumaj, Artur, Davies, Peter, Parter, Merav, 2020. Graph sparsification for derandomizing massively parallel computation with low space. 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020), Virtual, USA, 15-17 Jul 2020, Published in SPAA '20: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, pp. 175-185
  • Czumaj, Artur, Fichtenberger, Hendrik, Peng, Pan, Sohler, Christian, 2020. Testable properties in general graphs and random order streaming. 24th International Conference on Randomization and Computation (RANDOM 2020), Virtual, USA, 17-19 Aug 2020, Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020), pp. 1-20
  • Czumaj, Artur, Sohler, Christian, 2020. A characterization of graph properties testable for general planar graphs with one-sided error (it's all about forbidden subgraphs). The 60th IEEE Symposium on Foundations of Computer Science (FOCS 2019), Baltimore, MD, 9-12 Nov 2019, Published in 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
  • Czumaj, Artur, Davies, Peter, Parter, Merav, 2020. Simple, deterministic, constant-round coloring in the congested clique. 39th Annual ACM Symposium on Principles of Distributed Computing (PODC 2020), Virtual conference, 3-7 Aug 2020, Published in PODC '20: Proceedings of the 39th Symposium on Principles of Distributed Computing, pp. 309-318
  • Englert, Matthias, Räcke, Harald, Stotz, Richard, 2020. Polylogarithmic guarantees for generalized reordering buffer management. FOCS 2019 60th Annual IEEE Symposium on Foundations of Computer Science, Baltimore, Maryland, 9-12 Nov 2019, Published in 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
  • Kabanets, Valentine, Lu, Zhenjian, Koroth, Sajin, Myrisiotis, Dimitrios, Carboni Oliveira, Igor, 2020. Algorithms and lower bounds for de Morgan formulas of low-communication leaf gates. Computational Complexity Conference (CCC), 28?31 Jul 2020, Published in CCC '20: Proceedings of the 35th Computational Complexity Conference, pp. 1-41
  • Ilango, Rahul, Loff, Bruno, Carboni Oliveira, Igor, 2020. NP-hardness of circuit minimization for multi-output functions. Computational Complexity Conference (CCC), 28?31 Jul 2020, Published in CCC '20: Proceedings of the 35th Computational Complexity Conference, pp. 1-36
  • Chen, Lijie, Hirahara, Shuichi, Carboni Oliveira, Igor, Pich, Jan, Rajgopal, Ninad, Santhanam, Rahul, 2020. Beyond natural proofs : hardness magnification and locality. Innovations in Theoretical Computer Science, Seattle, USA, 12-14 Jan 2020, Published in 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), pp. 70 :1-70 :48
  • Daviaud, Laure, Jurdzinski, Marcin, Thejaswini, K. S., 2020. The Strahler number of a parity game. 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), 8-11 Jul 2020, Published in Leibniz International Proceedings in Informatics (LIPIcs), pp. 123:1-123:19
  • Chistikov, Dmitry, Vyalyi, Mikhail, 2020. Re-pairing brackets. The 35th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2020), 8-11 Jul 2020, Published in LICS '20: Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, pp. 312-326
  • Chistikov, Dmitry, Cadilhac, Michael, Zetzsche, Georg, 2020. Rational subsets of Baumslag-Solitar groups. 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), 8-11 Jul 2020, Published in 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), pp. 1-16
  • Chistikov, Dmitry, Haase, Christoph, 2020. On the power of ordering in linear arithmetic theories. 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), 8-11 Jul 2020, Published in 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), pp. 1-15
  • Chistikov, Dmitry, Kiefer, Stefan, Murawski, Andrzej S., Purser, David, 2020. The big-O problem for labelled markov chains and weighted automata. 31st International Conference on Concurrency Theory (CONCUR 2020), 1-4 Sep 2020, Published in Leibniz International Proceedings in Informatics (LIPIcs), pp. 41:1-41:19
  • Bhattacharya, Sayan, Kulkarni, Janardhan, 2019. Deterministically maintaining a (2 + ?)-approximate minimum vertex cover in O(1/?2) amortized update time. Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, CA, USA, 6-9 Jan 2019, Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1872-1885
  • Dinur, Irit, Goldreich, Oded, Gur, Tom, 2019. Every set in P is strongly testable under a suitable encoding. 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), Published in 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), pp. 30:1-30:17
  • Ben-Sasson, Eli, Chiesa, Alessandro, Goldberg, Lior, Gur, Tom, Riabzev, Michael, Spooner, Nicholas, 2019. Linear-size constant-query IOPs for delegating computation. The Seventeenth Theory of Cryptography Conference (TCC 2019), Nuremberg, Germany, 1-5 Dec 2019, Published in Theory of Cryptography. TCC 2019, pp. 494-521
  • Tiskin, Alexander, 2019. Bounded-length Smith-Waterman alignment. 19th International Workshop on Algorithms in Bioinformatics (WABI 2019), Niagara Falls, NY, USA, 8-10 Sep 2019, pp. 16:1-16:12
  • Czerwinski, Wojciech, Daviaud, Laure, Fijalkow, Nathanael, Jurdzinski, Marcin, Lazic, Ranko, Parys, Pawel, 2019. Universal trees grow inside separating automata : quasi-polynomial lower bounds for parity games. ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), California, 6-9 Jan 2019, Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2333-2349
  • Dixon, Alex, Lazic, Ranko, 2019. KReach : a tool for reachability in petri nets. TACAS 2020 : 26th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, Dublin, Ireland, 25-30 Apr 2020, Published in Tools and Algorithms for the Construction and Analysis of Systems. TACAS 2020, pp. 405-412
  • Lazic, Ranko, 2019. Finkel was right : counter-examples to several conjectures on variants of vector addition systems (invited talk). 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019), Bombay, India, 11-13 Dec 2019, Published in 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019), pp. 3:1-3:2
  • Czerwinski, Wojciech, Lasota, Slawomir, Lazic, Ranko, Leroux, Jerome, Mazowiecki, Filip, 2019. The reachability problem for Petri nets is not elementary. STOC 2019, Phoenix, AZ, USA, 23-26 Jun 2019, Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 24-33
  • Hubai, Tamàs, Král', Daniel, Parczyk, Olaf, Person, Yury, 2019. More non-bipartite forcing pairs. EuroComb 2019, Bratislava, Slovakia, 26-30 Aug 2019, Published in Acta Mathematica Universitatis Comenianae, pp. 819-825
  • Chistikov, Dmitry, Lisowski, Grzegorz, Paterson, Michael S., Turrini, Paolo, 2019. Convergence of opinion diffusion is PSPACE-complete. AAAI-34th conference on Artificial Intelligence, New York, New York, 7-12 Feb 2020, Published in Proceedings of The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, pp. 7103-7110
  • Oliveira, Igor C., Santhanam, Rahul, Srinivasan, Srikanth, 2019. Parity helps to compute majority. 34th Computational Complexity Conference (CCC 2019), New Brunswick, NJ, USA, 18-20 Jul 2019, Published in Proceedings of the 34th Computational Complexity Conference (CCC), pp. 23:1-23:17
  • Oliveira, Igor C., 2019. Randomness and intractability in Kolmogorov complexity. 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), Patras, Greece, 9-12 Jul 2019, Published in Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 32:1-32:14
  • Oliveira, Igor C., Pich, Jan, Santhanam, Rahul, 2019. Hardness magnification near state-of-the-art lower bounds. 34th Computational Complexity Conference (CCC 2019), New Brunswick, NJ, USA, 18-20 Jul 2019, Published in Proceedings of the 33rd Computational Complexity Conference, pp. 27:1-27:29
  • Daviaud, Laure, Jurdzinski, Marcin, Lehtinen, Karolina, 2019. Alternating weak automata from universal trees. 30th International Conference on Concurrency Theory (CONCUR 2019), Amsterdam, the Netherlands, 26-31 Aug 2019, Published in 30th International Conference on Concurrency Theory (CONCUR 2019), pp. 1-14
  • Chistikov, Dmitry, Murawski, Andrzej S., Purser, David, 2019. Asymmetric distances for approximate differential privacy. 30th International Conference on Concurrency Theory (CONCUR 2019), Amsterdam, Netherlands, 27-30 Aug 2019, pp. 1-17
  • Lokshtanov, Daniel, Ramanujan, Maadapuzhi Sridharan, Saurabh, Saket, Zehavi, Meirav, 2018. Reducing CMSO model checking to highly connected graphs. 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague, 13 Jul 2018, Published in 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), pp. 135:1-135:14
  • Bang-Jensen, Jørgen, Basavaraju, Manu, Vitting Klinkby, Kristine, Misra, Pranabendu, Ramanujan, Maadapuzhi Sridharan, Saurabh, Saket, Zehvi, Meirav, 2018. Parameterized algorithms for survivable network design with uniform demands. 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, Louisiana, USA, 7-10 Jan 2018, Published in Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1-13
  • Lokshtanov, Daniel, Ramanujan, Maadapuzhi Sridharan, Saket, Saurabh, 2018. When recursion is better than iteration : a linear-time algorithm for acyclicity with few error vertices. 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, Louisiana, USA, New Orleans, Louisiana, USA, 7-10 Jan 2018, Published in Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1-18
  • Bhattacharya, Sayan, Chakrabarty, Deeparnab, Henzinger, Monika, Nanongkai, Danupon, 2018. Dynamic algorithms for graph coloring. Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, USA, 7-10 Jan 2018, Published in Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1-20
  • Gur, Tom, Ramnarayan, Govind, Rothblum, Ron D., 2018. Relaxed locally correctable codes. 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), Published in 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), pp. 27:1-27:11
  • Chiesa, Alessandro, Gur, Tom, 2018. Proofs of proximity for distribution testing. 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), Published in 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), pp. 53:1-53:14
  • Gur, Tom, Liu, Yang P., Rothblum, Ron, 2018. An exponential separation between MA and AM proofs of proximity. The 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague, Czech Republic, 9-13 Jul 2018, Published in 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), pp. 73:1-73:15
  • Chiesa, Alessandro, Forbes, Michael, Gur, Tom, Spooner, Nicholas, 2018. Spatial isolation implies zero knowledge even in a quantum world. 59th Annual IEEE Symposium on Foundations of Computer Science, Paris, France, 7-9 Oct 2018, Published in 59th Annual IEEE Symposium on Foundations of Computer Science, pp. 755-765
  • Gregor, Petr, Jager, Sven, Mutze, Torsten, Sawada, Joe, Wille, Kaja, 2018. Gray codes and symmetric chains. 45th International Colloquium on Automata, Languages, and Programming (ICALP), Prague, 9-13 Jul 2018, Published in Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 66:1-66:14
  • Mutze, Torsten, Nummenpalo, Jerri, Walczak, Bartosz, 2018. Sparse Kneser graphs are Hamiltonian. 50th Annual ACM Symposium on the Theory of Computing (STOC), Los Angeles, 25-29 Jun 2018, Published in Proceedings of the 50th Annual ACM Symposium on the Theory of Computing (STOC), pp. 912-919
  • Daviaud, Laure, Jurdzinski, Marcin, Lazic, Ranko, Mazowiecki, Filip, Pérez, Guillermo A., Worell, James, 2018. When is containment decidable for probabilistic automata?. ICALP 2018: 45th International Colloquium on Automata, Languages, and Programming, Prague, Czech Republic, 9-13 Jul 2018, Published in 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), pp. 121:1-121:14
  • Daviaud, Laure, Jurdzinski, Marcin, Lazic, Ranko, 2018. A pseudo-quasi-polynomial algorithm for mean-payoff parity games. 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Oxford, 9?12 Jul 2018, Published in LICS '18: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, pp. 325-334
  • Czumaj, Artur, Lacki, Jakub, Madry, Aleksander, Mitrovic, Slobodan, Onak, Krzysztof, Sankowski, Piotr, 2018. Round compression for parallel matching algorithms. The 50th Annual ACM Symposium on Theory of Computing (STOC 2018), Los Angeles, 25-29 Jun 2018, Published in STOC 2018 Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 471-484
  • Czumaj, Artur, Davies, Peter, 2018. Faster deterministic communication in radio networks. 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016), Rome, Italy, 12-15 Jul 2016, Published in Leibniz International Proceedings in Informatics (LIPIcs), pp. 1-14
  • Cygan, Marek, Czumaj, Artur, Mucha, Marcin, Sankowski, Piotr, 2018. Online facility location with deletions. 26th Annual European Symposium on Algorithms (ESA 2018), Helsinki, Finland, 20-24 Aug 2018, Published in {26th Annual European Symposium on Algorithms (ESA 2018), pp. 21:1-21:15
  • Czumaj, Artur, Davies, Peter, 2018. Deterministic blind radio networks. 32nd International Symposium on Distributed Computing (DISC 2018), New Orleans, LA, 15-19 Oct 2018, Published in 32nd International Symposium on Distributed Computing (DISC 2018), pp. 15:1-15:17
  • Czumaj, Artur, Konrad, Christian, 2018. Detecting cliques in CONGEST networks. 32nd International Symposium on Distributed Computing (DISC 2018), New Orleans, LA, 15-19 Oct 2018, Published in 32nd International Symposium on Distributed Computing (DISC 2018), pp. 16:1-16:15
  • Englert, Matthias, Mezlaf, David, Westermann, Matthias, 2018. Online makespan scheduling with job migration on uniform machines. 26th Annual European Symposium on Algorithms (ESA 2018), Helsinki, Finland, 20-24 Aug 2018, Published in 26th Annual European Symposium on Algorithms (ESA 2018), pp. 1-14
  • Hirahara, Shuichi, Oliveira, Igor C., Santhanam, Rahul, 2018. NP-hardness of minimum circuit size problem for OR-AND-MOD circuits. Computational Complexity Conference, San Diego, California, 22-24 Jun 2018, Published in Proceedings of the 33rd Computational Complexity Conference, pp. 5:1-5:31
  • Oliveira, Igor Carboni, Santhanam, Rahul, 2018. Hardness magnification for natural problems. 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), Paris, France, 7-9 Oct 2018, pp. 65-76
  • Chen, Ruiwen, Oliveira, Igor Carboni, Santhanam, Rahul, 2018. An average-case lower bound against ACC0. LATIN 2018: Theoretical Informatics 13th Latin American Symposium, Buenos Aires, Argentina, 16-19 Apr 2018, Published in LATIN 2018: Theoretical Informatics, pp. 317-330
  • Oliveira, Igor C., Santhanam, Rahul, Tell, Roei, 2018. Expander-based cryptography meets natural proofs. 10th Innovations in Theoretical Computer Science Conference (ITCS), San Diego, California, USA., 10-12 Jan 2019, Published in Proceedings of the 33rd Computational Complexity Conference, pp. 18:1-18:14
  • Oliveira, Igor C., Santhanam, Rahul, 2018. Pseudo-derandomizing learning and approximation. 22nd International Conference on Randomization and Computation (RANDOM), Princeton, NJ, USA, 20-22 Aug 2018, Published in Proceedings of the 22nd International Conference on Randomization and Computation (RANDOM), pp. 55:1-55:19
  • Almagor, Shaull, Chistikov, Dmitry, Ouaknine, Joel, Worrell, James, 2018. O-minimal invariants for linear loops. ICALP 2018: 45th International Colloquium on Automata, Languages, and Programming, Prague, Czech Republic, 9-13 Jul 2018, Published in 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), pp. 114:1-114:14
  • Chistikov, Dmitry, Murawski, Andrzej S., Purser, David, 2018. Bisimilarity distances for approximate differential privacy. International Symposium on Automated Technology for Verification and Analysis 2018, Los Angeles, USA, Oct 7-10 2018, Published in Lecture Notes in Computer Science, pp. 194-210
  • Lokshtanov, Daniel, Panolan, Fahad, Maadapuzhi Sridharan, Ramanujan, Saurabh, Saket, 2017. Lossy kernelization. STOC 2017, 49th Annual ACM Symposium on the Theory of Computing, Montreal, 19-23 Jun 2017, Published in STOC 2017 Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 224-237
  • Bhattacharya, Sayan, Gupta, Manoj, Mohan, Divyarthi, 2017. Improved algorithm for dynamic b-Matching. 25th Annual European Symposium on Algorithms (ESA 2017), Vienna, Austria, 4-6 Sep 2017, Published in 25th Annual European Symposium on Algorithms (ESA 2017), pp. 1:1-1:5
  • Bhattacharya, Sayan, Chakraborty, Deeparnab, Henzinger, Monika, 2017. Deterministic fully dynamic approximate vertex cover and fractional matching in O(1) update time. IPCO 2017 (19th Conference on Integer Programming and Combinatorial Optimization), University of Waterloo, Canada, 26-28 Jun 2017, Published in Lecture Notes in Computer Science, pp. 86-98
  • Bhattacharya, Sayan, Henzinger, Monika, Nanongkai, Danupon, 2017. Fully dynamic approximate maximum matching and minimum vertex cover in O(log3 n) worst case update time. Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, 16-19 Jan 2017, Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 470-489
  • Blais, Eric, Canonne, Clément L., Gur, Tom, 2017. Distribution testing lower bounds via reductions from communication complexity. 32nd Computational Complexity Conference (CCC 2017), Published in 32nd Computational Complexity Conference (CCC 2017), pp. 28:1-28:40
  • Canonne, Clément L., Gur, Tom, 2017. An adaptivity hierarchy theorem for property testing. 32nd Computational Complexity Conference (CCC 2017), Published in 32nd Computational Complexity Conference (CCC 2017, pp. 27:1-27:25
  • Gur, Tom, Rothblum, Ron D., 2017. A hierarchy theorem for interactive proofs of proximity. 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), Published in 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), pp. 39:1-39:43
  • Mutze, Torsten, Nummenpalo, Jerri, 2017. A constant-time algorithm for middle levels Gray codes. 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 16-19 Jan 2017, Published in Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), pp. 2238-2253
  • Figueira, Diego, Lazic, Ranko, Leroux, Jerome, Mazowiecki, Filip, Sutre, Grégoire, 2017. Polynomial-space completeness of reachability for succinct branching VASS in dimension one. The 44th International Colloquium on Automata, Languages, and Programming (ICALP), Warsaw, Poland, 10-14 Jul 2017, Published in 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), pp. 119 : 1-119: 14
  • Clemente, Lorenzo, Lasota, Slawomir, Lazic, Ranko, Mazowiecki, Filip, 2017. Timed pushdown automata and branching vector addition systems. 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Reykjavik, Iceland, 20-23 Jun 2017, Published in 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
  • Colcombet, Thomas, Jurdzinski, Marcin, Lazic, Ranko, Schmitz, Sylvain, 2017. Perfect half space games. 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Reykjavik, Iceland, 20-23 Jun 2017, Published in Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
  • Jurdzinski, Marcin, Lazic, Ranko, 2017. Succinct progress measures for solving parity games. 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Reykjavik, Iceland, 20-23 Jun 2017, Published in Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pp. 1-9
  • Czumaj, Artur, Davies, Peter, 2017. Exploiting spontaneous transmissions for broadcasting and leader election in radio networks. ACM Symposium on Principles of Distributed Computing (PODC 2017), Washington, DC, USA, 25 - 27 July 2017, Published in Proceedings of the 36th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2017), pp. 3-12
  • Englert, Matthias, Räcke, Harald, 2017. Reordering buffers with logarithmic diameter dependency for trees. 28th ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, 16-19 Jan 2017, Published in SODA '17 Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1224-1234
  • Chen, Xi, Oliveira, Igor Carboni, Servedio, Rocco A., 2017. Addition is exponentially harder than counting for shallow monotone circuits. 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), Montreal, QC, Canada, 19-23 Jun 2017, Published in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 1232-1245
  • Oliveira, Igor Carboni, Santhanam, Rahul, 2017. Pseudodeterministic constructions in subexponential time. 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), Montreal, QC, Canada, 19-23 Jun 2017, Published in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 665-677
  • Oliveira, Igor Carboni, Santhanam, Rahul, 2017. Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness. 32nd Computational Complexity Conference (CCC), Riga, Latvia, 6-9 Jul 2017, Published in Leibniz International Proceedings in Informatics (LIPIcs), pp. 18:1-18:49
  • Chistikov, Dmitry, Haase, Christoph, 2017. On the complexity of quantified integer programming. The 44th International Colloquium on Automata, Languages, and Programming (ICALP), Warsaw, Poland, 10-14 July 2017, Published in 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), pp. 94:1-94:13
  • Chistikov, Dmitry, Kiefer, Stefan, Maru?iC, Ines, Shirmohammadi, Mahsa, Worrell, James, 2017. On rationality of nonnegative matrix factorization. Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, 16-19 Jan 2017, Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1290-1305
  • Chistikov, Dmitry, Iván, S., Lubiw, A., Shallit, J., 2017. Fractional coverings, greedy coverings, and rectifier networks. 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), Hannover, Germany, 8-11 Mar 2017, Published in Leibniz International Proceedings in Informatics, LIPIcs, pp. 23:1-23:14
  • Chistikov, D., Kiefer, S., Maru?ic, I., Shirmohammadi, M., Worrell, J., 2017. On rationality of nonnegative matrix factorization. Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, 16-19 Jan 2017, Published in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1290-1305
  • Bhattacharya, Sayan, Henzinger, Monika, Nanongkai, Danupon, 2016. New deterministic approximation algorithms for fully dynamic matching. 48th Annual ACM Symposium on Theory of Computing, Cambridge, MA, USA, 19-21 Jun 2016, Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp. 398-411
  • Englert, Matthias, Lazic, Ranko, Totzke, Patrick, 2016. Reachability in two-dimensional unary vector addition systems with states is NL-complete. Thirty-First Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), New York City, USA, 5?8 Jul 2016, Published in Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
  • Lazic, Ranko, Schmitz, Sylvain, 2016. The complexity of coverability in ?-Petri nets. 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), New York City, USA, 5?8 Jul 2016, Published in Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pp. 467-476
  • Goller, Stefan, Haase, Christoph, Lazic, Ranko, Totzke, Patrick, 2016. A polynomial-time algorithm for reachability in branching VASS in dimension one. 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Rome, Italy, 12-15 Jul 2016, Published in Leibniz International Proceedings in Informatics (LIPIcs)
  • Lazic, Ranko, Murawski, Andrzej S., 2016. Contextual approximation and higher-order procedures. 19th International Conference, FOSSACS 2016, Eindhoven, The Netherlands, 2-8 Apr 2016, Published in Foundations of Software Science and Computation Structures :19th International Conference, FOSSACS 2016, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2016, Eindhoven, The Netherlands, April 2-8, 2016, Proceeding, pp. 162-179
  • Hofman, Piotr, Lasota, Slawomir, Lazic, Ranko, Leroux, Jerome, Schmitz, Sylvain, Totzke, Patrick, 2016. Coverability trees for petri nets with unordered data. 19th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS), Eindhoven, The Netherlands, 2-8 Apr 2016, Published in Lecture Notes in Computer Science, pp. 445-461
  • Czumaj, Artur, Deligkas, Argyrios, Fasoulakis, Michail, Fearnley, John, Jurdzinski, Marcin, Savani, Rahul, 2016. Distributed methods for computing approximate equilibria. International Conference on Web and Internet Economics, WINE 2016, Montréal, Canada, 11-14 Dec 2016, Published in Web and Internet Economics. WINE 2016, pp. 15-28
  • Czumaj, Artur, Peng, Pan, Sohler, Christian, 2016. Relating two property testing models for bounded degree directed graphs. 48th Annual ACM Symposium on Theory of Computing (STOC 2016), Cambridge, MA, 19-21 Jun 2016, Published in STOC 2016 Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1033-1045
  • Al-Bawan, Kamal, Englert, Matthias, Westermann, Matthias, 2016. Online packet scheduling for CIOQ and buffered crossbar switches. 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), California, USA, 11-13 Jul 2016, Published in SPAA '16 Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 241-250
  • Al-Bawan, Kamal, Englert, Matthias, Westermann, Matthias, 2016. Comparison-based FIFO buffer management in QoS switches. 12th Latin American Theoretical Informatics Symposium (LATIN), 2016, Ensenada, México, 11-15 Apr 2016, Published in Proceedings of the 12th Latin American Theoretical Informatics Symposium (LATIN), 2016, pp. 27-40
  • Chen, Xi, Oliveira, Igor C., Servedio, Rocco A., Tan, Li-Yang, 2016. Near-optimal small-depth lower bounds for small distance connectivity. STOC 2016: 48th Annual Symposium on the Theory of Computing, Cambridge, MA, USA, 19-21 Jun 2016, Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp. 612-625
  • Chistikov, Dmitry, Majumdar, Rupak, Niksic, Filip, 2016. Hitting families of schedules for asynchronous programs. 28th International Conference, CAV 2016, Toronto, ON, Canada, 17-23 Jul 2016, Published in Computer Aided Verification. CAV 2016, pp. 157-176
  • Chistikov, D., Kiefer, S., Marusic, I., Shirmohammadi, M., Worrell, J., 2016. On restricted nonnegative matrix factorization. 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Rome, Italy, 12-15 Jul 2016, Published in Leibniz International Proceedings in Informatics, LIPIcs, pp. 103:1-103:14
  • Atig, Mohamed Faouzi, Chistikov, Dmitry, Hofman, Piotr, Kumar, K. Narayan, Saivasan, Prakash, Zetzsche, Georg, 2016. The complexity of regular abstractions of one-counter languages. 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), New York City, USA, 5?8 Jul 2016, Published in LICS '16 Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, pp. 207-216
  • Chistikov, Dmitry, Haase, Christoph, 2016. The taming of the semi-linear set. 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), pp. 128:1-128:13
  • Chistikov, Dmitry, Czerwinski, Wojciech, Hofman, Piotr, Pilipczuk, Michal, Wehar, Michael, 2016. Shortest paths in one-counter systems. 19th International Conference, FOSSACS 2016, Eindhoven, The Netherlands, 2-8 Apr 2016, Published in Foundations of Software Science and Computation Structures. FoSSaCS 2016, pp. 462-478
  • Chistikov, Dmitry, Martyugin, Pavel, Shirmohammadi, Mahsa, 2016. Synchronizing automata over nested words. 19th International Conference, FOSSACS 2016, Eindhoven, The Netherlands, 2-8 Arp 2016, Published in Foundations of Software Science and Computation Structures. FoSSaCS 2016, pp. 252-268
  • Gajarsky, Jakub, Hlineny, Petr, Lokshtanov, Daniel, Obdrálek, Jan, Ordyniak, Sebastian, Ramanujan, Maadapuzhi Sridharan, Saurabh, Saket, 2015. FO model checking on posets of bounded width. IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, Berkeley, CA, USA, 17-20 Oct 2015, Published in 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pp. 963-974
  • Fomin, Fedor V., Lokshtanov, Daniel, Misra, Neeldhara, Ramanujan, Maadapuzhi Sridharan, Saurabh, Saket, 2015. Solving d-SAT via backdoors to small Treewidth. Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, San Diego, USA, 4?6 Jan 2015, Published in Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 630-641
  • Bhattacharya, Sayan, Dvorák, Wolfgang, Henzinger, Monika, Starnberger, Martin, 2015. Welfare maximization with friends-of-friends network externalities. 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), München, Germany, 4-7 Mar 2015, Published in 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), pp. 90-102
  • Bhattacharya, Sayan, Henzinger, Monika, Italiano, Giuseppe F., 2015. Design of dynamic algorithms via primal-dual method. International Colloquium on Automata, Languages, and Programming, Kyoto, Japan, 6-10 Jul 2015, Published in Automata, Languages, and Programming : 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II, pp. 206-218
  • Bhattacharya, Sayan, Henzinger, Monika, Nanongkai, Danupon, Tsourakakis, Charalampos, 2015. Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. Forty-seventh annual ACM symposium on Theory of computing, Portland, Oregon, USA, 14-17 Jun 2015, Published in Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pp. 173-182
  • Bhattacharya, Sayan, Henzinger, Monika, Italiano, Giuseppe F., 2015. Deterministic fully dynamic data structures for vertex cover and matching. Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, 4-6 Jan 2015, Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 785-804
  • Bhattacharya, Sayan, Hoefer, Martin, Huang, Chien-Chung, Kavitha, Telikepalli, Wagner, Lisa, 2015. Maintaining near-popular matchings. International Colloquium on Automata, Languages, and Programming, Kyoto, Japan, 6-10 Jul 2015, Published in Automata, Languages, and Programming, pp. 504-515
  • Goldreich, Oded, Gur, Tom, Rothblum, Ron D., 2015. Proofs of proximity for context-free languages and read-once branching programs. The 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), Kyoto, Japan, 6-10 Jul 2015, Published in Automata, Languages, and Programming. ICALP 2015, pp. 666-677
  • Goldreich, Oded, Gur, Tom, Komargodski , Ilan, 2015. Strong locally testable codes with relaxed local decoders. 30th Conference on Computational Complexity (CCC?15), Published in 30th Conference on Computational Complexity (CCC 2015), pp. 1-41
  • Jurdzinski, Marcin, Lazic, Ranko, Schmitz, Sylvain, 2015. Fixed-dimensional energy games are in pseudo-polynomial time. 42nd International Colloquium, ICALP 2015, Kyoto, Japan, 6-10 Jul 2015, Published in Automata, Languages, and Programming : 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II, pp. 260-272
  • Lazic, Ranko, Schmitz, Sylvain, 2015. The ideal view on Rackoff's coverability technique. 9th International Workshop on Reachability Problems, Warsaw, Poland, 21-23 Sep 2015, Published in Reachability Problems : 9th International Workshop, RP 2015, Warsaw, Poland, September 21-23, 2015, Proceedings, pp. 76-88
  • Hebdige, Michael, Král', Daniel, 2015. Third case of the cyclic coloring conjecture. The Eight European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2015, Bergen, Norway, 31 Aug 4 Sep 2015, Published in Electronic Notes in Discrete Mathematics, pp. 11-15
  • Czumaj, Artur, Peng, Pan, Sohler, Christian, 2015. Testing cluster structure of graphs. Forty-Seventh Annual ACM on Symposium on Theory of Computing, Portland, Oregon, 15-17 Jun 2015, Published in Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pp. 723-732
  • Czumaj, Artur, 2015. Random permutations using switching networks. Forty-Seventh Annual ACM on Symposium on Theory of Computing, Portland, Oregon, 15-17 Jun 2015, Published in Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pp. 703-712
  • Oliveira, Igor C., Santhanam, Rahul, 2015. Majority is incompressible by AC0P circuits. Proceedings of the 30th Conference on Computational Complexity, Portland, Oregon, USA., 17-19 Jun 2015, Published in Leibniz International Proceedings in Informatics (LIPIcs), pp. 124-157
  • Blais, Eric, Canonne, Clément L., Oliveira, Igor C., Servedio, Rocco A., Tan, Li-Yang, 2015. Learning circuits with few negations. International Workshop on Randomization and Computation (RANDOM), Princeton, NJ, USA., 24-26 Aug 2015, Published in Leibniz International Proceedings in Informatics (LIPIcs), pp. 512-527
  • Chistikov, Dmitry, Dimitrova, Rayna, Majumdar, Rupak, 2015. Approximate counting in SMT and value estimation for probabilistic programs. 21st International Conference, TACAS 2015, London, UK, 11-18 Apr 2015, Published in Tools and Algorithms for the Construction and Analysis of Systems. TACAS 2015, pp. 320-334
  • Lazic, Ranko, Schmitz, Sylvain, 2014. Non-elementary complexities for branching VASS, MELL, and extensions. Joint Meeting of the 23rd EACSL Annual Conference on Computer Science Logic and the 29th ACM/IEEE Symposium on Logic in Computer Science, Vienna, Austria, 14-18 Jul 2014, Published in Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
  • Klimo?ová , Tereza, Král?, Daniel, 2014. Hereditary properties of permutations are strongly testable. 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'14), Portland, USA, 5-7 Jan 2014, Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1164-1173
  • Azar, Yossi, Englert, Matthias, Gamzu, Iftah, Kidron, Eytan, 2014. Generalized reordering buffer management. STACS ?14: 31st International Symposium on Theoretical Aspects of Computer Science, Lyon, France, 5-8 Mar 2014, Published in 31st International Symposium on Theoretical Aspects of Computer Science (STACS ?14), pp. 87-98
  • Englert, Matthias, Matsakis, Nicolaos, Mucha, Marcin, 2014. New bounds for online packing LPs. Latin American Theoretical INformatics (LATIN) 2014, Montevideo, Uruguay, 31 Mar- 4 Apr 2014, Published in Lecture Notes in Computer Science series, pp. 1-12
  • Chistikov, Dmitry, Majumdar, Rupak, 2014. Unary pushdown automata and straight-line programs. 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, 8-11 Jul 2014, Published in Automata, Languages, and Programming. ICALP 2014, pp. 146-157
  • Chistikov, Dmitry, 2014. Notes on counting with finite machines. 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014), New Delhi, India, 15?17 Dec 2014, pp. 339-350
  • Tiskin, Alexander, 2013. Efficient high-similarity string comparison. EDBT '13 Proceedings of the Joint EDBT/ICDT, Genoa, Italy, 18-22 Mar 2013, pp. 358-365
  • Adamaszek, Anna, Czumaj, Artur, Englert, Matthias, Räcke, Harald, 2012. An O(log k)-competitive algorithm for generalized caching. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, 17-19 Jan 2012, Published in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1681-1689
  • Czumaj, Artur, Monemizadeh, Morteza, Onak, Krzysztof, Sohler, Christian, 2011. Planar graphs : random walks and bipartiteness testing. 52nd Annual Symposium on Foundations of Computer Science (FOCS), Palm Springs, CA, 22-25 Oct. 2011, Published in Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on, pp. 423-432
  • Adamaszek, Anna, Czumaj, Artur, Englert, Matthias, Räcke, Harald, 2011. Almost tight bounds for reordering buffer management. STOC'11 Symposium on Theory of Computing Conference (Co-located with FCRC 2011), San Jose, CA, USA, 6-8 Jun 2011, Published in STOC '11 Proceedings of the 43rd annual ACM symposium on Theory of computing, pp. 607-616
  • Tiskin, Alexander, 2010. Parallel selection by regular sampling. 16th International Euro-Par Conference on Parallel Processing, Ischia, Italy, August 31 - September 03 2010
  • Tiskin, Alexander, 2010. Fast distance multiplication of unit-Monge matrices. 21st Annual ACM/SIAM Symposium on Discrete Algorithms, Austin, TX, 17-19 Jan 2010, Published in Proceedings of the twenty-first annual ACM-SIAM symposium on discrete algorithms, pp. 1287-1296
  • Krusche, Peter, Tiskin, Alexander, 2010. New algorithms for efficient parallel string comparison. 22nd ACM Symposium on Parallelism in Algorithms and Architectures, Santorini, Greece, 13-15 Jun 2010, Published in SPAA '10: Proceedings of the Twenty-Second Annual Symposium on Parallelism in Algorithms and Architectures, pp. 209-216
  • Adamaszek, Michal, Czumaj, Artur, Sohler, Christian, 2010. Testing monotone continuous distributions on high-dimensional real cubes. Workshop on Property Testing, Tsinghua University, Peoples Republic of China, Published in Property Testing : Current Research and Surveys, pp. 228-233
  • Czumaj, Artur, 2010. Local graph exploration and fast property testing. 16th Annual European Symposium on Algorithms (ESA 2010), Liverpool, England, 6-8 Sep 2010, Published in Lecture Notes in Computer Science, pp. 410-414
  • Czumaj, Artur, Sohler, Christian, 2010. Testing expansion in bounded-degree graphs. Meeting on Combinatorics and Probability, Mathemat Res Inst, Oberwolfach, Germany, April 26-May 02, 2009, Published in Combinatorics, Probability and Computing, pp. 693-709
  • Czumaj, Artur, Sohler, Christian, 2010. Sublinear-time algorithms. Workshop on Property Testing, Tsinghua University, Peoples Republic of China, Published in Property Testing : Current Research and Surveys, pp. 41-64
  • Czumaj, Artur, Adamaszek, Michal, Sohler, Christian, 2010. Testing monotone continuous distributions on high-dimensional real cubes. 21st ACM-SIAM Symposium on Discrete Algorithms (SODA'10), Austin, Texas, 17-19 Jan 2010, Published in SIAM, pp. 56-65
  • Englert, Matthias, Gupta, Anupam (Researcher in Computer Science), Krauthgamer, Robert, Raecke, Harald, Talgam-Cohen, Inbal, Talwar, Kunal, 2010. Vertex sparsifiers : new results from old techniques. 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2010)/14th International Workshop on Randomization and Computation (RANDOM 2010), Univ Politecnica Catalunya (UPC), Barcelona, Spain, 01-03 Sep 2010
  • Englert, Matthias, Gupta, Anupam, Krauthgamer, Robert, Räcke, Harald, Talgam-Cohen, Inbal, Talwar, Kunal, 2010. Vertex sparsifiers : new results from old techniques. 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010,, Barcelona, Spain, 1-3 Sep 2010, Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp. 152-165
  • Fearnley, John, Jurdzinski, Marcin, Savani, Rahul, 2010. Linear complementarity algorithms for infinite games. 36th Conference on Current Trends in Theory and Practice of Computer Science, Spindleruv Mlyn, Czech Republic, January 23-29, 2010, Published in Lecture Notes in Computer Science, pp. 382-393
  • Tiskin, Alexander, 2009. Periodic string comparison. 20th Annual Symposium on Combinatorial Pattern Matching, Lille, France, June 22-24, 2009, Published in Lecture Notes in Computer Science, pp. 193-206
  • Aziz, Haris, Lachish, Oded, Paterson, Michael S., Savani, Rahul, 2009. Power indices in spanning connectivity games. 5th International Conference on Algorithmic Aspects in Information and Management, San Francisco, CA, June 15-17, 2009, Published in Lecture Notes in Computer Science, pp. 55-67
  • Adamaszek, Anna, Czumaj, Artur, Lingas, Andrzej, 2009. PTAS for k-tour cover problem on the plane for moderately large values of k. 20th International Symposium on Algorithms and Computations (ISAAC 2009), Honolulu, HI, December 16-18, 2009, Published in Lecture Notes in Computer Science, pp. 994-1003
  • Englert, Matthias, Räcke, Harald, 2009. Oblivious routing for the Lp-norm. 50th Annual IEEE Symposium on Foundations of Computer Science, Atlanta, GA, October 25-27 2009, Published in 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 32-40
  • Englert, Matthias, Röglin, Heiko, Spönemann, Jacob, Vöcking, Berthold, 2009. Economical caching. 26th International Symposium on Theoretical Aspects of Computer Science, Freiburg, Germany, Feb 2009, Published in Leibniz International Proceedings in Informatics (LIPIcs), pp. 385-396
  • Jurdzinski, Marcin, Kwiatkowska, Marta, Norman, Gethin, Trivedi, Ashutosh, 2009. Concavely-priced probabilistic timed automata. 30th International Conference on Concurrency Theory, Bologna, Italy, September 01-04, 2009, Published in Lecture Notes in Computer Science, pp. 415-430
  • Jurdzinski, Marcin, 2009. Algorithms for solving infinite games. 35th Conference on Current Trends in Theory and Practice of Computer Science, Spindleruv Mlyn, Czech Republic, January 24-30, 2009, Published in Lecture Notes in Computer Science, pp. 46-48
  • Krusche, Peter, Tiskin, Alexander, 2008. Efficient parallel string comparison. International Parallel Computing Conference 2007, RWTH Aachen Univ, Aachen, France, 4-7 Sep 2007, pp. 193-200
  • Bouyer, Patricia, Brihaye, Thomas, Jurdzinski, Marcin, Lazic, Ranko, Rutkowski, Michal, Ph.D., 2008. Average-price and reachability-price games on hybrid automata with strong resets. 6th International Conference on Formal Modeling and Analysis of Timed Systems, St Malo, France, 15-17 September, 2008, Published in Lecture Notes in Computer Science, pp. 63-77
  • Paterson, Michael S., Peres, Yuval, Thorup, Mikkel, Winkler, Peter, Zwick, Uri, 2008. Maximum overhang. 19th ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, Jan 20-22, 2008, Published in Proceedings of the 19th Annual ACM - SIAM Symposium on Discrete Algorithms, pp. 756-765
  • Iwama, Kazuo, Nishimura, Harumichi, Paterson, Michael S., Raymond, Rudy, Yamashita, Shigeru, 2008. Polynomial-time construction of linear network coding. ICALP 2008: 35th International Colloquium on Automata, Languages and Programming, Reykjavik, Iceland, 6 - 13 Jul 2008, Published in Lecture Notes in Computer Science, pp. 271-282
  • Aziz, Haris, Paterson, Michael S., 2008. Classification of computationally tractable weighted voting games. World Congress on Engineering 2008, Imperial Coll London, London, England, Jul 02-04, 2008, Published in World Congress on Engineering : WCE 2008 : 2-4 July, 2008, Imperial College London, London, U.K, pp. 129-134
  • Englert, Matthias, Özmen, Deniz, Westermann, Matthias, 2008. The power of reordering for online minimum makespan scheduling. 49th Annual IEEE Symposium on Foundations of Computer Science, Philadelphia, PA, 25-28 Oct 2008, Published in Symposium on Foundations of Computer Science. Annual Proceedings, pp. 603-612
  • Jurdzinski, Marcin, Trivedi, Ashutosh, 2008. Average-time games. 28th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Bangalore, India, 9-11 Dec 2008, Published in Leibniz International Proceedings in Informatics, pp. 340-351
  • Jurdzinski, Marcin, Trivedi, Ashutosh, 2008. Concavely-Priced Timed Automata (Extended Abstract). 6th International Conference on Formal Modeling and Analysis of Timed Systems, St Malo, France, Sep 15-17, 2008, Published in Lecture Notes in Computer Science, pp. 48-62
  • Jurdzinski, Marcin, Savani, Rahul, 2008. A simple P-matrix linear complementarity problem for discounted games. 4th Conference on Computability in Europe (CiE 2008), Athens, Greece, 15-20 Jun 2008, Published in Logic and Theory of Algorithms, pp. 283-293
  • Jurdzinski, Marcin, Lazic, Ranko, 2007. Alternation-free modal mu-calculus for data trees. 22nd Annual IEEE Symposium on Logic in Computer Science, Wroclaw, Poland, 10-14 Jul 2007, Published in 22nd Annual IEEE Symposium on Logic in Computer Science : proceedings : Wroc¿aw, Poland, 10-14 July, 2007, pp. 131-140
  • Aziz, Haris, Paterson, Michael S., Leech, Dennis, 2007. Efficient algorithm for designing weighted voting games. 11th IEEE International Multitopic Conference, Lahore, Pakistan, 28-30 Dec 2007, Published in IEEE International Multitopic Conference, 2007. INMIC 2007, pp. 211-216
  • Czumaj, Artur, Sohler, Christian, 2007. On testable properties in bounded degree graphs. 18th ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Los Angeles, 07-09 Jan 2007, Published in Proceeding SODA '07 Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 494-501
  • Czumaj, Artur, Lingas, Andrzej, 2007. Finding a heaviest triangle is not harder than matrix multiplication. 18th ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Los Angeles, 07-09 Jan 2007, Published in Proceeding SODA '07 Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 986-994
  • Czumaj, Artur, Sohler, Christian, 2007. Testing expansion in bounded-degree graphs. 48th Annual IEEE Symposium on Foundations of Computer Science, Providence, RI, 20-23 Oct 2007, Published in 48th Annual IEEE Symposium on Foundations of Computer Science, 2007. FOCS '07, pp. 570-578
  • Czumaj, Artur, Sohler, Christian, 2007. Sublinear-time approximation algorithms for clustering via random sampling. 12th International Conference on Random Structures and Algorithms, Poznan, Poland, 01-05 Aug 2005, Published in Random Structures & Algorithms, pp. 226-256
  • Englert, Matthias, Räcke, Harald, Westermann, Matthias, 2007. Reordering buffers for general metric spaces. ACM symposium on theory of computing, Published in STOC '07 Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pp. 556-564
  • Englert, Matthias, Westermann, Matthias, 2007. Considering suppressed packets improves buffer management in QoS switches. ACM-SIAM symposium on Discrete algorithms, 7-9 Jan 2007, New Orleans, Louisiana, Published in ACM-SIAM symposium on Discrete algorithms, pp. 209-218
  • Englert, Matthias, Röglin, Heiko, Vöcking, Berthold, 2007. Worst case and probabilistic analysis of the 2-opt algorithm for the TSP. Eighteenth annual ACM-SIAM symposium on Discrete algorithm, New Orleans, Louisiana, 7-9 Jan 2007, Published in Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 1295-1304
  • Jurdzinski, Marcin, Trivedi, Ashutosh, 2007. Reachability-time games on timed automata. 34th International Colloquium on Automata, Languages and Programming, Wroclaw, Poland, 9-13 Jul 2007, Published in Automata, Languages and Programming, Proceedings, pp. 838-849
  • Dimovski, Aleksandar, Lazic, Ranko, 2006. Assume-guarantee software verification based on game semantics. 8th International Conference on Formal Engineering Methods (ICFEM 2006), Macao, China, 01-03 Nov 2006, Published in Formal Methods and Software Engineering, Proceedings, pp. 529-548
  • Lazic, Ranko, 2006. Safely freezing LTL. 26th International Conference on Foundations of Software Technology and Theoretical Computer Science, Calcutta, India, 13-15 Dec 2006, pp. 381-392
  • Jurdzinski, Marcin, Paterson, Michael S., Zwick, Uri, 2006. A deterministic subexponential algorithm for solving parity games. 17th ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, Jan 2006, Published in Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 117-123
  • Paterson, Michael S., Zwick, Uri, 2006. Overhang. 17th ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, JAN, 2006, Published in Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 231-240
  • Dyer, Martin, Goldberg, Leslie Ann, Paterson, Michael S., 2006. On counting homomorphisms to directed acyclic graphs. 33rd International Colloquium on Automata, Languages and Programming, Venice, Italy, 10-14 Jul 2006, Published in Lecture Notes in Computer Science, pp. 38-49
  • Englert, Matthias, Roglin, H., Vocking, B., 2006. Worst case and probabilistic analysis of the 2-opt algorithm for the TSP. Electronic Colloquium on Computational Complexity
  • Jurdzinski, Marcin, Peled, Doron, Qu, Hongyang, 2006. Calculating probabilities of real-time test cases. 5th International Workshop on Formal Approaches to Software Testing (FATES 2005), Edinburgh, 11 Jul 2005, Published in Formal Approaches to Software Testing, pp. 134-151
  • Chatterjee, Krishnendu, Henzinger, Thomas A., Jurdzinski, Marcin, 2006. Games with secure equilibria. 3rd International Symposium on Formal Methods for Components and Objects, Leiden, Netherlands, 2-05 Nov 2004, Published in Theoretical Computer Science, pp. 67-82
  • Demri, Stephane, Lazic, Ranko, Nowak, David, 2005. On the freeze quantifier in Constraint LTL : decidability and complexity. 12th International Symposium on Temporal Representation and Reasoning, Burlington, VT, 23-25 Jun 2005, Published in Information and Computation, pp. 2-24
  • Goldberg, Leslie Ann, Paterson, Michael S., Srinivasan, Aravind, Sweedyk, Elizabeth, 1997. Better approximation guarantees for job-shop scheduling. 8th Annual ACM/SIAM Symposium on Discrete Algorithms, New Orleans, LA, 05-07 Jan 1997, Published in SODA '97 Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, pp. 599-608
  • Paterson, Michael S., Srinivasan, Aravind, 1995. Contention resolution with bounded delay. 36th Annual Symposium on Foundations of Computer Science (FOCS 95), Milwaukee, WI, 23-25 Oct 1995, Published in 36th Annual Symposium on Foundations of Computer Science, 1995. Proceedings, pp. 104-113
Title Funder Award start Award end
ERC Starting Grant (original record 72385) UK Research and Innovation 01 Oct 2023 30 Sep 2028
Google PhD Fellowship: Towards Optimal Dynamic Clustering Google Ireland Limited 30 Sep 2024 29 Sep 2026
Two-way automata: limitations and frontiers EPSRC 01 Sep 2023 31 Aug 2026
New Horizons in Multivariate Preprocessing (MULTIPROCESS) EPSRC 01 Jan 2022 31 Dec 2025
Digital twins of robust automation, planning and routing for environmental navigation optimisation and impact - Sir David Attenborough DT project - original record 72777 Alan Turing Institute 01 May 2023 30 Sep 2024
Royal Society - Enhanced Research Expenses 2023 - relates to ideate 71421 and 63148 Royal Society 15 Jul 2023 30 Sep 2024
Royal Society University Research Fellowship Royal Society 01 Oct 2019 30 Sep 2024
Algorithms, Dynamics and Connections with Phase Transitions EPSRC 01 Sep 2021 31 Aug 2024
Royal Society Wolfson Wolfson Visiting Fellowships Royal Society 03 Jul 2023 02 Jul 2024
Theoretical Foundations of Modern Parallel and Distributed Algorithms EPSRC 01 Apr 2021 31 Mar 2024
Foundations of classical and quantum verifiable computing UK Research and Innovation 01 Jan 2020 31 Dec 2023
Weizmann - UK Joint Research Program: Combinatorial and Algorithmic Primitives for Modern Networks Weizmann Institute of Science 01 Oct 2018 30 Sep 2023
Research Fellowship Royal Commission for the Exhibition of 1851 01 Oct 2022 30 Sep 2023
IBM Faculty Award: Efficient Processing Methods for Big Graphs IBM UNITED KINGDOM TRUST 01 Oct 2017 31 Aug 2023
Structure vs Randomness in Algorithms and Computation EPSRC 01 Jul 2021 30 Jun 2023
Theory and Applications of Dynamic Algorithms EPSRC 06 Jan 2020 05 Jan 2023
Royal Society University Research Fellowship ( 6 months costed extension for PDRA, IDEATE 63148 - R.CSAA.3234) Royal Society 01 Apr 2021 30 Sep 2021
Large Discrete Structures (ERC Consolidator Grant Proposal) European Research Council (ERC) 01 Dec 2015 31 Jul 2021
Solving Parity Games in Theory and Practice EPSRC 01 May 2017 31 Jul 2021
Automata in the Wild ( Incubator event) EPSRC 15 Jan 2020 30 Jun 2021
Large Discrete Structures (ERC Consolidator Grant Proposal) European Research Council (ERC) 01 Feb 2015 30 Nov 2020
Analysis of formal languages via computational complexity Royal Society 01 Feb 2018 31 Jan 2020
Sublinear Algorithms for Big Graphs EPSRC 01 Jan 2016 31 Dec 2018
Petri Net Reachability Conjecture Leverhulme Trust 01 Oct 2017 31 Dec 2018
Leverhulme Prize Application for Professor D Kral Leverhulme Trust 01 Oct 2015 30 Sep 2018
Analytic methods for large discrete structures EPSRC 01 Oct 2015 30 Sep 2018
Scalable Indexing and Compression: Algorithms and Combinatorics (Early Career Fellowship for Golnaz Badkobeh) Leverhulme Trust 01 Sep 2015 31 Aug 2018
Algorithms for verifying systems with unbounded data and concurrency Royal Society 29 Jun 2015 28 Dec 2017
Automated reasoning for security and privacy: International Exchanges Standard Programme Royal Society 31 Mar 2017 01 Oct 2017
Counter Automata: Verification and Synthesis EPSRC 12 Jan 2015 11 Jul 2017
International Exchanges Scheme - 2013/R1; Advances in Approximation Algorithms. Royal Society 01 Sep 2013 29 Feb 2016
CCOSA: Classes of Combinatorial Objects from Structure to Algorithms: ERC Starting Fellowship for Dr Daniel Kral European Research Council 01 Oct 2012 30 Nov 2015
CCOSA: Classes of Combinatorial Objects from Structure to Algorithms: ERC Starting Fellowship for Dr Daniel Kral Subproject for Institution # 34195 European Research Council 01 Oct 2012 30 Nov 2015
Visiting Professorship - Formal verification, concurrency theory Leverhulme Trust 01 Feb 2015 31 Jul 2015
Extension to DIMAP - The centre for discrete mathematics and its applications EPSRC 26 Mar 2013 25 Mar 2014
PATTERN MATCHING ALGORITHMS FOR STREAMING DATA (PDF FOR BEN SACH) EPSRC 01 Oct 2010 30 Sep 2013
Sigma: A New Online Learning System JISC 01 Jul 2013 30 Sep 2013
The Centre for Discrete Mathematics and its Applications EPSRC 26 Mar 2007 25 Mar 2013
Efficient Decentralised Approaches in Algorithmic Game Theory EPSRC 01 Oct 2009 30 Sep 2012
Advances in Sublinear Algorithms EPSRC 01 Sep 2009 31 Aug 2012
The Interplay between Algorithms and Randomness Weizmann Institute of Science 01 Jan 2010 31 Dec 2011
2006 RCUK Academic Fellowship Competition - Complexity Science RCUK 01 Oct 2006 30 Sep 2011
Postdoctoral Fellowship for Mathias Englert: Randomisation In Online Algorithms, Load Balancing and Other Dynamic Problems EPSRC 01 Sep 2008 31 Aug 2011
Leverhulme Trust Senior Research Fellowship - 2009. Advanced Algorithms: Parallelism and Strings Royal Society 01 Oct 2009 30 Sep 2010
Games for Quantative Analysis of Real Time Systems. EPSRC 01 Sep 2007 31 Aug 2010
Workshop on extremal and probabilistic combinatorics - PI is J Hladky, PhD student British Combinatorial Committee 18 Jul 2010 25 Jul 2010
Workshop on Extremal and Probabilistic Combinatorics - J Hladky PI London Mathematical Society 18 Jul 2010 25 Jul 2010
Second Workshop on Timed Systems British Council 29 Mar 2010 31 Mar 2010
Special Structures in Vehicle Routing Problems EPSRC 17 Mar 2008 16 Mar 2010
Fast distance multiplication of unit-monge matrices Royal Society 16 Jan 2010 19 Jan 2010
Algorithms for Computing Equilibria in Games - (Fellow - R Savani) EPSRC 01 Oct 2006 30 Sep 2009
International Travel Grant - Periodic String Comparison Royal Society 22 Jun 2009 24 Jun 2009
Parallel Computing 2007 (ParCo 2007) Royal Society 02 Sep 2007 08 Sep 2007
Algorithmics of network-sharing games EPSRC 01 Jan 2005 30 Jun 2007
Discontinuous behaviour in the complexity of randomized algorithms EPSRC 01 Jan 2004 31 Dec 2006
Scalable Software Model Checking Based on Game Semantics EPSRC 01 Oct 2003 30 Sep 2006
International Computer Science Symposium in Russia (CSR2006) Royal Society 08 Jun 2006 07 Jul 2006
ALCOM-FT EU DGXII 01 Jun 2000 01 Dec 2003