Coronavirus (Covid-19): Latest updates and information
Skip to main content Skip to navigation

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.

  • 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 Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)
  • 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 ACM-SIAM Symposium on Discrete Algorithms (SODA)
  • 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)
  • Dall'Agno, 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 Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)
  • 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)
  • 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)
  • 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. Simple, deterministic, constant-round coloring in the congested clique. 39th Annual ACM Symposium on Principles of Distributed Computing (PODC 2020), Virtual conference, 3-6 Aug 2020
  • 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
  • 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
  • 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), Online, 01-04 Sep 2020, Published in Leibniz International Proceedings in Informatics (LIPIcs), pp. 12:1-12:20
  • Merino, Arturo, Micka, Ondrej, Mutze, Torsten, 2020. On a combinatorial generation problem of Knuth. 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, Virtual Conference, 10-13 Jan 2021
  • 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 Proceedings of 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
  • 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
  • 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 ACM-SIAM Symposium on Discrete Algorithms
  • Carboni Oliveira, Igor, Kabanets, Valentine, Lu, Zhenjian, Koroth, Sajin, Myrisiotis, Dimitrios, 2020. Algorithms and lower bounds for de Morgan formulas of low-communication leaf gates. Computational Complexity Conference (CCC), 28?31 Jul 2020
  • Carboni Oliveira, Igor, Loff, Bruno, Ilango, Rahul, 2020. NP-hardness of circuit minimization for multi-output functions. Computational Complexity Conference (CCC), 28?31 Jul 2020
  • 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, 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 Leibniz International Proceedings in Informatics (LIPIcs)
  • 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 Leibniz International Proceedings in Informatics (LIPIcs)
  • 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, 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, Henzinger, Monika, Nanongkai, Danupon, 2019. 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
  • 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
  • Czumaj, Artur, Sohler, Christian, 2019. 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 Proceedings of the 60th IEEE Symposium on Foundations of Computer Science (FOCS 2019)
  • Lokshtanov, Daniel, Sridharan, Ramanujan, Saurabh, Saket, Zehavi, Meirav, 2019. 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
  • 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
  • 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 Proceedings of TACAS 2020 (Tools and Algorithms for the Construction and Analysis of Systems)
  • 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
  • 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
  • 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
  • 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
  • Chen, Lijie, Hirahara, Shuichi, Carboni Oliveira, Igor, Pich, Jan, Rajgopal, Ninad, Santhanam, Rahul, 2019. Beyond natural proofs : hardness magnification and locality. Innovations in Theoretical Computer Science, Seattle, USA, 12-14 Jan 2020
  • 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
  • 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., 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
  • Englert, Matthias, Räcke, Harald, Stotz, Richard, 2019. Polylogarithmic guarantees for generalized reordering buffer management. FOCS 2019 60th Annual IEEE Symposium on Foundations of Computer Science, Baltimore, Maryland, 9-12 Nov 2019
  • 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
  • Hubai, Tamàs, Král', Daniel, Parczyk, Olaf, Person, Yury, 2019. Person : more non-bipartite forcing pairs. EuroComb 2019, Bratislava, Slovakia, 26-30 Aug 2019, Published in Acta Mathematica Universitatis Comenianae
  • 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
  • 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
  • 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
  • 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 Leibniz International Proceedings in Informatics (LIPIcs)
  • 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 Leibniz International Proceedings in Informatics (LIPIcs)
  • 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 Leibniz International Proceedings in Informatics (LIPIcs)
  • 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
  • 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
  • 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
  • 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
  • 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 Proceedings of 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), pp. 1-15
  • Jurdzinski, Marcin, Lazic, Ranko, 2018. 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 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
  • 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 Proceedings of LICS 2018, pp. 325-334
  • 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
  • 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
  • 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
  • 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
  • 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 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
  • 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
  • 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 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
  • 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
  • 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
  • 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
  • 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 Leibniz International Proceedings in Informatics (LIPIcs)
  • 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
  • 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
  • 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
  • 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)
  • 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 July 2017, Published in Proceedings of the 44th International Colloquium on Automata, Languages, and Programming
  • 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)
  • 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
  • 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
  • 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
  • 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. 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
  • 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
  • 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
  • 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, 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
  • 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, 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 Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), pp. 94:1-94:13
  • 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
  • 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
  • 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
  • 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)
  • 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)
  • 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)
  • 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
  • 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
  • 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
  • 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
  • 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, 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, 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
  • 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, 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
  • 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. 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, 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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)
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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. 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, 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
  • 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, 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, 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
  • Tiskin, Alexander, 2010. Parallel selection by regular sampling. 16th International Euro-Par Conference on Parallel Processing, Ischia, Italy, August 31 - September 03 2010
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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, 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, 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
  • 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
  • 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. 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, 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
  • 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
  • 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
  • Englert, Matthias, Westermann, Matthias, 2007. Considering suppressed packets improves buffer management in QoS switches. ACM-SIAM symposium on Discrete algorithms, New Orleans, Louisiana, 7-9 Jan 2007, Published in ACM-SIAM symposium on Discrete algorithms, pp. 209-218
  • 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, 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
  • 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
  • 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
  • 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
Royal Society University Research Fellowship Royal Society 01 Oct 2019 30 Sep 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
Theory and Applications of Dynamic Algorithms EPSRC 06 Jan 2020 05 Jan 2023
Weizmann - UK Joint Research Program: Combinatorial and Algorithmic Primitives for Modern Networks Weizmann Institute of Science 01 Oct 2018 30 Sep 2022
IBM Faculty Award: Efficient Processing Methods for Big Graphs IBM 01 Oct 2017 30 Aug 2022
Large Discrete Structures (ERC Consolidator Grant Proposal) EU 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 14 Jan 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
Petri Net Reachability Conjecture Leverhulme Trust 01 Oct 2017 31 Dec 2018
Sublinear Algorithms for Big Graphs EPSRC 01 Jan 2016 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 Subproject for Institution # 34195 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 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
Sigma: A New Online Learning System JISC 01 Jul 2013 30 Sep 2013
PATTERN MATCHING ALGORITHMS FOR STREAMING DATA (PDF FOR BEN SACH) EPSRC 01 Oct 2010 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 - J Hladky PI London Mathematical Society 18 Jul 2010 25 Jul 2010
Workshop on extremal and probabilistic combinatorics - PI is J Hladky, PhD student British Combinatorial Committee 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