- Czumaj, Artur, Davies, Peter, 2021. Exploiting spontaneous transmissions for broadcasting and leader election in radio networks. Journal of the ACM, 68 (2)
- Gur, Tom, Lachish, Oded, 2021. On the power of relaxed local decoding algorithms. SIAM Journal on 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
- 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
- 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)
- 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)
- 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
- Gur, Tom, Shinkar, Igor, 2020. An entropy lower bound for non-malleable extractors. IEEE Transactions on Information Theory
- Gutin, Gregory, Ramanujan, M. S., Reidl, Felix, Wahlström, Magnus, 2020. Alternative parameterizations of Metric Dimension. Theoretical Computer Science, 806, pp. 133-143
- 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
- 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
- Hoang, Hung P., Mutze, Torsten, 2020. Combinatorial generation via permutation languages. II. Lattice congruences. Israel Journal of Mathematics
- Mutze, Torsten, Nummenpalo, Jerri, 2020. A constant-time algorithm for middle levels Gray codes. Algorithmica, 82, pp. 1239-1258
- Milich, Marcel, Mutze, Torsten, Pergel, Martin, 2020. On flips in planar matchings. Discrete Applied Mathematics
- Mutze, Torsten, Nummenpalo, Jerri, Walczak, Bartosz, 2020. Sparse Kneser graphs are Hamiltonian. Journal of the London Mathematical Society
- Elizabeth, Hartung, Hoang, Hung P., Mutze, Torsten, Williams, Aaron, 2020. Combinatorial generation via permutation languages. I. Fundamentals. Transactions of the American Mathematical Society
- Oliveira, Igor C., Bydzovsky, Jan, Krajicek, Jan, 2020. Consistency of circuit lower bounds with bounded theories. Logical Methods in Computer Science
- Král', Daniel, Lovasz, Laszlo M., Noel, Jonathan A., Sosnovec, Jakub, 2020. Finitely forcible graphons with an almost arbitrary structure. Discrete Analysis
- 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
- Dvorák, Zdenek, Král', Daniel, Thomas, Robin, 2020. Three-coloring triangle-free graphs on surfaces IV. Bounding face sizes of 4-critical graphs. Journal of Combinatorial Theory, Series B
- Král', Daniel, Noel, J., Norine, S., Volec, J., Wei, F., 2020. Non-bipartite k-common graphs. Combinatorica
- 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
- 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
- Grzesik, Andrzej, Král', Daniel, Lovász, Miklós, 2020. Elusive extremal graphs. Proceedings of the London Mathematical Society, 121 (6), pp. 1685-1736
- 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
- Dvorák, Zdenek, Král', Daniel, Thomas, Robin, 2020. Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies. Journal of Combinatorial Theory Series B
- Lazic, Ranko, Schmitz, Sylvain, 2020. The ideal view on Rackoff's coverability technique. Information and Computation
- 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)
- 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
- Chiesa, Alessandro, Forbes, Michael, Gur, Tom, Spooner, Nicholas, 2019. Spatial isolation implies zero knowledge even in a quantum world. Journal of the ACM
- 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
- Chistikov, Dmitry, Martyugin, Pavel, Shirmohammadi, Mahsa, 2019. Synchronizing automata over nested words. Journal of Automata, Languages and Combinatorics, 24 (2-4), pp. 219-251
- 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
- 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, 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, 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, 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
- 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
- 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, Deligkas, Argyrios, Fasoulakis, Michail, Fearnley, John, Jurdzinski, Marcin, Savani, Rahul, 2018. Distributed methods for computing approximate equilibria. Algorithmica
- 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
- Czumaj, Artur, Davies, Peter, 2018. Deterministic communication in radio networks. SIAM Journal on Computing, 47 (1), pp. 218-240
- 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
- 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
- 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)
- Chistikov, Dmitry, Haase, Christoph, Halfon, Simon, 2018. Context-free commutative grammars with integer counters and resets. Theoretical Computer Science, 735, pp. 147-161
- 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
- Al-Bawani, Kamal, Englert, Matthias, Westermann, Matthias, 2018. Comparison-based buffer management in QoS switches. Algorithmica, 80 (3), pp. 1073-1092
- Al-Bawani, Kamal, Englert, Matthias, Westermann, Matthias, 2018. Online packet scheduling for CIOQ and buffered crossbar switches. Algorithmica, 80, pp. 3861-3888
- 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., Král', Daniel, Martins, Taísa L., 2018. Finitely forcible graph limits are universal. Advances in Mathematics, 340, pp. 819-854
- Cooper, Jacob W., Kaiser, Tomas, Král', Daniel, Noel, Jonathan, 2018. Weak regularity and finitely forcible graph limits. Transactions of the American Mathematical Society
- 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
- Kloster, Kyle, Král', Daniel, Sullivan, Blair D., 2018. Walk entropy and walk-regularity. Linear Algebra and Its Applications, 546, pp. 115-121
- Mutze, Torsten, Su, Pascal, 2017. Bipartite Kneser graphs are Hamiltonian. Combinatorica, 37 (6), pp. 1207-1219
- 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
- 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
- Krajicek, Jan, Oliveira, Igor Carboni, 2017. Unprovability of circuit upper bounds in Cook's theory PV. Logical Methods in Computer Science, 13 (1)
- 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
- Kardos, Frantisek, Král', Daniel, Liebenau, Anita, Mach, Luká?, 2017. First order convergence of matroids. European Journal of Combinatorics, 59, pp. 150-168
- 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)
- 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
- Hebdige, Michael, Král', Daniel, 2016. Third case of the cyclic coloring conjecture. SIAM Journal on Discrete Mathematics
- 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)
- 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
- 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, Özmen, Deniz, Westermann, Matthias, 2014. The power of reordering for online minimum makespan scheduling. SIAM Journal on Computing, 43 (3), pp. 1220-1237
- 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
- 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
- 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
- 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
- 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
- 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
- Král', Daniel, Pikhurko, Oleg, 2013. Quasirandom permutations are characterized by 4-point densities. Geometric and Functional Analysis, 23 (2), pp. 570-579
- 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, 2012. An overview of some results for reordering buffers. Computer Science - Research and Developmen, Vol.27 (No.3), pp. 217-223
- 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
- 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
- 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
- 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
- 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
- Jurdzinski, Marcin, Lazic, Ranko, 2011. Alternating automata on data trees and XPath satisfiability. ACM Transactions on Computational Logic (TOCL), 12 (3), pp. 1-21
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- Paterson, Michael S., Peres, Y., Thorup, Mikkel, Winkler, P., Zwick, Uri, 2009. Maximum overhang. American Mathematical Monthly, Vol.116 (No.9), pp. 765-787
- Paterson, Michael S., Zwick, Uri, 2009. Overhang. American Mathematical Monthly, Vol.116 (No.1), pp. 19-44
- 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
- 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
- Tiskin, Alexander, 2009. Faster Subsequence Recognition in Compressed Strings. Journal of Mathematical Sciences, 158 (5), pp. 759-769
- Deineko, Vladimir G., Tiskin, Alexander, 2009. Fast minimum-weight double-tree shortcutting for metric TSP. Journal of Experimental Algorithmics, Vol.14
- 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
- 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)
- 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
- Czumaj, Artur, Sohler, Christian, 2008. Testing Euclidean minimum spanning trees in the plane. ACM Transactions on Algorithms, 4 (3)
- Tiskin, Alexander, 2008. Semi-local longest common subsequences in subquadratic time. Journal of Discrete Algorithms, 6 (4), pp. 570-581
- Tiskin, Alexander, 2008. Semi-local string comparison : algorithmic techniques and applications. Mathematics in Computer Science, 1 (4), pp. 571-603
- 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)
- 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
- Dyer, Martin, Goldberg, Leslie Ann, Paterson, Michael S., 2007. On counting homomorphisms to directed acyclic graphs. Journal of the ACM, Vol.54 (No.6)
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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, 2008. Euclidean traveling salesperson problem. In Kao, Ming-Yang (ed.), Encyclopedia of algorithms, Springer Verlag, pp. 281-284
- 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, Vöcking, Berthold, 2008. Price of anarchy for machines models. In Kao, Ming-Yang (ed.), Encyclopedia of algorithms, Springer Verlag, pp. 1-99
- 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, 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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

