- 'Agrawal, Akanksha, 'Kanesh, Lawqueen, 'Panolan, Fahad, 'Ramanujan, M. S., 'Saurabh, Saket, 2022. 'A fixed-parameter tractable algorithm for elimination distance to bounded degree graphs. SIAM Journal on Discrete Mathematics, 36 (2), pp. 911-921
- 'Fomin, Fedor V., 'Panolan, Fahad, 'Ramanujan, Maadapuzhi Sridharan, 'Saurabh, Saket, 2022. 'On the optimality of pseudo-polynomial algorithms for integer programming. Mathematical Programming Series B
- 'Bhattacharya, Sayan, 'Grandoni, Fabrizio, 'Kulkarni, Janardhan, 'Liu, Quanquan C., 'Solomon, Shay, 2022. 'Fully dynamic (? +1)-coloring in O(1) update time. ACM Transactions on Algorithms, 18 (2), pp. 1-25
- 'Chiesa, Alessandro, 'Forbes, Michael, 'Gur, Tom, 'Spooner, Nicholas, 2022. 'Spatial isolation implies zero knowledge even in a quantum world. Journal of the ACM, 69 (2)
- 'Dall'Agnol, Marcel, 'Gur, Tom, 'Moulik, Subhayan Roy, 'Thaler, Justin, 2022. 'Quantum proofs of proximity. Quantum
- Gregor, Petr, Jäger, Sven, Mutze, Torsten, Sawada, Joe, Wille, Kaja, 2022. Gray codes and symmetric chains. Journal of Combinatorial Theory, Series B, 153, pp. 31-60
- 'Elizabeth, Hartung, 'Hoang, Hung P., 'Mutze, Torsten, 'Williams, Aaron, 2022. 'Combinatorial generation via permutation languages. I. Fundamentals. Transactions of the American Mathematical Society, 375, pp. 2255-2291
- 'Merino, Arturo, 'Micka, Ondrej, 'Mutze, Torsten, 2022. 'On a combinatorial generation problem of Knuth. SIAM Journal on Computing, 51 (3), pp. 379-423
- Merino, Arturo, Mutze, Torsten, 2022. Combinatorial generation via permutation languages. III. Rectangulations. Discrete & Computational Geometry
- 'Lu, Zhenjian, 'Oliveira, Igor C., 2022. 'Theory and applications of probabilistic Kolmogorov complexity. Bulletin of EATCS, 137
- 'Chistikov, Dmitry, 'Kiefer, Stefan, 'Murawski, Andrzej S., 'Purser, David, 2022. 'The big-O problem. Logical Methods in Computer Science, 18 (1), pp. 40:1-40:50
- 'Adamaszek, Anna, 'Czumaj, Artur, 'Englert, Matthias, 'R?cke, Harald, 2022. 'Almost tight bounds for reordering buffer management. SIAM Journal on Computing, 51 (3), pp. 701-722
- 'Hancock, Robert, 'Kr?l', Daniel, 'Krnc, Matja?, 'Volec, Jan, 2022. 'Toward characterizing locally common graphs. Random Structures & Algorithms
- 'Kr?l?, Daniel, 'Noel, Jonathan A., 'Norine, S., 'Volec, J., 'Wei, F., 2022. 'Non-bipartite k-common graphs. Combinatorica, 42, pp. 87-114
- Cooper, Jacob W., Grzesik, Andrzej, Kabela, Adam, Král', Daniel, 2022. Packing and covering directed triangles asymptotically. European Journal of Combinatorics, 101
- 'Grzesik, Andrzej, 'Král', Daniel, 'Lovász, László M., 'Volec, Jan, 2022. 'Cycles of a given length in tournaments. Journal of Combinatorial Theory, Series B
- 'Cooper, Jacob W., 'Král?, Daniel, 'Lamaison, Ander, 'Mohr, Samuel, 2022. 'Quasirandom Latin squares. Random Structures & Algorithms, 61 (2), pp. 298-308
- 'Ganian, Robert, 'Ordyniak, Sebastian, 'Ramanujan, Maadapuzhi Sridharan, 2021. 'On structural parameterizations of the edge disjoint paths problem. Algorithmica, 83 (6), pp. 1605-1637
- 'Bergougnoux, Benjamin, 'Eiben, Eduard, 'Ganian, Robert, 'Ordyniak, Sebastian, 'Ramanujan, Maadapuzhi Sridharan, 2021. 'Towards a polynomial kernel for directed feedback vertex set. Algorithmica, 83 (5), pp. 1201-1221
- Gur, Tom, Lachish, Oded, 2021. On the power of relaxed local decoding algorithms. SIAM Journal on Computing, 50 (2), pp. 788-813
- Chiesa, Alessandro, Gur, Tom, Shinkar, Igor, 2021. Relaxed locally correctable codes with nearly-linear block length and constant query complexity. SIAM Journal of Computing
- Aichholzer, Oswin, Cardinal, Jean, Huynh, Tony, Knauer, Kolja, Mutze, Torsten, Steiner, Raphael, Vogtenhuber, Birgit, 2021. Flip distances between graph orientations. Algorithmica, 83, pp. 116-143
- 'Hoang, Hung P., 'Mutze, Torsten, 2021. 'Combinatorial generation via permutation languages. II. Lattice congruences. Israel Journal of Mathematics, 244, pp. 359-417
- Mutze, Torsten, Nummenpalo, Jerri, Walczak, Bartosz, 2021. Sparse Kneser graphs are Hamiltonian. Journal of the London Mathematical Society, 103 (4), pp. 1253-1275
- Milich, Marcel, Mutze, Torsten, Pergel, Martin, 2021. On flips in planar matchings. Discrete Applied Mathematics, 289, pp. 427-445
- 'Daviaud, Laure, 'Jurdzinski, Marcin, 'Lazic, Ranko, 'Mazowiecki, Filip, 'P?rez, Guillermo A., 'Worrell, James, 2021. 'When are emptiness and containment decidable for probabilistic automata?. Journal of Computer and System Sciences, 119, pp. 78-96
- Englert, Matthias, Hofman, Piotr, Lasota, Slawomir, Lazic, Ranko, Leroux, Jérôme, Straszynski, Juliusz, 2021. A lower bound for the coverability problem in acyclic pushdown VAS. Information Processing Letters, 167
- 'Englert, Matthias, 'Mezlaf, David, 'Westermann, Matthias, 2021. 'Online makespan scheduling with job migration on uniform machines. Algorithmica, 83, pp. 3537-3566
- Blondin, Michael, Englert, Matthias, Finkel, Alain, Göller, Stefan, Haase, Christoph, Lazic, Ranko, McKenzie, Pierre, Totzke, Patrick, 2021. The reachability problem for two-dimensional vector addition systems with states. Journal of the ACM, 68 (5), pp. 1-43
- Dvorák, Zdenek, Král', Daniel, Thomas, Robin, 2021. Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies. Journal of Combinatorial Theory Series B, 150, pp. 244-269
- Dvorák, Zdenek, Král', Daniel, Thomas, Robin, 2021. Three-coloring triangle-free graphs on surfaces IV. Bounding face sizes of 4-critical graphs. Journal of Combinatorial Theory, Series B, 150, pp. 270-304
- Dvorák, Zdenek, Hebdige , Michael, Hlasek, Filip, Král', Daniel, Noel, Jonathan A., 2021. Cyclic coloring of plane graphs with maximum face size 16 and 17. European Journal of Combinatorics, 94
- Czerwinski, Wojciech, Lasota, Slawomir, Lazic, Ranko, Leroux, Jérôme, Mazowiecki, Filip, 2021. The reachability problem for petri nets is not elementary. Journal of the ACM, 68 (1)
- Lazic, Ranko, Schmitz, Sylvain, 2021. The ideal view on Rackoff's coverability technique. Information and Computation, 277
- Czumaj, Artur, Davies, Peter, 2021. Exploiting spontaneous transmissions for broadcasting and leader election in radio networks. Journal of the ACM, 68 (2)
- Czumaj, Artur, Davies, Peter, Parter, Merav, 2021. Graph sparsification for derandomizing massively parallel computation with low space. ACM Transactions on Algorithms, 17 (2)
- 'Chikin, Nikolay, 'Gurvich, Vladimir, 'Knop, Konstantin, 'Paterson, Michael S., 'Vyalyi, Michael, 2021. 'More about exact slow k-Nim. Integers: Electronic Journal of Combinatorial Number Theory, 21
- Gutin, Gregory, Ramanujan, M. S., Reidl, Felix, Wahlström, Magnus, 2020. Alternative parameterizations of Metric Dimension. Theoretical Computer Science, 806, pp. 133-143
- Gur, Tom, Shinkar, Igor, 2020. An entropy lower bound for non-malleable extractors. IEEE Transactions on Information Theory, 66 (5), pp. 2904-2911
- Mutze, Torsten, Scheucher, Manfred, 2020. On L-shaped point set embeddings of trees : first non-embeddable examples. Journal of Graph Algorithms and Applications, 24 (3), pp. 343-369
- Mutze, Torsten, Nummenpalo, Jerri, 2020. A constant-time algorithm for middle levels Gray codes. Algorithmica, 82, pp. 1239-1258
- Hartung, Elizabeth, Hoang, Hung, Mutze, Torsten, Williams, Aaron, 2020. Combinatorial generation via permutation languages. I. Fundamentals. Transactions of the American Mathematical Society
- Felsner, Stefan, Kleist, Linda, Mutze, Torsten, Sering, Leon, 2020. Rainbow cycles in flip graphs. SIAM Journal on Discrete Mathematics, 34 (1), pp. 1-39
- Oliveira, Igor C., Bydzovsky, Jan, Krajicek, Jan, 2020. Consistency of circuit lower bounds with bounded theories. Logical Methods in Computer Science, 16 (2), pp. 12:1-12:16
- Chistikov, Dmitry, Goulko, Olga, Kent, Adrian, Paterson, Michael S., 2020. Globe-hopping. Proceedings of the Royal Society A : mathematical, physical and engineering sciences, 476 (2238)
- Kenyon, Robert V., Král', Daniel, Radin, C., Winkler, P., 2020. Permutations with fixed pattern densities. Random Structures and Algorithms, 56 (1), pp. 220-250
- Chan, Timothy F. N., Grzesik, Andrzej, Král', Daniel, Noel, Jonathan A., 2020. Cycles of length three and four in tournaments. Journal of Combinatorial Theory, Series A, 175
- Chan, T., Král', Daniel, Noel, Jonathan A., Pehova, Yanitsa, Sharifzadeh, Maryam, Volec, Jan, 2020. Characterization of quasirandom permutations by a pattern sum. Random Structures and Algorithms, 57 (4), pp. 920-939
- Dvorák, Zdenek, Král', Daniel, Thomas, Robin, 2020. Three-coloring triangle-free graphs on surfaces III. Graphs of girth five. Journal of Combinatorial Theory, Series B, 145, pp. 376-432
- Král', Daniel, Lovasz, Laszlo M., Noel, Jonathan A., Sosnovec, Jakub, 2020. Finitely forcible graphons with an almost arbitrary structure. Discrete Analysis
- Grzesik, Andrzej, Král', Daniel, Lovász, Miklós, 2020. Elusive extremal graphs. Proceedings of the London Mathematical Society, 121 (6), pp. 1685-1736
- Conway, J. H., Paterson, Michael S., Moscow, U. S .S. R., 2020. A headache-causing problem. The American Mathematical Monthly, 127 (4), pp. 291-296
- Gutin, Gregory, Ramanujan, M.S., Reidl, Felix, Wahlström, Magnus, 2019. Path-contractions, edge deletions and connectivity preservation. Journal of Computer and System Sciences, 101, pp. 1-20
- Goldreich, Oded, Gur, Tom, Komargodski, Ilan, 2019. Strong locally testable codes with relaxed local decoders. ACM Transactions on Computation Theory, 11 (3), pp. 1-38
- Blais, Eric, Canonne, Clément L., Gur, Tom, 2019. Distribution testing lower bounds via reductions from communication complexity. ACM Transactions on Computation Theory, 11 (2), pp. 1-37
- Chistikov, Dmitry, Martyugin, Pavel, Shirmohammadi, Mahsa, 2019. Synchronizing automata over nested words. Journal of Automata, Languages and Combinatorics, 24 (2-4), pp. 219-251
- Chistikov, Dmitry, Czerwinski, Wojciech, Hofman, Piotr, Pilipczuk, Michal, Wehar, Michael, 2019. Shortest paths in one-counter systems. Logical Methods in Computer Science, 15 (1), pp. 19:1-19:28
- Král', Daniel, Martins, Taísa L., Pach, Péter Pál, Wrochna, Marcin, 2019. The step Sidorenko property and non-norming edge-transitive graphs. Journal of Combinatorial Theory, Series A, 162, pp. 34-54
- Glebov, Roman, Král', Daniel, Volec, Jan, 2019. Compactness and finite forcibility of graphons. Journal of the European Mathematical Society, 21 (10), pp. 3199-3223
- Král', Daniel, Norin, Sergey, Volec, Jan, 2019. A bound on the inducibility of cycles. Journal of Combinatorial Theory, Series A, 161, pp. 359-363
- Král', Daniel, Martins, Taísa L., Pach, Péter Pál, Wrochna, Marcin, 2019. The step Sidorenko property and non-norming edge-transitive graphs. Journal of Combinatorial Theory Series A, 162, pp. 34-54
- Glebov, Roman, Klimo?ová, Tereza, Král', Daniel, 2019. Infinite dimensional finitely forcible graphon. Proceedings of the London Mathematical Society, 118 (4), pp. 826-856
- Král', Daniel, Lidicky, Bernard, Martins, Taisa, Pehova, Yanitsa, 2019. Decomposing graphs into edges and triangles. Combinatorics, Probability and Computing, 28 (3), pp. 465-472
- Král', Daniel, Norin, Sergey, Volec, Jan, 2019. A bound on the inducibility of cycles. Journal of Combinatorial Theory Series A, 161, pp. 359-363
- Clemente, Lorenzo, Lasota, Slawomir, Lazic, Ranko, Mazowiecki, Filip, 2019. Binary reachability of timed-register pushdown automata and branching vector addition systems. ACM Transactions on Computational Logic, 20 (3), pp. 1-31
- Czumaj, Artur, Lacki, Jakub, Madry, Aleksander, Mitrovic, Slobodan, Onak, Krzysztof, Sankowski, Piotr, 2019. Round compression for parallel matching algorithms. SIAM Journal of Computing, 49 (5)
- Lokshtanov, Daniel, Ramanujan, Maadapuzhi Sridharan, Saurabh, Saket, 2018. Linear time parameterized algorithms for subset feedback vertex set. ACM Transactions on Algorithms, 14 (1), pp. 1-37
- Bhattacharya, Sayan, Henzinger, Monika, Italiano, Giuseppe F., 2018. Deterministic fully dynamic data structures for vertex cover and matching. SIAM Journal on Computing, 47 (3), pp. 859-887
- Gur, Tom, Rothblum, Ron D., 2018. Non-interactive proofs of proximity. Computational Complexity, 27 (1), pp. 99-207
- Canonne, Clément L., Gur, Tom, 2018. An adaptivity hierarchy theorem for property testing. computational complexity, 27 (4), pp. 671-716
- Gregor, Petr, Mutze, Torsten, Nummenpalo, Jerri, 2018. A short proof of the middle levels theorem. Discrete Analysis, pp. 1-12
- Mutze, Torsten, Nummenpalo, Jerri, 2018. Efficient computation of middle levels Gray codes. ACM Transactions on Algorithms, 14 (2)
- Krajicek, Jan, Oliveira, Igor Carboni, 2018. On monotone circuits with local oracles and clique lower bounds. Chicago Journal of Theoretical Computer Science, 24, pp. 1-18
- Chistikov, Dmitry, Haase, Christoph, Halfon, Simon, 2018. Context-free commutative grammars with integer counters and resets. Theoretical Computer Science, 735, pp. 147-161
- Czumaj, Artur, Deligkas, Argyrios, Fasoulakis, Michail, Fearnley, John, Jurdzinski, Marcin, Savani, Rahul, 2018. Distributed methods for computing approximate equilibria. Algorithmica
- Al-Bawani, Kamal, Englert, Matthias, Westermann, Matthias, 2018. Online packet scheduling for CIOQ and buffered crossbar switches. Algorithmica, 80, pp. 3861-3888
- Al-Bawani, Kamal, Englert, Matthias, Westermann, Matthias, 2018. Comparison-based buffer management in QoS switches. Algorithmica, 80 (3), pp. 1073-1092
- Adamaszek, Anna, Czumaj, Artur, Englert, Matthias, Räcke , Harald, 2018. An O(log k)-competitive algorithm for generalized caching. ACM Transactions on Algorithms, 15 (1), pp. 1-18
- Cooper, Jacob W., Král', Daniel, Martins, Taísa L., 2018. Finitely forcible graph limits are universal. Advances in Mathematics, 340, pp. 819-854
- Dvorák, Zdenek, Král', Daniel, Thomas, Robin, 2018. Three-coloring triangle-free graphs on surfaces II. 4-critical graphs in a disk. Journal of Combinatorial Theory Series B, 132, pp. 1-46
- Cooper, Jacob W., Grzesik, Andrzej, Král', Daniel, 2018. Optimal-size clique transversals in chordal graphs. Journal of Graph Theory, 89 (4), pp. 479-493
- Cooper, Jacob W., Grzesik, Andrzej, Král', Daniel, 2018. Optimal-size clique transversals in chordal graphs. Journal of Graph Theory, 89 (4), pp. 479-493
- Cooper, Jacob W., Kaiser, Tomas, Král', Daniel, Noel, Jonathan, 2018. Weak regularity and finitely forcible graph limits. Transactions of the American Mathematical Society
- Kloster, Kyle, Král', Daniel, Sullivan, Blair D., 2018. Walk entropy and walk-regularity. Linear Algebra and Its Applications, 546, pp. 115-121
- Czumaj, Artur, Davies, Peter, 2018. Deterministic communication in radio networks. SIAM Journal on Computing, 47 (1), pp. 218-240
- Adamaszek, Anna, Czumaj, Artur, Lingas, Andrzej, Wojtaszczyk, Jakub Onufry, 2018. Approximation Schemes for Capacitated Geometric Network Design. SIAM Journal on Discrete Mathematics, 32 (4), pp. 2720-2746
- Mutze, Torsten, Su, Pascal, 2017. Bipartite Kneser graphs are Hamiltonian. Combinatorica, 37 (6), pp. 1207-1219
- Krajicek, Jan, Oliveira, Igor Carboni, 2017. Unprovability of circuit upper bounds in Cook's theory PV. Logical Methods in Computer Science, 13 (1)
- Gauy, Marcelo M., Han, Hiep, Oliveira, Igor C., 2017. Erdos?Ko?Rado for random hypergraphs : asymptotics and stability. Combinatorics, Probability and Computing, 26 (3), pp. 406-422
- Chistikov, Dmitry, Kiefer, Stefan, Maru?ic, Ines, Shirmohammadi, Mahsa, Worrell, James, 2017. Nonnegative matrix factorization requires irrationality. SIAM Journal on Applied Algebra and Geometry, 1 (1), pp. 285-307
- Chistikov, Dmitry, Dimitrova, Rayna, Majumdar, Rupak, 2017. Approximate counting in SMT and value estimation for probabilistic programs. ACTA Informatica, 54 (8), pp. 729-764
- Kardos, Frantisek, Král', Daniel, Liebenau, Anita, Mach, Luká?, 2017. First order convergence of matroids. European Journal of Combinatorics, 59, pp. 150-168
- Glebov, Roman, Hoppen, Carlos, Klimosova, Tereza, Kohayakawa, Yoshiharu, Král', Daniel, Liu, Hong, 2017. Densities in large permutations and parameter testing. European Journal of Combinatorics, 60, pp. 89-99
- Grzesik, Andrzej, Král', Daniel, Lovasz, Laszlo Miklos, 2017. Extremal graph theory and finite forcibility. Electronic Notes in Discrete Mathematics, 61, pp. 541-547
- Cohen-Addad, Vincent, Hebdige, Michael, Král', Daniel, Li, Zhentao, Salgado, Esteban, 2017. Steinberg's conjecture is false. Journal of Combinatorial Theory, Series B, 122, pp. 452-456
- Mutze, Torsten, 2016. Proof of the middle levels conjecture. Proceedings of the London Mathematical Society, 112 (4), pp. 677-713
- Englert, Matthias, Röglin, Heiko, Vocking, Berthold, 2016. Smoothed analysis of the 2-Opt algorithm for the general TSP. ACM Transactions on Algorithms, 13 (1)
- Hebdige, Michael, Král', Daniel, 2016. Third case of the cyclic coloring conjecture. SIAM Journal on Discrete Mathematics, 30 (1), pp. 525-548
- Glebov, Roman, Král', Daniel, Volec, Jan, 2016. A problem of Erdos and Sós on 3-graphs. Israel Journal of Mathematics, 211 (1), pp. 349-366
- Hladký, Jan, Král', Daniel, Norine, Serguei, 2016. Counting flags in triangle-free digraphs. Combinatorica, 37 (1), pp. 49-76
- Lazic, Ranko, Ouaknine, Joel, Worrell, James, 2016. Zeno, Hercules, and the Hydra : safety metric temporal logic is ACKERMANN-complete. ACM Transactions on Computational Logic, 17 (3)
- Oliveira, Igor Carboni, Thatte, Bhalchandra D., 2015. An algebraic formulation of the graph reconstruction conjecture. Journal of Graph Theory, 81 (4), pp. 351-363
- Tiskin, Alexander, 2015. Fast distance multiplication of unit-Monge matrices. Algorithmica, 71 (4), pp. 859-888
- Glebov, Roman, Grzesik, Andrzej, Klimo?ová, Tereza, Král', Daniel, 2015. Finitely forcible graphons and permutons. Journal of Combinatorial Theory. Series B, 110 (Number), pp. 112-135
- Ganian, Robert, Hlinený, Petr, Král', Daniel, Obdr?álek, Jan, Schwartz, Jarett, Teska, Jakub, 2015. FO model checking of interval graphs. Logical Methods in Computer Science, 11 (4), pp. 1-20
- Lazic, Ranko, Schmitz, Sylvain, 2015. Nonelementary complexities for branching VASS, MELL, and extensions.. ACM Transactions on Computational Logic (TOCL), 16 (3)
- Chistikov, Dmitry, Fedorova, Valentina, Voronenko, Andrey, 2014. Certificates of non-membership for classes of read-once functions. Fundamenta Informaticae, 132 (1), pp. 63-77
- Wandelt, Sebastian, Wang, Jiaying, Leser, Ulf, Deng, Dong, Gerdjikov, Stefan, Mishra, Shashwat, Mitankin, Petar, Patil, Manish, Siragusa, Enrico, Tiskin, Alexander, Wang, Wei, 2014. State-of-the-art in string similarity search and join. SIGMOD Record, 43 (1), pp. 64-76
- Deineko, Vladimir G., Klinz, Bettina, Tiskin, Alexander, Woeginger, Gerhard J., 2014. Four-point conditions for the TSP : the complete complexity classification. Discrete Optimization, 14, pp. 147-159
- Englert, Matthias, Gupta, Anupam, Krauthgamer, Robert, Räcke, Harald, Talgam-Cohen, Inbal, Talwar, Kunal, 2014. Vertex sparsifiers : new results from old techniques. SIAM Journal on Computing, 43 (4), pp. 1239-1262
- Englert, Matthias, Röglin, Heiko, Vöcking, Berthold, 2014. Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP. Algorithmica, 68 (1), pp. 190-264
- Englert, Matthias, Özmen, Deniz, Westermann, Matthias, 2014. The power of reordering for online minimum makespan scheduling. SIAM Journal on Computing, 43 (3), pp. 1220-1237
- Ferguson, David G. (Researcher in mathematics), Kaiser, Thomá?, Král', Daniel, 2014. The fractional chromatic number of triangle-free subcubic graphs. European Journal of Combinatorics, 35, pp. 184-220
- Czumaj, Artur, Goldreich, Oded, Ron, Dana, Seshadhri, C., Shapira, Asaf, Sohler, Christian, 2014. Finding cycles and trees in sublinear time. Random Structures & Algorithms, 45 (2), pp. 139-184
- Demri, Stéphane P., Jurdzinski, Marcin, Lachish, Oded, Lazic, Ranko, 2013. The covering and boundedness problems for branching vector addition systems. Journal of Computer and System Sciences, 79 (1), pp. 23-38
- Cummings, James, Král', Daniel, Pfender, Florian, Sperfeld, Konrad, Treglown, Andrew, Young, Michael, 2013. Monochromatic triangles in three-coloured graphs. Journal of Combinatorial Theory, Series B, 103 (4), pp. 489-503
- Král', Daniel, Pikhurko, Oleg, 2013. Quasirandom permutations are characterized by 4-point densities. Geometric and Functional Analysis, 23 (2), pp. 570-579
- Král', Daniel, Liu, Chun-Hung, Sereni, Jean-Sébastien, Whalen, Peter, Yilma, Zelealem B., 2013. A new bound for the 2/3 conjecture. Combinatorics, Probability and Computing, 22 (3), pp. 384-393
- Hatami, Hamed, Hladký, Jan, Král', Daniel, Norine, Serguei, Razborov, Alexander, 2013. On the number of pentagons in triangle-free graphs. Journal of Combinatorial Theory, Series A, 120 (3), pp. 722-732
- Hladký, Jan, Král', Daniel, Norine, Serguei, 2013. Rank of divisors on tropical curves. Journal of Combinatorial Theory, Series A, 120 (7), pp. 1521-1538
- Dvorák, Zdenek, Král', Daniel, Thomas, Robin, 2013. Testing first-order properties for subclasses of sparse graphs. Journal of the ACM, 60 (5)
- Baxter, Laura, Jironkin, Aleksey, Hickman, R. D. G., Moore, Jonathan D., Barrington, Christopher, Krusche, Peter, Dyer, Nigel, Buchanan-Wollaston, Vicky, Tiskin, Alexander, Beynon, Jim, Denby, Katherine J., Ott, Sascha, 2012. Conserved noncoding sequences highlight shared components of regulatory networks in dicotyledonous plants. The Plant Cell, Vol.24 (No.10), pp. 3949-3965
- Englert, Matthias, Westermann, Matthias, 2012. Considering suppressed packets improves buffer management in quality of service switches. SIAM Journal on Computing, 41 (5), pp. 1166-1192
- Englert, Matthias, 2012. An overview of some results for reordering buffers. Computer Science - Research and Developmen, Vol.27 (No.3), pp. 217-223
- Král', Daniel, Mach, Luká?, Sereni, Jean-Sébastien, 2012. A new lower bound based on Gromov's method of selecting heavily covered points. Discrete & Computational Geometry, Vol.48 (No.2), pp. 487-498
- Král', Daniel, Serra, Oriol, Vena, Lluís, 2012. A removal lemma for systems of linear equations over finite fields. Israel Journal of Mathematics, Vol.187 (No.1), pp. 193-207
- Rutkowski, Michal, Ph.D., Lazic, Ranko, Jurdzinski, Marcin, 2011. Average-price-per-reward games on hybrid automata with strong resets. International Journal on Software Tools for Technology Transfer, Vol.13 (No.6), pp. 553-569
- Jurdzinski, Marcin, Lazic, Ranko, 2011. Alternating automata on data trees and XPath satisfiability. ACM Transactions on Computational Logic (TOCL), 12 (3), pp. 1-21
- Korpelainen, Nicholas, Lozin, Vadim V., Malyshev, Dmitriy S., Tiskin, Alexander, 2011. Boundary properties of graphs for algorithmic graph problems. Theoretical Computer Science, Vol.412 (No.29), pp. 3545-3554
- Esperet, Louis, Kardo?, Franti?ek, King, Andrew D., Král', Daniel, Norine, Serguei, 2011. Exponentially many perfect matchings in cubic graphs. Advances in Mathematics, Vol.227 (No.4), pp. 1646-1664
- Kaiser, Tomá?, King, Andrew D., Král', Daniel, 2011. Fractional total colourings of graphs of high girth. Journal of Combinatorial Theory, Series B, Vol. 101 (No. 6), pp. 383-402
- Lazic, Ranko, 2011. Safety alternating automata on data words. ACM Transactions on Computational Logic (TOCL), Vol.12 (No.2), pp. 1-24
- Aziz, Haris, Bachrach, Yoram, Elkind, Edith, Paterson, Michael S., 2011. False-name manipulations in weighted voting games. Journal of Artificial Intelligence, Vol.40, pp. 57-93
- Picot, Emma, Krusche, Peter, Tiskin, Alexander, Carré, Isabelle A., Ott, Sascha, 2010. Evolutionary analysis of regulatory sequences (EARS) in plants. Plant Journal, Vol.64 (No.1), pp. 165-176
- Englert, Matthias, Raecke, Harald, Westermann, Matthias, 2010. Reordering buffers for general metric spaces. Theory of Computing, Vol.6 (No.1), pp. 27-46
- Englert, Matthias, Franke, T., Olbrich, L., 2010. Sensitivity of wardrop equilibria. Theory of Computing Systems, 47 (1), pp. 3-14
- Král', Daniel, Mácajová, Edita, Pór, Attila, Sereni, Jean-Sébastien, 2010. Characterisation results for Steiner Triple Systems and their application to edge-colourings of cubic graphs. Canadian Journal of Mathematics, Vol.62 (No.2), pp. 355-381
- Bakewell, Adam, Dimovski, Aleksandar, Ghica, Dan R., Lazic, Ranko, 2010. Data-abstraction refinement : a game semantic approach. International Journal on Software Tools for Technology Transfer, Vol.12 (No.5), pp. 373-389
- Lazic, Ranko, 2010. The reachability problem for branching vector addition systems requires doubly-exponential space. Information Processing Letters, Vol.110 (No.17), pp. 740-745
- Demri, Stéphane P., Lazic, Ranko, Sangnier, Arnaud, 2010. Model checking memoryful linear-time logics over one-counter automata. Theoretical Computer Science, Vol.411 (No.22-24), pp. 2298-2316
- Czumaj, Artur, Krysta, Piotr, Vöcking, Berthold, 2010. Selfish traffic allocation for server farms. SIAM Journal on Computing, Vol.39 (No.5), pp. 1957-1987
- Adamaszek, Anna, Czumaj, Artur, Lingas, Andrzej, 2010. PTAS for k-tour cover problem on the plane for moderately large values of k. International Journal of Foundations of Computer Science, 21 (6), pp. 893-904
- Deineko, Vladimir G., Tiskin, Alexander, 2009. Min-weight double-tree shortcutting for metric TSP : bounding the approximation ratio. Electronic Notes in Discrete Mathematics, 32, pp. 19-26
- Deineko, Vladimir G., Tiskin, Alexander, 2009. Fast minimum-weight double-tree shortcutting for metric TSP. Journal of Experimental Algorithmics, Vol.14
- Tiskin, Alexander, 2009. Faster Subsequence Recognition in Compressed Strings. Journal of Mathematical Sciences, 158 (5), pp. 759-769
- Englert, Matthias, Röglin, H., Westermann, M., 2009. Evaluation of online strategies for reordering buffers. Experimental Algorithmics (JEA), 14
- Englert, Matthias, Westermann, Matthias, 2009. Lower and upper bounds on FIFO buffer management in QoS switches. Algorithmica, 53 (4), pp. 523-548
- Král', Daniel, Serra, Oriol, Vena, Lluís, 2009. A combinatorial proof of the Removal Lemma for Groups. Journal of Combinatorial Theory, Series A, Vol.116 (No.4), pp. 971-978
- Demri, Stéphane P., Lazic, Ranko, 2009. LTL with the freeze quantifier and register automata. ACM Transactions on Computational Logic (TOCL), Vol.10 (No.3)
- Czumaj, Artur, Sohler, Christian, 2009. Small space representations for metric min-sum k-clustering and their applications. Theory of Computing Systems, 46 (3), pp. 416-442
- Czumaj, Artur, Shapira, Asaf, Sohler, Christian, 2009. Testing hereditary properties of nonexpanding bounded-degree graphs. SIAM Journal on Computing, 38 (6), pp. 2499-2510
- Czumaj, Artur, Sohler, Christian, 2009. Estimating the weight of metric minimum spanning trees in sublinear time. SIAM Journal on Computing, Vol.39 (No.3), pp. 904-922
- Czumaj, Artur, Lingas, Andrzej, 2009. Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication. SIAM Journal on Computing, 39 (2), pp. 431-444
- Paterson, Michael S., Zwick, Uri, 2009. Overhang. American Mathematical Monthly, Vol.116 (No.1), pp. 19-44
- Paterson, Michael S., Peres, Y., Thorup, Mikkel, Winkler, P., Zwick, Uri, 2009. Maximum overhang. American Mathematical Monthly, Vol.116 (No.9), pp. 765-787
- Jurdzinski, Marcin, Laroussinie, Francois, Sproston, Jeremy, 2008. Model checking probabilistic timed automata with one or two clocks. Logical Methods in Computer Science, Vol.4 (No.3)
- Jurdzinski, Marcin, Paterson, Michael S., Zwick, Uri, 2008. A deterministic subexponential algorithm for solving parity games. SIAM Journal on Computing, Vol.38 (No.4), pp. 1519-1532
- Tiskin, Alexander, 2008. Semi-local string comparison : algorithmic techniques and applications. Mathematics in Computer Science, 1 (4), pp. 571-603
- Tiskin, Alexander, 2008. Semi-local longest common subsequences in subquadratic time. Journal of Discrete Algorithms, 6 (4), pp. 570-581
- Lazic, Ranko, Newcomb, Tom, Ouaknine, Joel, Roscoe, A. W., Worrell, James, 2008. Nets with tokens which carry data. Fundamenta Informaticae, Vol.88 (No.3), pp. 251-274
- Czumaj, Artur, Sohler, Christian, 2008. Testing Euclidean minimum spanning trees in the plane. ACM Transactions on Algorithms, 4 (3)
- Tiskin, Alexander, 2007. Communication-efficient parallel generic pairwise elimination. Future Generation Computer Systems, 23 (2), pp. 179-188
- Tiskin, Alexander, 2007. Packing tripods : narrowing the density gap. Discrete Mathematics, 307 (16), pp. 1973-1981
- Czumaj, Artur, Kowaluk, Miroslaw, Lingas, Andrzej, 2007. Faster algorithms for finding lowest common ancestors in directed acyclic graphs. Theoretical Computer Science, Vol.380 (No.1-2), pp. 37-46
- Dyer, Martin, Goldberg, Leslie Ann, Paterson, Michael S., 2007. On counting homomorphisms to directed acyclic graphs. Journal of the ACM, Vol.54 (No.6)
- Ironya, Dror, Sivan, Toledo, Tiskin, Alexander, 2004. Communication lower bounds for distributed-memory matrix multiplication. Journal of Parallel and Distributed Computing, 64 (9), pp. 1017-1026
- Martin, J. M. R, Tiskin, Alexander, 2004. Dynamic BSP : towards a flexible approach to parallel computing over the grid. Communicating Process Architectures, pp. 219-226
- Goldberg, Leslie Ann, Jerrum, Mark, Paterson, Michael S., 2003. The computational complexity of two-state spin systems. Random Structures & Algorithms, 23 (2), pp. 133-154
- Tiskin, Alexander, 2002. Bulk-synchronous parallel Gaussian elimination. Journal of Mathematical Sciences, 108 (6), pp. 977-991
- Goldberg, Leslie Ann, Paterson, Michael S., Srinivasan, Aravind, Sweedyk, Elizabeth, 2001. Better approximation guarantees for job-shop scheduling. SIAM Journal on Discrete Mathematics, 14 (1), pp. 67-92
- Goldberg, Leslie Ann, MacKenzie, Phil, Paterson, Michael S., Srinivasan, Aravind, 2000. Contention resolution with constant expected delay. Journal of the ACM, 47 (6), pp. 1048-1096
- Agarwala, Richa, Bafna, Vineet, Farach, Martin, Paterson, Michael S., Thorup, Mikkel, 1999. On the approximability of numerical taxonomy (fitting distances by tree metrics). SIAM Journal on Computing, 28 (3), pp. 1073-1085
- Paterson, Michael S., Przytycka, Teresa, 1996. On the complexity of string folding. Discrete Applied Mathematics, 71 (1-3), pp. 217-230
- Miltersen, Peter Bro, Paterson, Michael S., Tarui, Jun, 1996. The asymptotic complexity of merging networks. Journal of the ACM, 43 (1), pp. 147-165
- Fischer, Michael J., Paterson, Michael S., 1994. Fishspear : a priority queue algorithm. Journal of the ACM, 41 (1), pp. 3-30
- Zwick, Uri, Paterson, Michael S., 1993. The memory game. Theoretical Computer Science, 110 (1), pp. 169-196

- Lazic, Ranko, Totzke, Patrick, 2017. What makes petri nets harder to verify : stack or data?, Concurrency, security, and puzzles : Festschrift for A.W. Roscoe on the occasion of his 60th birthday. In Concurrency, Security, and Puzzles : Essays Dedicated to Andrew William Roscoe on the Occasion of His 60th Birthday, Springer, pp. 144-161
- Guo, Siyao, Malkin, Tal, Oliveira, Igor C., Rosen, Alon, 2015. The power of negations in cryptography. In Dodis, Yevgeniy; Nielsen, Jesper Buus (eds.), Theory of Cryptography : 12th International Conference, TCC 2015, Warsaw, Poland, March 23-25, 2015, Proceedings, Part I, Springer-Verlag Berlin Heidelberg, pp. 36-65
- Czumaj, Artur, Fasoulakis, Michail, Jurdzinski, Marcin, 2014. Approximate well-supported Nash equilibria in symmetric bimatrix games. In Lavi, Ron (ed.), Algorithmic Game Theory : 7th International Symposium, SAGT 2014, Haifa, Israel, September 30 ? October 2, 2014. Proceedings, Springer Berlin Heidelberg, pp. 244-254
- Czumaj, Artur, Vöcking, Berthold, 2014. Thorp shuffling, butterflies, and non-Markovian couplings. In Esparza, Javier; Fraigniaud, Pierre; Husfeldt, Thore; Koutsoupias, Elias (eds.), Automata, Languages, and Programming, Springer Berlin Heidelberg, pp. 344-355
- Fearnley, J., Jurdzinski, Marcin, 2013. Reachability in two-clock timed automata is PSPACE-complete. In Freivalds, Rusin?; Kwiatkowska, Martha; Fomin, Fedor V.; Peleg , David (eds.), Automata, Languages, and Programming : 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part II, Berlin ; London, Springer Berlin Heidelberg, pp. 212-223
- Ganian, R., Hlinený, P., Král', Daniel, Obdr?álek, J., Schwartz, J., Teska, J., 2013. FO model checking of interval graphs. In Freivalds, Rusin?; Kwiatkowska, Martha; Fomin, Fedor V.; Peleg , David (eds.), Automata, Languages, and Programming : 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part II, Berlin ; London, Springer Berlin Heidelberg, pp. 250-262
- Berenbrink, Petra, Czumaj, Artur, Englert, Matthias, Friedetzky, Thomas, Nagel, Lars, 2012. Multiple-choice balanced allocation in (almost) parallel. In Gupta , Anupam; Jansen , Klaus; Rolim , José; Servedio , Rocco (eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques : 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings, Berlin Heidelberg, Springer-Verlag, pp. 411-422
- Korpelainen, Nicholas, Lozin, Vadim V., Tiskin, Alexander, 2010. Hamiltonian cycles in subcubic graphs : what makes the problem difficult. In Kratochvil, J; Li, A; Fiala, J; Kolman, P (eds.), Theory and Applications of Models of Computation, Springer, pp. 320-327
- Krusche, Peter, Tiskin, Alexander, 2010. Computing alignment plots efficiently. In Chapman, Barbara; Desprez, Frédéric; Joubert, Gerhard R.; Lichnewsky, Alain; Peters, Frans; Priol, Thierry (eds.), Parallel Computing: From Multicores and GPU's to Petascale, IOS Press, pp. 158-165
- Tiskin, Alexander, Krusche, Peter, 2010. Parallel longest increasing subsequences in scalable time and memory. In Wyrzykowski, Roman; Dongarra, Jack; Karczewski, Konrad; Wasniewski, Jerzy (eds.), Parallel processing and applied mathematics, Germany, Springer Verlag, pp. 176-185
- Tiskin, Alexander, 2010. Parallel selection by regular sampling. In Guarracino, M. R.; Vivien, F.; Traff, J. L.; Cannataro, M.; Danelutto, M.; Hast, A.; Perla, F.; Knüpfer, A.; Di Martino, B.; Alexander, M. (eds.), Euro-Par 2010 - Parallel Processing, Germany, Springer Verlag, pp. 393-399
- Englert, Matthias, Gupta, A., Krauthgamer, Robert, Räcke, Harald, Talgam-Cohen, Inbal, Talwar, Kunal, 2010. Vertex sparsifiers : new results from old techniques. In Serna, Maria; Shaltiel, Ronen; Jansen, Klaus; Rolim, José (eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Springer Verlag, pp. 152-165
- Lazic, Ranko, Jurdzinski, Marcin, Rutkowski, Michal, Ph.D., 2009. Average-price-per-reward games on hybrid automata with strong resets. In Jones, Neil D.; Müller-Olm, Markus (eds.), Verification, Model Checking, and Abstract Interpretation, London, Springer, pp. 167-181
- Tiskin, Alexander, 2009. Periodic string comparison. In Combinatorial Pattern Matching, Springer Verlag, pp. 193-206
- Krusche, Peter, Tiskin, Alexander, 2009. String comparison by transposition networks. In London Algorithmics 2008: Theory and Practice, London, College Publications, pp. 184-204
- Englert, Matthias, Voecking, Berthold, Winkler, Melanie, 2009. Economical caching with stochastic prices. In Watanabe, O; Zeugmann, T (eds.), Stochastic Algorithms : Foundations and Applications, Springer, pp. 179-190
- Czumaj, Artur, Czyzowicz, J., Gasieniec, L., Jansson, J., Lingas, Andrzej, Zylinski, P., 2009. Approximation algorithms for buy-at-bulk geometric network design. In Dehne, F.; Gavrilova, M.; Sack, J. R.; Toth, C. D. (eds.), Algorithms and data structures, Springer, pp. 168-180
- Englert, Matthias, Franke, T., Olbrich, L., 2008. Sensitivity of wardrop equilibria. In Monien, Burkhard; Schroeder, Ulf-Peter (eds.), Algorithmic game theory, Springer Verlag, pp. 158-169
- Czumaj, Artur, Lingas, Andrzej, 2008. Minimum k-connected geometric networks. In Kao, Ming-Yang (ed.), Encyclopedia of algorithms, Springer Verlag, pp. 536-539
- Czumaj, Artur, 2008. Euclidean traveling salesperson problem. In Kao, Ming-Yang (ed.), Encyclopedia of algorithms, Springer Verlag, pp. 281-284
- Czumaj, Artur, Vöcking, Berthold, 2008. Price of anarchy for machines models. In Kao, Ming-Yang (ed.), Encyclopedia of algorithms, Springer Verlag, pp. 1-99
- Jurdzinski, Marcin, Laroussinie, Francois, Sproston, Jeremy, 2007. Modd checking probabilistic timed automata with one or two clocks. In Grumberg, O.; Huth, M. (eds.), Tools and Algorithms for the Construction and Analysis of Systems : 13th International Conference, TACAS 2007, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2007 Braga, Portugal, March 24 - April 1, 2007. Proceed, Springer Verlag, pp. 170-184
- Deineko, Vladimir G., Tiskin, Alexander, 2007. Fast minimum-weight double-tree shortcutting for metric TSP. In Demetrescu, C. (ed.), Experimental Algorithms, Springer Berlin Heidelberg, pp. 136-149
- Krusche, Peter, Tiskin, Alexander, 2007. Efficient parallel string comparison. Bischof, C.; Bücker, M.; Gibbon, P.; Joubert, G. R.; Lippert, T.; Mohr, B.; Peters, F. (eds.), Parallel Computing: Architectures, Algorithms and Applications, Julich, John von Neumann-Institut für Computing
- Lazic, Ranko, Newcomb, Tom, Ouaknine, Joel, Roscoe, A. W., Worrell, James, 2007. Nets with tokens which carry data. In Kleijnen, J.; Yakovlev, A. (eds.), Petri Nets and Other Models of Concurrency ? ICATPN 2007 : 28th International Conference on Applications and Theory of Petri Nets and Other Models of Concurrency, ICATPN 2007, Siedlce, Poland, June 25-29, 2007. Proceedings, Heidelberg, Springer Verlag, pp. 301-320
- Czumaj, Artur, Wang, Xin, 2007. Fast message dissemination in random geometric ad-hoc radio networks. In Tokuyama, T. (ed.), Algorithms and Computation, Springer Berlin Heidelberg, pp. 220-231
- Czumaj, Artur, Sohler, Christian, 2007. Small space representations for metric min-sum k-clustering and their applications. In Thomas, W.; Weil, P. (eds.), STACS 2007 : 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007. Proceedings, Springer Berlin Heidelberg, pp. 536-548
- Czumaj, Artur, Wang, Xin, 2007. Communication problems in random line-of-sight ad-hoc radio networks. In Hromkovic, J.; Kralovic, R.; Nunkesser, M.; Widmayer, P. (eds.), Stochastic Algorithms : Foundations and Applications, Springer Berlin Heidelberg, pp. 70-81
- Tiskin, Alexander, 2006. Bulk-synchronous parallelism : an emerging paradigm of high-performance computing. In Yang, Laurence T.; Guo, Minyi (eds.), High-Performance Computing: Paradigm and Infrastructure, John Wiley & Sons, Inc, pp. 69-80
- Krusche, Peter, Tiskin, Alexander, 2006. Efficient longest common subsequence computation using bulk-synchronous parallelism. In Gavrilova, M.; Gervasi, O.; Kumar, V.; Tan, C. J. K.; Taniar, D.; Lagana, A.; Mun, Y.; Choo, H. (eds.), Computational Science and Its Applications - ICCSA 2006, Springer Berlin Heidelberg, pp. 165-174
- Tiskin, Alexander, 2006. Efficient representation and parallel computation of string-substring longest common subsequences. In Joubert, G. R.; Nagel, W. E.; Peters, F. J.; Plata, O.; Tirado, P.; Zapata, E. (eds.), Parallel Computing: Current & Future Issues of High-End Computing,, John von Neumann Institute for Computing, pp. 827-834
- Tiskin, Alexander, 2006. Longest common subsequences in permutations and maximum cliques in circle graphs. In Lewenstein, M.; Valiente, G. (eds.), Longest Common Subsequences in Permutations and Maximum Cliques in Circle Graphs, Springer Berlin Heidelberg, pp. 270-281
- Tiskin, Alexander, 2006. All semi-local longest common subsequences in subquadratic time. In Grigoriev, D.; Harrison, J.; Hirsch, E. A. (eds.), Computer Science ? Theory and Applications, Springer Berlin Heidelberg, pp. 352-363
- Deineko, Vladimir, Tiskin, Alexander, 2006. One-sided monge TSP is NP-Hard. In Gavrilova, M.; Gervasi, O.; Kumar, V.; Tan, C. J. K.; Taniar, D.; Lagana, A.; Mun, Y.; Choo, H. (eds.), Computational Science and Its Applications - ICCSA 2006, Springer, pp. 793-801
- Englert, Matthias, Roglin, H., Westermann, M., 2006. Evaluation of online strategies for reordering buffers. In Carme, Àlvarez; María, Serna (eds.), Experimental Algorithms, Springer Verlag, pp. 183-194
- Englert, Matthias, Westermann, Matthias, 2006. Lower and upper bounds on FIFO buffer management in QoS switches. In Azar, Yossi; Erlebach, Thomas (eds.), Algorithms ? ESA 2006, Springer Verlag, pp. 352-363
- Englert, Matthias, Westermann, Matthias, 2005. Reordering buffer management for non-uniform cost models. In Caires, Luís; Italiano, Giuseppe F.; Monteiro, Luís; Palamidessi, Catuscia; Yung, Moti (eds.), Automata, Languages and Programming, Springer Berlin Heidelberg, pp. 627-638
- Lazic, Ranko, Newcomb, Tom, Roscoe, A. W., 2005. On model checking data-independent systems with arrays with whole-array operations. In Abadallah, A. E.; Jones, C. B.; Sanders, J. W. (eds.), Communicating Sequential Processes. The First 25 Years, Springer Berlin Heidelberg, pp. 275-291
- Dimovski, Aleksandar, Lazic, Ranko, 2004. CSP representation of game semantics for second-order idealized Algol. In Davies, J.; Schulte, W.; Barnett, M. (eds.), Formal Methods and Software Engineering, Springer Berlin Heidelberg, pp. 146-161
- Tiskin, Alexander, 2003. Communication-efficient parallel Gaussian elimination. In Malyshkin, V. (ed.), Parallel Computing Technologies, Springer Berlin Heidelberg, pp. 369-383
- Tiskin, Alexander, 2002. Parallel convex hull computation by generalised regular sampling. In Monien, B.; Feldmann, R. (eds.), Euro-Par 2002 Parallel Processing, Springer Berlin Heidelberg, pp. 392-399
- Adler, Micah, Fich, Faith, Goldberg, Leslie Ann, Paterson, Michael S., 2002. Tight size bounds for packet headers in narrow meshes. In Montanari, U.; Rolim, J. D. P.; Welzl, E. (eds.), Automata, Languages and Programming, Springer Berlin Heidelberg, pp. 756-767
- Goldberg, Leslie Ann, Jerrum, Mark, Kannan, Sampath, Paterson, Michael S., 2000. A bound on the capacity of backoff and acknowledgement-based protocols. In Montanari, U.; Rolim, J. D. P; Welzl, E (eds.), Automata, Languages and Programming, Springer Berlin Heidelberg, pp. 705-716

- '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
- '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, 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
- '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
- '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. European Symposium on Algorithms 2022, Germany, 5-9 Sep 2022, Published in Leibniz International Proceedings in Informatics (LIPIcs) series
- '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
- '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. '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
- '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. '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)
- '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
- '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
- '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)
- '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
- 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)
- '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
- 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, 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, '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
- '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
- 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., 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
- 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
- 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
- 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
- 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
- '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 Proceedings of the 40th Annual ACM Symposium on Principles of Distributed Computing (PODC 2021)
- '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
- 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
- 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
- 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
- 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
- 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
- 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)
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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)
- 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
- 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
- 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
- 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
- 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)
- 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
- 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, 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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)
- 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
- 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. 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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