- Bhattacharya, Sayan, Grandoni, Fabrizio, Wajc, David, 2021. Online edge coloring algorithms via the nibble method. ACM-SIAM Symposium on Discrete Algorithms (SODA21), Virtual, 10-13 Jan 2021, Published in SODA '21: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2830-2841
- Bhattacharya, Sayan, Henzinger, Monika, Nanongkai, Danupon, Wu, Xiaowei, 2021. Dynamic set cover : improved amortized and worst-case update time. ACM-SIAM Symposium on Discrete Algorithms (SODA21), Virtual, 10-13 Jan 2021, Published in Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2537-2549
- Dall'Agno, Marcel, Gur, Tom, Wajc, David, Lachish, Oded, 2021. A structural theorem for local algorithms with applications to testing, coding, and privacy. ACM-SIAM Symposium on Discrete Algorithms (SODA21), Virtual, 10-13 Jan 2021, Published in SODA '21: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1651-1665
- 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
- 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)
- 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, Sohler, Christian, 2020. Sublinear time approximation of the cost of a metric k-nearest neighbor graph. Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'2020), Salt Lake City, Utah, USA, January 5-8, 2020, Salt Lake City, Utah, USA, 5-8 Jan 2020, Published in Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, pp. 2973-2992
- Czumaj, Artur, Davies, Peter, Parter, Merav, 2020. Simple, deterministic, constant-round coloring in the congested clique. 39th Annual ACM Symposium on Principles of Distributed Computing (PODC 2020), Virtual conference, 3-6 Aug 2020
- Czumaj, Artur, Fichtenberger, Hendrik, Peng, Pan, Sohler, Christian, 2020. Testable properties in general graphs and random order streaming. 24th International Conference on Randomization and Computation (RANDOM 2020), Virtual, USA, 17-19 Aug 2020
- Czumaj, Artur, Davies, Peter, Parter, Merav, 2020. Graph sparsification for derandomizing massively parallel computation with low space. 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020), Virtual, USA, 15-17 Jul 2020, Published in SPAA '20: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, pp. 175-185
- Bhattacharya, Sayan, Kulkarni, Janardhan, 2020. An improved algorithm for incremental cycle detection and topological ordering in sparse graphs. 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Salt Lake City, Utah, U.S., 5-8 Jan 2020, Published in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)
- Bhattacharya, Sayan, Nanongkai, Danupon, Saranurak, Thatchaphol, 2020. Coarse-grained complexity for dynamic algorithms. 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Salt Lake City, Utah, U.S., 5-8 Jan 2020, Published in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)
- 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 ACM-SIAM Symposium on Discrete Algorithms
- 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 Proceedings of ICALP 2020, pp. 60:1-60:17
- Hartung, Elizabeth, Hoang, Hung, Mutze, Torsten, Williams, Aaron, 2020. Combinatorial generation via permutation languages. 31st Annual ACM-SIAM Symposium on Discrete Algorithms, Salt Lake City, United States, 5-8 Jan 2020, Published in SODA '20: Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1214-1225
- 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, Haase, Christoph, 2020. On the power of ordering in linear arithmetic theories. 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), 8-11 Jul 2020, Published in 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), pp. 1-15
- Chistikov, Dmitry, 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
- 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
- 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
- Czerwinski, Wojciech, Lasota, Slawomir, Lazic, Ranko, Leroux, Jerome, Mazowiecki, Filip, 2020. Reachability in fixed dimension vector addition systems with states. 31st International Conference on Concurrency Theory (CONCUR 2020), Online, 01-04 Sep 2020, Published in Leibniz International Proceedings in Informatics (LIPIcs), pp. 12:1-12:20
- 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
- Czumaj, Artur, Sohler, Christian, 2019. A characterization of graph properties testable for general planar graphs with one-sided error (it's all about forbidden subgraphs). The 60th IEEE Symposium on Foundations of Computer Science (FOCS 2019), Baltimore, MD, 9-12 Nov 2019, Published in Proceedings of the 60th IEEE Symposium on Foundations of Computer Science (FOCS 2019)
- 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
- Lokshtanov, Daniel, Sridharan, Ramanujan, Saurabh, Saket, Zehavi, Meirav, 2019. Parameterized complexity and approximability of directed odd cycle transversal. ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), Salt Lake City, Utah, 5-8 Jan 2020
- 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
- Chen, Lijie, Hirahara, Shuichi, Carboni Oliveira, Igor, Pich, Jan, Rajgopal, Ninad, Santhanam, Rahul, 2019. Beyond natural proofs : hardness magnification and locality. Innovations in Theoretical Computer Science, Seattle, USA, 12-14 Jan 2020
- Oliveira, Igor C., Pich, Jan, Santhanam, Rahul, 2019. Hardness magnification near state-of-the-art lower bounds. 34th Computational Complexity Conference (CCC 2019), New Brunswick, NJ, USA, 18-20 Jul 2019, Published in Proceedings of the 33rd Computational Complexity Conference, pp. 27:1-27:29
- Oliveira, Igor C., 2019. Randomness and intractability in Kolmogorov complexity. 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), Patras, Greece, 9-12 Jul 2019, Published in Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 32:1-32:14
- Oliveira, Igor C., Santhanam, Rahul, Srinivasan, Srikanth, 2019. Parity helps to compute majority. 34th Computational Complexity Conference (CCC 2019), New Brunswick, NJ, USA, 18-20 Jul 2019, Published in Proceedings of the 34th Computational Complexity Conference (CCC), pp. 23:1-23:17
- 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
- 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
- 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
- Englert, Matthias, Räcke, Harald, Stotz, Richard, 2019. Polylogarithmic guarantees for generalized reordering buffer management. FOCS 2019 60th Annual IEEE Symposium on Foundations of Computer Science, Baltimore, Maryland, 9-12 Nov 2019
- Hubai, Tamàs, Král', Daniel, Parczyk, Olaf, Person, Yury, 2019. Person : more non-bipartite forcing pairs. EuroComb 2019, Bratislava, Slovakia, 26-30 Aug 2019, Published in Acta Mathematica Universitatis Comenianae
- Lazic, Ranko, 2019. Finkel was right : counter-examples to several conjectures on variants of vector addition systems (invited talk). 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019), Bombay, India, 11-13 Dec 2019, Published in 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019), pp. 3:1-3:2
- Dixon, Alex, Lazic, Ranko, 2019. KReach : a tool for reachability in petri nets. TACAS 2020 : 26th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, Dublin, Ireland, 25-30 Apr 2020, Published in Proceedings of TACAS 2020 (Tools and Algorithms for the Construction and Analysis of Systems)
- Czerwinski, Wojciech, 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
- Czumaj, Artur, Davies, Peter, 2018. Faster deterministic communication in radio networks. 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016), Rome, Italy, 12-15 Jul 2016, Published in Leibniz International Proceedings in Informatics (LIPIcs), pp. 1-14
- Czumaj, Artur, Lacki, Jakub, Madry, Aleksander, Mitrovic, Slobodan, Onak, Krzysztof, Sankowski, Piotr, 2018. Round compression for parallel matching algorithms. The 50th Annual ACM Symposium on Theory of Computing (STOC 2018), Los Angeles, 25-29 Jun 2018, Published in STOC 2018 Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 471-484
- 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, 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
- 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
- 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, Liu, Yang P., Rothblum, Ron, 2018. An exponential separation between MA and AM proofs of proximity. The 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague, Czech Republic, 9-13 Jul 2018, Published in 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), pp. 73:1-73:15
- Gur, Tom, Ramnarayan, Govind, Rothblum, Ron D., 2018. Relaxed locally correctable codes. 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), Published in 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), pp. 27:1-27:11
- Chiesa, Alessandro, Gur, Tom, 2018. Proofs of proximity for distribution testing. 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), Published in 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), pp. 53:1-53:14
- Chiesa, Alessandro, Forbes, Michael, Gur, Tom, Spooner, Nicholas, 2018. Spatial isolation implies zero knowledge even in a quantum world. 59th Annual IEEE Symposium on Foundations of Computer Science, Paris, France, 7-9 Oct 2018, Published in 59th Annual IEEE Symposium on Foundations of Computer Science, pp. 755-765
- Lokshtanov, Daniel, Ramanujan, Maadapuzhi Sridharan, Saket, Saurabh, 2018. When recursion is better than iteration : a linear-time algorithm for acyclicity with few error vertices. 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, Louisiana, USA, New Orleans, Louisiana, USA, 7-10 Jan 2018, Published in Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1-18
- Lokshtanov, Daniel, Ramanujan, Maadapuzhi Sridharan, Saurabh, Saket, Zehavi, Meirav, 2018. Reducing CMSO model checking to highly connected graphs. 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague, 13 Jul 2018, Published in 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), pp. 135:1-135:14
- Bang-Jensen, Jørgen, Basavaraju, Manu, Vitting Klinkby, Kristine, Misra, Pranabendu, Ramanujan, Maadapuzhi Sridharan, Saurabh, Saket, Zehvi, Meirav, 2018. Parameterized algorithms for survivable network design with uniform demands. 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, Louisiana, USA, 7-10 Jan 2018, Published in Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1-13
- 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
- Chistikov, Dmitry, Murawski, Andrzej S., Purser, David, 2018. Bisimilarity distances for approximate differential privacy. International Symposium on Automated Technology for Verification and Analysis 2018, Los Angeles, USA, Oct 7-10 2018, Published in Lecture Notes in Computer Science, pp. 194-210
- Almagor, Shaull, Chistikov, Dmitry, Ouaknine, Joel, Worrell, James, 2018. O-minimal invariants for linear loops. ICALP 2018: 45th International Colloquium on Automata, Languages, and Programming, Prague, Czech Republic, 9-13 Jul 2018, Published in 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), pp. 114:1-114:14
- Hirahara, Shuichi, Oliveira, Igor C., Santhanam, Rahul, 2018. NP-hardness of minimum circuit size problem for OR-AND-MOD circuits. Computational Complexity Conference, San Diego, California, 22-24 Jun 2018, Published in Proceedings of the 33rd Computational Complexity Conference, pp. 5:1-5:31
- Oliveira, Igor C., Santhanam, Rahul, 2018. Pseudo-derandomizing learning and approximation. 22nd International Conference on Randomization and Computation (RANDOM), Princeton, NJ, USA, 20-22 Aug 2018, Published in Proceedings of the 22nd International Conference on Randomization and Computation (RANDOM), pp. 55:1-55:19
- Oliveira, Igor C., Santhanam, Rahul, Tell, Roei, 2018. Expander-based cryptography meets natural proofs. 10th Innovations in Theoretical Computer Science Conference (ITCS), San Diego, California, USA., 10-12 Jan 2019, Published in Proceedings of the 33rd Computational Complexity Conference, pp. 18:1-18:14
- Chen, Ruiwen, Oliveira, Igor Carboni, Santhanam, Rahul, 2018. An average-case lower bound against ACC0. LATIN 2018: Theoretical Informatics 13th Latin American Symposium, Buenos Aires, Argentina, 16-19 Apr 2018, Published in LATIN 2018: Theoretical Informatics, pp. 317-330
- Oliveira, Igor Carboni, Santhanam, Rahul, 2018. Hardness magnification for natural problems. 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), Paris, France, 7-9 Oct 2018, pp. 65-76
- 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
- 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
- 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, 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, 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
- 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
- Canonne, Clément L., Gur, Tom, 2017. An adaptivity hierarchy theorem for property testing. 32nd Computational Complexity Conference (CCC 2017), Published in 32nd Computational Complexity Conference (CCC 2017, pp. 27:1-27:25
- Gur, Tom, Rothblum, Ron D., 2017. A hierarchy theorem for interactive proofs of proximity. 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), Published in 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), pp. 39:1-39:43
- Blais, Eric, Canonne, Clément L., Gur, Tom, 2017. Distribution testing lower bounds via reductions from communication complexity. 32nd Computational Complexity Conference (CCC 2017), Published in 32nd Computational Complexity Conference (CCC 2017), pp. 28:1-28:40
- 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
- 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
- Chistikov, Dmitry, Kiefer, Stefan, Maru?iC, Ines, Shirmohammadi, Mahsa, Worrell, James, 2017. On rationality of nonnegative matrix factorization. Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, 16-19 Jan 2017, Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1290-1305
- Chistikov, D., Kiefer, S., Maru?ic, I., Shirmohammadi, M., Worrell, J., 2017. On rationality of nonnegative matrix factorization. Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, 16-19 Jan 2017, Published in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1290-1305
- Chistikov, Dmitry, Iván, S., Lubiw, A., Shallit, J., 2017. Fractional coverings, greedy coverings, and rectifier networks. 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), Hannover, Germany, 8-11 Mar 2017, Published in Leibniz International Proceedings in Informatics, LIPIcs, pp. 23:1-23:14
- Chistikov, Dmitry, Haase, Christoph, 2017. On the complexity of quantified integer programming. The 44th International Colloquium on Automata, Languages, and Programming (ICALP), Warsaw, Poland, 10-14 July 2017, Published in 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), pp. 94:1-94:13
- Chen, Xi, Oliveira, Igor Carboni, Servedio, Rocco A., 2017. Addition is exponentially harder than counting for shallow monotone circuits. 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), Montreal, QC, Canada, 19-23 Jun 2017, Published in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 1232-1245
- Oliveira, Igor Carboni, Santhanam, Rahul, 2017. Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness. 32nd Computational Complexity Conference (CCC), Riga, Latvia, 6-9 Jul 2017, Published in Leibniz International Proceedings in Informatics (LIPIcs), pp. 18:1-18:49
- Oliveira, Igor Carboni, Santhanam, Rahul, 2017. Pseudodeterministic constructions in subexponential time. 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), Montreal, QC, Canada, 19-23 Jun 2017, Published in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 665-677
- 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
- Clemente, Lorenzo, Lasota, Slawomir, Lazic, Ranko, Mazowiecki, Filip, 2017. Timed pushdown automata and branching vector addition systems. 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Reykjavik, Iceland, 20-23 Jun 2017, Published in 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
- Figueira, Diego, Lazic, Ranko, Leroux, Jerome, Mazowiecki, Filip, Sutre, Grégoire, 2017. Polynomial-space completeness of reachability for succinct branching VASS in dimension one. The 44th International Colloquium on Automata, Languages, and Programming (ICALP), Warsaw, Poland, 10-14 Jul 2017, Published in 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), pp. 119 : 1-119: 14
- Czumaj, Artur, Deligkas, Argyrios, Fasoulakis, Michail, Fearnley, John, Jurdzinski, Marcin, Savani, Rahul, 2016. Distributed methods for computing approximate equilibria. International Conference on Web and Internet Economics, WINE 2016, Montréal, Canada, 11-14 Dec 2016, Published in Web and Internet Economics. WINE 2016, pp. 15-28
- Czumaj, Artur, Peng, Pan, Sohler, Christian, 2016. Relating two property testing models for bounded degree directed graphs. 48th Annual ACM Symposium on Theory of Computing (STOC 2016), Cambridge, MA, 19-21 Jun 2016, Published in STOC 2016 Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1033-1045
- 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
- Chistikov, D., Kiefer, S., Marusic, I., Shirmohammadi, M., Worrell, J., 2016. On restricted nonnegative matrix factorization. 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Rome, Italy, 12-15 Jul 2016, Published in Leibniz International Proceedings in Informatics, LIPIcs, pp. 103:1-103:14
- Chistikov, Dmitry, Czerwinski, Wojciech, Hofman, Piotr, Pilipczuk, Michal, Wehar, Michael, 2016. Shortest paths in one-counter systems. 19th International Conference, FOSSACS 2016, Eindhoven, The Netherlands, 2-8 Apr 2016, Published in Foundations of Software Science and Computation Structures. FoSSaCS 2016, pp. 462-478
- Chistikov, Dmitry, Martyugin, Pavel, Shirmohammadi, Mahsa, 2016. Synchronizing automata over nested words. 19th International Conference, FOSSACS 2016, Eindhoven, The Netherlands, 2-8 Arp 2016, Published in Foundations of Software Science and Computation Structures. FoSSaCS 2016, pp. 252-268
- Atig, Mohamed Faouzi, Chistikov, Dmitry, Hofman, Piotr, Kumar, K. Narayan, Saivasan, Prakash, Zetzsche, Georg, 2016. The complexity of regular abstractions of one-counter languages. 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), New York City, USA, 5?8 Jul 2016, Published in LICS '16 Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, pp. 207-216
- Chistikov, Dmitry, Majumdar, Rupak, Niksic, Filip, 2016. Hitting families of schedules for asynchronous programs. 28th International Conference, CAV 2016, Toronto, ON, Canada, 17-23 Jul 2016, Published in Computer Aided Verification. CAV 2016, pp. 157-176
- Chistikov, Dmitry, Haase, Christoph, 2016. The taming of the semi-linear set. 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), pp. 128:1-128:13
- Chen, Xi, Oliveira, Igor C., Servedio, Rocco A., Tan, Li-Yang, 2016. Near-optimal small-depth lower bounds for small distance connectivity. STOC 2016: 48th Annual Symposium on the Theory of Computing, Cambridge, MA, USA, 19-21 Jun 2016, Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp. 612-625
- Al-Bawan, Kamal, Englert, Matthias, Westermann, Matthias, 2016. Online packet scheduling for CIOQ and buffered crossbar switches. 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), California, USA, 11-13 Jul 2016, Published in SPAA '16 Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 241-250
- Al-Bawan, Kamal, Englert, Matthias, Westermann, Matthias, 2016. Comparison-based FIFO buffer management in QoS switches. 12th Latin American Theoretical Informatics Symposium (LATIN), 2016, Ensenada, México, 11-15 Apr 2016, Published in Proceedings of the 12th Latin American Theoretical Informatics Symposium (LATIN), 2016, pp. 27-40
- Englert, Matthias, Lazic, Ranko, Totzke, Patrick, 2016. Reachability in two-dimensional unary vector addition systems with states is NL-complete. Thirty-First Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), New York City, USA, 5?8 Jul 2016, Published in Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
- Lazic, Ranko, 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
- 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, 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
- Czumaj, Artur, 2015. Random permutations using switching networks. Forty-Seventh Annual ACM on Symposium on Theory of Computing, Portland, Oregon, 15-17 Jun 2015, Published in Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pp. 703-712
- Czumaj, Artur, Peng, Pan, Sohler, Christian, 2015. Testing cluster structure of graphs. Forty-Seventh Annual ACM on Symposium on Theory of Computing, Portland, Oregon, 15-17 Jun 2015, Published in Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pp. 723-732
- Bhattacharya, Sayan, Henzinger, Monika, Italiano, Giuseppe F., 2015. Design of dynamic algorithms via primal-dual method. International Colloquium on Automata, Languages, and Programming, Kyoto, Japan, 6-10 Jul 2015, Published in Automata, Languages, and Programming : 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II, pp. 206-218
- Bhattacharya, Sayan, Hoefer, Martin, Huang, Chien-Chung, Kavitha, Telikepalli, Wagner, Lisa, 2015. Maintaining near-popular matchings. International Colloquium on Automata, Languages, and Programming, Kyoto, Japan, 6-10 Jul 2015, Published in Automata, Languages, and Programming, pp. 504-515
- Bhattacharya, Sayan, Dvorák, Wolfgang, Henzinger, Monika, Starnberger, Martin, 2015. Welfare maximization with friends-of-friends network externalities. 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), München, Germany, 4-7 Mar 2015, Published in 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), pp. 90-102
- Bhattacharya, Sayan, Henzinger, Monika, Italiano, Giuseppe F., 2015. Deterministic fully dynamic data structures for vertex cover and matching. Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, 4-6 Jan 2015, Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 785-804
- Bhattacharya, Sayan, Henzinger, Monika, Nanongkai, Danupon, Tsourakakis, Charalampos, 2015. Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. Forty-seventh annual ACM symposium on Theory of computing, Portland, Oregon, USA, 14-17 Jun 2015, Published in Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pp. 173-182
- Goldreich, Oded, Gur, Tom, Komargodski , Ilan, 2015. Strong locally testable codes with relaxed local decoders. 30th Conference on Computational Complexity (CCC?15), Published in 30th Conference on Computational Complexity (CCC 2015), pp. 1-41
- Goldreich, Oded, Gur, Tom, Rothblum, Ron D., 2015. Proofs of proximity for context-free languages and read-once branching programs. The 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), Kyoto, Japan, 6-10 Jul 2015, Published in Automata, Languages, and Programming. ICALP 2015, pp. 666-677
- 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
- 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
- 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
- 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
- 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
- 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
- Czumaj, Artur, 2010. Local graph exploration and fast property testing. 16th Annual European Symposium on Algorithms (ESA 2010), Liverpool, England, 6-8 Sep 2010, Published in Lecture Notes in Computer Science, pp. 410-414
- Czumaj, Artur, Sohler, Christian, 2010. Sublinear-time algorithms. Workshop on Property Testing, Tsinghua University, Peoples Republic of China, Published in Property Testing : Current Research and Surveys, pp. 41-64
- Czumaj, Artur, Sohler, Christian, 2010. Testing expansion in bounded-degree graphs. Meeting on Combinatorics and Probability, Mathemat Res Inst, Oberwolfach, Germany, April 26-May 02, 2009, Published in Combinatorics, Probability and Computing, pp. 693-709
- Adamaszek, Michal, Czumaj, Artur, Sohler, Christian, 2010. Testing monotone continuous distributions on high-dimensional real cubes. Workshop on Property Testing, Tsinghua University, Peoples Republic of China, Published in Property Testing : Current Research and Surveys, pp. 228-233
- Czumaj, Artur, Adamaszek, Michal, Sohler, Christian, 2010. Testing monotone continuous distributions on high-dimensional real cubes. 21st ACM-SIAM Symposium on Discrete Algorithms (SODA'10), Austin, Texas, 17-19 Jan 2010, Published in SIAM, pp. 56-65
- Tiskin, Alexander, 2010. Fast distance multiplication of unit-Monge matrices. 21st Annual ACM/SIAM Symposium on Discrete Algorithms, Austin, TX, 17-19 Jan 2010, Published in Proceedings of the twenty-first annual ACM-SIAM symposium on discrete algorithms, pp. 1287-1296
- Krusche, Peter, Tiskin, Alexander, 2010. New algorithms for efficient parallel string comparison. 22nd ACM Symposium on Parallelism in Algorithms and Architectures, Santorini, Greece, 13-15 Jun 2010, Published in SPAA '10: Proceedings of the Twenty-Second Annual Symposium on Parallelism in Algorithms and Architectures, pp. 209-216
- Tiskin, Alexander, 2010. Parallel selection by regular sampling. 16th International Euro-Par Conference on Parallel Processing, Ischia, Italy, August 31 - September 03 2010
- 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
- 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
- Aziz, Haris, Lachish, Oded, Paterson, Michael S., Savani, Rahul, 2009. Power indices in spanning connectivity games. 5th International Conference on Algorithmic Aspects in Information and Management, San Francisco, CA, June 15-17, 2009, Published in Lecture Notes in Computer Science, pp. 55-67
- Adamaszek, Anna, Czumaj, Artur, Lingas, Andrzej, 2009. PTAS for k-tour cover problem on the plane for moderately large values of k. 20th International Symposium on Algorithms and Computations (ISAAC 2009), Honolulu, HI, December 16-18, 2009, Published in Lecture Notes in Computer Science, pp. 994-1003
- 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
- Jurdzinski, Marcin, 2009. Algorithms for solving infinite games. 35th Conference on Current Trends in Theory and Practice of Computer Science, Spindleruv Mlyn, Czech Republic, January 24-30, 2009, Published in Lecture Notes in Computer Science, pp. 46-48
- Jurdzinski, Marcin, Kwiatkowska, Marta, Norman, Gethin, Trivedi, Ashutosh, 2009. Concavely-priced probabilistic timed automata. 30th International Conference on Concurrency Theory, Bologna, Italy, September 01-04, 2009, Published in Lecture Notes in Computer Science, pp. 415-430
- Englert, Matthias, Röglin, Heiko, Spönemann, Jacob, Vöcking, Berthold, 2009. Economical caching. 26th International Symposium on Theoretical Aspects of Computer Science, Freiburg, Germany, Feb 2009, Published in Leibniz International Proceedings in Informatics (LIPIcs), pp. 385-396
- Englert, Matthias, Räcke, Harald, 2009. Oblivious routing for the Lp-norm. 50th Annual IEEE Symposium on Foundations of Computer Science, Atlanta, GA, October 25-27 2009, Published in 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 32-40
- Aziz, Haris, Paterson, Michael S., 2008. Classification of computationally tractable weighted voting games. World Congress on Engineering 2008, Imperial Coll London, London, England, Jul 02-04, 2008, Published in World Congress on Engineering : WCE 2008 : 2-4 July, 2008, Imperial College London, London, U.K, pp. 129-134
- Paterson, Michael S., Peres, Yuval, Thorup, Mikkel, Winkler, Peter, Zwick, Uri, 2008. Maximum overhang. 19th ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, Jan 20-22, 2008, Published in Proceedings of the 19th Annual ACM - SIAM Symposium on Discrete Algorithms, pp. 756-765
- Iwama, Kazuo, Nishimura, Harumichi, Paterson, Michael S., Raymond, Rudy, Yamashita, Shigeru, 2008. Polynomial-time construction of linear network coding. ICALP 2008: 35th International Colloquium on Automata, Languages and Programming, Reykjavik, Iceland, 6 - 13 Jul 2008, Published in Lecture Notes in Computer Science, pp. 271-282
- 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
- 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
- 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
- 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
- Aziz, Haris, Paterson, Michael S., Leech, Dennis, 2007. Efficient algorithm for designing weighted voting games. 11th IEEE International Multitopic Conference, Lahore, Pakistan, 28-30 Dec 2007, Published in IEEE International Multitopic Conference, 2007. INMIC 2007, pp. 211-216
- Czumaj, Artur, Lingas, Andrzej, 2007. Finding a heaviest triangle is not harder than matrix multiplication. 18th ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Los Angeles, 07-09 Jan 2007, Published in Proceeding SODA '07 Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 986-994
- Czumaj, Artur, Sohler, Christian, 2007. On testable properties in bounded degree graphs. 18th ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Los Angeles, 07-09 Jan 2007, Published in Proceeding SODA '07 Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 494-501
- Czumaj, Artur, Sohler, Christian, 2007. Sublinear-time approximation algorithms for clustering via random sampling. 12th International Conference on Random Structures and Algorithms, Poznan, Poland, 01-05 Aug 2005, Published in Random Structures & Algorithms, pp. 226-256
- Czumaj, Artur, Sohler, Christian, 2007. Testing expansion in bounded-degree graphs. 48th Annual IEEE Symposium on Foundations of Computer Science, Providence, RI, 20-23 Oct 2007, Published in 48th Annual IEEE Symposium on Foundations of Computer Science, 2007. FOCS '07, pp. 570-578
- Jurdzinski, Marcin, Lazic, Ranko, 2007. Alternation-free modal mu-calculus for data trees. 22nd Annual IEEE Symposium on Logic in Computer Science, Wroclaw, Poland, 10-14 Jul 2007, Published in 22nd Annual IEEE Symposium on Logic in Computer Science : proceedings : Wroc¿aw, Poland, 10-14 July, 2007, pp. 131-140
- 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
- Englert, Matthias, Westermann, Matthias, 2007. Considering suppressed packets improves buffer management in QoS switches. ACM-SIAM symposium on Discrete algorithms, New Orleans, Louisiana, 7-9 Jan 2007, Published in ACM-SIAM symposium on Discrete algorithms, pp. 209-218
- Englert, Matthias, Räcke, Harald, Westermann, Matthias, 2007. Reordering buffers for general metric spaces. ACM symposium on theory of computing, Published in STOC '07 Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pp. 556-564
- Englert, Matthias, Röglin, Heiko, Vöcking, Berthold, 2007. Worst case and probabilistic analysis of the 2-opt algorithm for the TSP. Eighteenth annual ACM-SIAM symposium on Discrete algorithm, New Orleans, Louisiana, 7-9 Jan 2007, Published in Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 1295-1304
- Jurdzinski, Marcin, Paterson, Michael S., Zwick, Uri, 2006. A deterministic subexponential algorithm for solving parity games. 17th ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, Jan 2006, Published in Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 117-123
- Dyer, Martin, Goldberg, Leslie Ann, Paterson, Michael S., 2006. On counting homomorphisms to directed acyclic graphs. 33rd International Colloquium on Automata, Languages and Programming, Venice, Italy, 10-14 Jul 2006, Published in Lecture Notes in Computer Science, pp. 38-49
- Paterson, Michael S., Zwick, Uri, 2006. Overhang. 17th ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, JAN, 2006, Published in Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 231-240
- Jurdzinski, Marcin, Peled, Doron, Qu, Hongyang, 2006. Calculating probabilities of real-time test cases. 5th International Workshop on Formal Approaches to Software Testing (FATES 2005), Edinburgh, 11 Jul 2005, Published in Formal Approaches to Software Testing, pp. 134-151
- Chatterjee, Krishnendu, Henzinger, Thomas A., Jurdzinski, Marcin, 2006. Games with secure equilibria. 3rd International Symposium on Formal Methods for Components and Objects, Leiden, Netherlands, 2-05 Nov 2004, Published in Theoretical Computer Science, pp. 67-82
- 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
- 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. 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. On model checking data-independent systems with arrays with whole-array operations. 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
- Dimovski, Aleksandar, Lazic, Ranko, 2004. Software model checking based on game semantics and CSP. 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
- 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
- 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
- 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
- Paterson, Michael S., Srinavasan, Aravind, 1995. Contention resolution with bounded delay. 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, M. S., Dancik, V., 1994. Longest common subsequences. University of Warwick. Department of Computer Science
- Paterson, Michael S., 1993. Computer science seminars 1992/93. 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
- 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
- Fischer, Michael J., Paterson, Michael S., 1992. Fishspear : a priority queue algorithm. 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
- Czumaj, Artur, 1992. An optimal parallel algorithm for computing a near-optimal order of matrix multiplications. 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
- Paterson, Michael S., Zwick, Uri, 1991. Shrinkage of de Morgan formulae under restriction. 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, 1990. Improved circuits and formulae for multiple addition, multiplication and symmetric Boolean functions. 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., Pippenger, Nicholas, Zwick, Uri, 1990. Optimal carry save networks. 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, 1989. Binary partitions with applications to hidden-surface removal and solid modelling. 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
- McColl, William Finlay, Paterson, Michael S., 1988. Planar acyclic computation. 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
- 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
- McColl, William Finlay, Paterson, Michael S., 1975. The depth of all Boolean functions. 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 |
---|---|---|---|

ALCOM-FT | EU DGXII | 01 Jun 2000 | 01 Dec 2003 |

International Computer Science Symposium in Russia (CSR2006) | Royal Society | 08 Jun 2006 | 07 Jul 2006 |

Scalable Software Model Checking Based on Game Semantics | EPSRC | 01 Oct 2003 | 30 Sep 2006 |

Discontinuous behaviour in the complexity of randomized algorithms | EPSRC | 01 Jan 2004 | 31 Dec 2006 |

Algorithmics of network-sharing games | EPSRC | 01 Jan 2005 | 30 Jun 2007 |

Parallel Computing 2007 (ParCo 2007) | Royal Society | 02 Sep 2007 | 08 Sep 2007 |

International Travel Grant - Periodic String Comparison | Royal Society | 22 Jun 2009 | 24 Jun 2009 |

Algorithms for Computing Equilibria in Games - (Fellow - R Savani) | EPSRC | 01 Oct 2006 | 30 Sep 2009 |

Fast distance multiplication of unit-monge matrices | Royal Society | 16 Jan 2010 | 19 Jan 2010 |

Special Structures in Vehicle Routing Problems | EPSRC | 17 Mar 2008 | 16 Mar 2010 |

Second Workshop on Timed Systems | British Council | 29 Mar 2010 | 31 Mar 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 |

Games for Quantative Analysis of Real Time Systems. | EPSRC | 01 Sep 2007 | 31 Aug 2010 |

Leverhulme Trust Senior Research Fellowship - 2009. Advanced Algorithms: Parallelism and Strings | Royal Society | 01 Oct 2009 | 30 Sep 2010 |

Postdoctoral Fellowship for Mathias Englert: Randomisation In Online Algorithms, Load Balancing and Other Dynamic Problems | EPSRC | 01 Sep 2008 | 31 Aug 2011 |

2006 RCUK Academic Fellowship Competition - Complexity Science | RCUK | 01 Oct 2006 | 30 Sep 2011 |

The Interplay between Algorithms and Randomness | Weizmann Institute of Science | 01 Jan 2010 | 31 Dec 2011 |

Advances in Sublinear Algorithms | EPSRC | 01 Sep 2009 | 31 Aug 2012 |

Efficient Decentralised Approaches in Algorithmic Game Theory | EPSRC | 01 Oct 2009 | 30 Sep 2012 |

The Centre for Discrete Mathematics and its Applications | EPSRC | 26 Mar 2007 | 25 Mar 2013 |

PATTERN MATCHING ALGORITHMS FOR STREAMING DATA (PDF FOR BEN SACH) | EPSRC | 01 Oct 2010 | 30 Sep 2013 |

Sigma: A New Online Learning System | JISC | 01 Jul 2013 | 30 Sep 2013 |

Extension to DIMAP - The centre for discrete mathematics and its applications | EPSRC | 26 Mar 2013 | 25 Mar 2014 |

Visiting Professorship - Formal verification, concurrency theory | Leverhulme Trust | 01 Feb 2015 | 31 Jul 2015 |

CCOSA: Classes of Combinatorial Objects from Structure to Algorithms: ERC Starting Fellowship for Dr Daniel Kral | European Research Council | 01 Oct 2012 | 30 Nov 2015 |

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 |

International Exchanges Scheme - 2013/R1; Advances in Approximation Algorithms. | Royal Society | 01 Sep 2013 | 29 Feb 2016 |

Counter Automata: Verification and Synthesis | EPSRC | 12 Jan 2015 | 11 Jul 2017 |

Automated reasoning for security and privacy: International Exchanges Standard Programme | Royal Society | 31 Mar 2017 | 01 Oct 2017 |

Algorithms for verifying systems with unbounded data and concurrency | Royal Society | 29 Jun 2015 | 28 Dec 2017 |

Scalable Indexing and Compression: Algorithms and Combinatorics (Early Career Fellowship for Golnaz Badkobeh) | Leverhulme Trust | 01 Sep 2015 | 31 Aug 2018 |

Analytic methods for large discrete structures | EPSRC | 01 Oct 2015 | 30 Sep 2018 |

Leverhulme Prize Application for Professor D Kral | Leverhulme Trust | 01 Oct 2015 | 30 Sep 2018 |

Sublinear Algorithms for Big Graphs | EPSRC | 01 Jan 2016 | 31 Dec 2018 |

Petri Net Reachability Conjecture | Leverhulme Trust | 01 Oct 2017 | 31 Dec 2018 |

Analysis of formal languages via computational complexity | Royal Society | 01 Feb 2018 | 31 Jan 2020 |

Large Discrete Structures (ERC Consolidator Grant Proposal) | European Research Council (ERC) | 01 Feb 2015 | 30 Nov 2020 |

Automata in the Wild ( Incubator event) | EPSRC | 15 Jan 2020 | 14 Jan 2021 |

Solving Parity Games in Theory and Practice | EPSRC | 01 May 2017 | 31 Jul 2021 |

Large Discrete Structures (ERC Consolidator Grant Proposal) | EU | 01 Dec 2015 | 31 Jul 2021 |

Royal Society University Research Fellowship ( 6 months costed extension for PDRA, IDEATE 63148 - R.CSAA.3234) | Royal Society | 01 Apr 2021 | 30 Sep 2021 |

IBM Faculty Award: Efficient Processing Methods for Big Graphs | IBM | 01 Oct 2017 | 30 Aug 2022 |

Weizmann - UK Joint Research Program: Combinatorial and Algorithmic Primitives for Modern Networks | Weizmann Institute of Science | 01 Oct 2018 | 30 Sep 2022 |

Theory and Applications of Dynamic Algorithms | EPSRC | 06 Jan 2020 | 05 Jan 2023 |

Structure vs Randomness in Algorithms and Computation | EPSRC | 01 Jul 2021 | 30 Jun 2023 |

Foundations of classical and quantum verifiable computing | UK Research and Innovation | 01 Jan 2020 | 31 Dec 2023 |

Theoretical Foundations of Modern Parallel and Distributed Algorithms | EPSRC | 01 Apr 2021 | 31 Mar 2024 |

Royal Society University Research Fellowship | Royal Society | 01 Oct 2019 | 30 Sep 2024 |