- Chistikov, Dmitry, Paterson, Mike, 2018. Globe-hopping [pre-print]. University of Warwick
- Gajarsky, Jakub, Král', Daniel, 2018. Recovering sparse graphs. Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 29:1-29:15
- Aziz, Haris, Paterson, Michael S., 2008. Variation in weighted voting games. University of Warwick. Department of Computer Science
- Aziz, Haris, Paterson, Michael S., Leech, Dennis, 2007. Combinatorial and computational aspects of multiple weighted voting games. University of Warwick, Department of Economics
- Aziz, H., Paterson, Michael S., Leech, Dennis, 2007. Efficient algorithm for designing weighted voting games. University of Warwick. Department of Computer Science
- Dimovski, Aleksandar, Lazic, Ranko, 2004. Software model checking based on game semantics and CSP. University of Warwick. Department of Computer Science
- Lazic, Ranko, Newcomb, Tom, Roscoe, A. W., 2004. On model checking data-independent systems with arrays with whole-array operations. University of Warwick. Department of Computer Science
- Dimovski, Aleksandar, Lazic, Ranko, 2004. CSP representation of game semantics for second-order idealized Algol. University of Warwick. Department of Computer Science
- Lazic, Ranko, Newcomb, Tom, Roscoe, A. W., 2004. Polymorphic systems with arrays : decidability and undecidability. University of Warwick. Department of Computer Science
- Lazic, Ranko, Nowak, David, 2003. On a semantic definition of data independence. University of Warwick. Department of Computer Science
- Goldberg, Leslie Ann, Jerrum, Mark, Paterson, Michael S., 2001. The computational complexity of two-state spin systems. University of Warwick. Department of Computer Science
- Goldberg, Leslie Ann, Jerrum, Mark, Kannan, Sampath, Paterson, Michael S., 2000. A bound on the capacity of backoff and acknowledgement-based protocols. University of Warwick. Department of Computer Science
- Adler, Micah, Fitch, Faith, Goldberg, Leslie Ann, Paterson, Michael S., 2000. Tight size bounds for packet headers in narrow meshes. University of Warwick. Department of Computer Science
- Ravindran, Somasundaram, Gibbons, Alan (Alan M.), Paterson, Michael S., 2000. Dense edge-disjoint embedding of complete binary trees in interconnection networks. Theoretical Computer Science, Elsevier Science BV, pp. 325-342
- Cormode, Graham, Paterson, Michael S., Sahinalp, Suleyman Cenk, Vishkin, Uzi, 1999. Communication complexity of document exchange. University of Warwick. Department of Computer Science
- Goldberg, Leslie Ann, MacKenzie, Phil, Paterson, Michael S., Srinavasan, Aravind, 1998. Contention resolution with constant expected delay. University of Warwick. Department of Computer Science
- Khanna, Sanjeev, Muthukrishnan, S., Paterson, Michael S., 1998. On approximating rectangle tiling and packing. University of Warwick. Department of Computer Science
- Agarwala, Richa, Bafna, Vineet, Farach, Martin, Paterson, Michael S., Thorup, Mikkel, 1997. On the approximability of numerical taxonomy (fitting distances by tree metrics). University of Warwick. Department of Computer Science
- Goldberg, Leslie Ann, Paterson, Michael S., Srinavasan, Aravind, Sweedyk, Elizabeth, 1996. Better approximation guarantees for job-shop scheduling. University of Warwick. Department of Computer Science
- Ravindran, Somasundaram, Gibbons, Alan (Alan M.), Paterson, Michael S., 1995. Dense edge-disjoint embedding of complete binary trees in interconnection networks. University of Warwick. Department of Computer Science
- Paterson, Michael S., Przytycka, Teresa, 1995. On the complexity of string folding. University of Warwick. Department of Computer Science
- Miltersen, Peter Bro, Paterson, Michael S., Tarui, Jun, 1995. The asymptotic complexity of merging networks. University of Warwick. Department of Computer Science
- Paterson, Michael S., Srinavasan, Aravind, 1995. Contention resolution with bounded delay. University of Warwick. Department of Computer Science
- Paterson, M. S., Dancik, V., 1994. Longest common subsequences. University of Warwick. Department of Computer Science
- Koizumi, Hirotaka, Maruoka, Akira, Paterson, Michael S., 1993. Consistency of natural relations on sets. University of Warwick. Department of Computer Science
- Paterson, Michael S., 1993. Computer science seminars 1992/93. University of Warwick. Department of Computer Science
- Czumaj, Artur, 1992. Parallel algorithm for the matrix chain product problem. University of Warwick. Department of Computer Science
- Czumaj, Artur, 1992. An optimal parallel algorithm for computing a near-optimal order of matrix multiplications. University of Warwick. Department of Computer Science
- Fischer, Michael J., Paterson, Michael S., 1992. Fishspear : a priority queue algorithm. University of Warwick. Department of Computer Science
- Gibbons, Alan (Alan M.), Paterson, Michael S., 1992. Dense edge-disjoint embedding of binary trees in the mesh. University of Warwick. Department of Computer Science
- Paterson, Michael S., Zwick, Uri, 1992. Shallow multiplication circuits and wise financial investments. University of Warwick. Department of Computer Science
- Zwick, Uri, Paterson, Michael S., 1991. The memory game. University of Warwick. Department of Computer Science
- Paterson, Michael S., Zwick, Uri, 1991. Shrinkage of de Morgan formulae under restriction. University of Warwick. Department of Computer Science
- Paterson, Michael S., Zwick, Uri, 1990. Shallow multiplication circuits. University of Warwick. Department of Computer Science
- Paterson, Michael S., Yao, F. Frances, 1990. Optimal binary space partitions for orthogonal objects. University of Warwick. Department of Computer Science
- Paterson, Michael S., Zwick, Uri, 1990. Improved circuits and formulae for multiple addition, multiplication and symmetric Boolean functions. University of Warwick. Department of Computer Science
- Paterson, Michael S., Pippenger, Nicholas, Zwick, Uri, 1990. Optimal carry save networks. University of Warwick. Department of Computer Science
- Paterson, Michael S., Yao, F. Frances, 1989. Binary partitions with applications to hidden-surface removal and solid modelling. University of Warwick. Department of Computer Science
- McColl, William Finlay, Paterson, Michael S., 1988. Planar acyclic computation. University of Warwick. Department of Computer Science
- Yao, F. Frances, Dobkin, David P., Edelsbrunner, Herbert, Paterson, Michael S., 1988. Partitioning space for range queries. University of Warwick. Department of Computer Science
- Paterson, Michael S., Razborov, Alexander, 1988. The set of minimal braids is co-NP-complete. University of Warwick. Department of Computer Science
- Paterson, Michael S., 1987. Improved sorting networks with O(log n) depth. University of Warwick. Department of Computer Science
- Paterson, Michael S., 1986. Universal chains and wiring layouts. University of Warwick. Department of Computer Science
- Daykin, D. E., Daykin, J. W., Paterson, Michael S., 1983. On log concavity for order-preserving and order-non-reversing maps of partial orders. University of Warwick. Department of Computer Science
- Munro, J. Ian, Paterson, Michael S., 1978. Selection and sorting with limited storage. University of Warwick. Department of Computer Science
- Paterson, Michael S., 1976. New bounds for formula size. University of Warwick. Department of Computer Science
- McColl, William Finlay, Paterson, Michael S., 1975. The depth of all Boolean functions. University of Warwick. Department of Computer Science
- Valiant, Leslie, Paterson, Michael S., 1975. Circuit size is nonlinear in depth. University of Warwick. Department of Computer Science
- Schönhage, Arnold, Paterson, Michael S., Pippenger, Nicholas, 1975. Finding the median. University of Warwick. Department of Computer Science
- Paterson, Michael S., 1974. Complexity of monotone networks for Boolean matrix product. University of Warwick. Department of Computer Science

Title | Funder | Award start | Award end |
---|---|---|---|

ERC Starting Grant (original record 72385) | UK Research and Innovation | 01 Oct 2023 | 30 Sep 2028 |

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 |

Research Fellowship | Royal Commission for the Exhibition of 1851 | 01 Oct 2022 | 30 Sep 2025 |

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 |

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 |

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

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