Publications by current BARC members, 2017-2023

• Mikkel Abrahamsen, Tzvika Geft, Dan Halperin, Barak Ugav. Coordination of Multiple Robots along Given Paths with Bounded Junction Complexity. AAMAS, 2023
• Mikkel Abrahamsen, Mikkel Thorup. How to Cut Corners and Get Bounded Convex Curvature. Discret. Comput. Geom., 2023
• Panagiotis Charalampopoulos, Pawel Gawrychowski, Yaowei Long, Shay Mozes, Seth Pettie, Oren Weimann, Christian Wulff-Nilsen. Almost Optimal Exact Distance Oracles for Planar Graphs. J. ACM, 2023
• Thomas Bellitto, Shaohua Li, Karolina Okrasa, Marcin Pilipczuk, Manuel Sorge. The Complexity of Routing Problems in Forbidden-Transition Graphs and Edge-Colored Graphs. Algorithmica, 2023
• Talya Eden, Shyam Narayanan, Jakub Tetek. Sampling an Edge in Sublinear Time Exactly and Optimally. SOSA, 2023
• Jacob Holm, Eva Rotenberg, Alice Ryhl. Splay Top Trees. SOSA, 2023
• Jakob Bæk Tejs Houen, Rasmus Pagh, Stefan Walzer. Simple Set Sketching. SOSA, 2023
• Shyam Narayanan, Jakub Tetek. Estimating the Effective Support Size in Constant Query Complexity. SOSA, 2023
• Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström. Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints. SODA, 2023
• Anders Aamand, Mikkel Abrahamsen, Lorenzo Beretta, Linda Kleist. Online Sorting and Translational Packing of Convex Polygons. SODA, 2023
• Gramoz Goranci, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak, Mikkel Thorup, Christian Wulff-Nilsen. Fully Dynamic Exact Edge Connectivity in Sublinear Time. SODA, 2023
• Christoph Grunau, Ahmet Alper Özüdogru, Václav Rozhon, Jakub Tetek. A Nearly Tight Analysis of Greedy k-means++. SODA, 2023
• Meike Hatzel, Lars Jaffke, Paloma T. Lima, Tomás Masarík, Marcin Pilipczuk, Roohani Sharma, Manuel Sorge. Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation. SODA, 2023
• Jacob Holm, Jakub Tetek. Massively Parallel Computation on Embedded Planar Graphs. SODA, 2023
• Lars Jaffke, Paloma T. Lima, Tomás Masarík, Marcin Pilipczuk, Uéverton S. Souza. A tight quasi-polynomial bound for Global Label Min-Cut. SODA, 2023
• Maciej Besta, Cesare Miglioli, Paolo Sylos Labini, Jakub Tetek, Patrick Iff, Raghavendra Kanakagiri, Saleh Ashkboos, Kacper Janda, Michal Podstawski, Grzegorz Kwasniewski, Niels Gleinig, Flavio Vella, Onur Mutlu, Torsten Hoefler. ProbGraph: High-Performance and High-Accuracy Graph Mining with Probabilistic Set Representations. SC, 2022
• Arkadev Chattopadhyay, Marek Cygan, Noga Ron-Zewi, Christian Wulff-Nilsen. Special Section on the Fifty-Second Annual ACM Symposium on the Theory of Computing (STOC 2020). SIAM J. Comput., 2022
• Rasmus Pagh, Mikkel Thorup. Improved Utility Analysis of Private CountSketch. NeurIPS, 2022
• Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas. On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials. CCC, 2022
• Radu Curticapean, Nutan Limaye, Srikanth Srinivasan. On the VNP-Hardness of Some Monomial Symmetric Polynomials. FSTTCS, 2022
• Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Marcin Pilipczuk, Michal Pilipczuk. On the Complexity of Problems on Tree-Structured Graphs. IPEC, 2022
• Aleksander B. G. Christiansen, Jacob Holm, Eva Rotenberg, Carsten Thomassen. On Dynamic α + 1 Arboricity Decomposition and Out-Orientation. MFCS, 2022
• Sébastien Tavenas, Nutan Limaye, Srikanth Srinivasan. Set-multilinear and non-commutative formula lower bounds for iterated matrix multiplication. STOC, 2022
• Christian Janos Lebeda, Martin Aumüller, Rasmus Pagh. Representing Sparse Vectors with Differential Privacy, Low Error, Optimal Space, and Fast Access. J. Priv. Confidentiality, 2022
• Tomás Masarík, Irene Muzi, Marcin Pilipczuk, Pawel Rzazewski, Manuel Sorge. Packing Directed Cycles Quarter- and Half-Integrally. Comb., 2022
• Meike Hatzel, Pawel Komosa, Marcin Pilipczuk, Manuel Sorge. Constant Congestion Brambles. Discret. Math. Theor. Comput. Sci., 2022
• David Coudert, André Nusser, Laurent Viennot. Enumeration of Far-apart Pairs by Decreasing Distance for Faster Hyperbolicity Computation. ACM J. Exp. Algorithmics, 2022
• Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh. Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering. SIAM J. Comput., 2022
• Anders Aamand, Debarati Das, Evangelos Kipouridis, Jakob Bæk Tejs Knudsen, Peter M. R. Rasmussen, Mikkel Thorup. No Repetition: Fast and Reliable Sampling with Highly Concentrated Hashing. Proc. VLDB Endow., 2022
• Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen. Negative-Weight Single-Source Shortest Paths in Near-linear Time. FOCS, 2022
• Jakub Gajarský, Lars Jaffke, Paloma T. Lima, Jana Novotná, Marcin Pilipczuk, Pawel Rzazewski, Uéverton S. Souza. Taming Graphs with No Large Creatures and Skinny Ladders. ESA, 2022
• Karl Bringmann, Anne Driemel, André Nusser, Ioannis Psarros. Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fréchet Distance. SODA, 2022
• Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner. Planar Graph Isomorphism Is in Log-Space. ACM Trans. Comput. Theory, 2022
• Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas. Guest Column: Lower Bounds Against Constant-Depth Algebraic Circuits. SIGACT News, 2022
• Shaohua Li, Marcin Pilipczuk. Hardness of Metric Dimension in Graphs of Constant Treewidth. Algorithmica, 2022
• Prasad Chaugule, Nutan Limaye. On the Closures of Monotone Algebraic Classes and Variants of the Determinant. LATIN, 2022
• Hugo Jacob, Marcin Pilipczuk. Bounding Twin-Width for Bounded-Treewidth Graphs, Planar Graphs, and Bipartite Graphs. WG, 2022
• Yi Li, Mingmou Liu. Lower Bounds for Sparse Oblivious Subspace Embeddings. PODS, 2022
• Mikkel Thorup. Dijkstra's Single Source Shortest Path Algorithm. Edsger Wybe Dijkstra, 2022
• Jakob Bæk Tejs Houen, Mikkel Thorup. Understanding the Moments of Tabulation Hashing via Chaoses. ICALP, 2022
• Konrad Majewski, Tomás Masarík, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Pawel Rzazewski, Marek Sokolowski. Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument. ICALP, 2022
• Jakub Tetek, Mikkel Thorup. Edge sampling and graph parameter estimation via vertex neighborhood accesses. STOC, 2022
• Radu Curticapean. Determinants from Homomorphisms. ESA, 2022
• Tomás Masarík, Marcin Pilipczuk, Pawel Rzazewski, Manuel Sorge. Constant Congestion Brambles in Directed Graphs. SIAM J. Discret. Math., 2022
• Matti Karppa, Rasmus Pagh. HyperLogLogLog: Cardinality Estimation With One Log More. KDD, 2022
• Martin Aumüller, Sariel Har-Peled, Sepideh Mahabadi, Rasmus Pagh, Francesco Silvestri. Sampling near neighbors in search for fairness. Commun. ACM, 2022
• Yixin Cao, Marcin Pilipczuk. Preface to the Special Issue on Parameterized and Exact Computation. Algorithmica, 2022
• Rasmus Pagh. Technical Perspective: Relative Error Streaming Quantiles. SIGMOD Rec., 2022
• Jakub Tetek. Approximate Triangle Counting via Sampling and Fast Matrix Multiplication. ICALP, 2022
• Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk. A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs. SIAM J. Comput., 2022
• Debarati Das, Evangelos Kipouridis, Maximilian Probst Gutenberg, Christian Wulff-Nilsen. A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs. SOSA, 2022
• Mikkel Thorup. Reconstructing the Tree of Life (Fitting Distances by Tree Metrics) (Invited Paper). SWAT, 2022
• Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström. Directed flow-augmentation. STOC, 2022
• Zhiyi Huang, Xinkai Shu, Shuyi Yan. The power of multiple choices in online stochastic matching. STOC, 2022
• Michael A. Bender, Martin Farach-Colton, John Kuszmaul, William Kuszmaul, Mingmou Liu. On the optimal time/space tradeoff for hash tables. STOC, 2022
• Ioana Oriana Bercea, Guy Even. An extendable data structure for incremental stable perfect hashing. STOC, 2022
• Andreas Björklund, Thore Husfeldt, Petteri Kaski. The shortest even cycle problem is tractable. STOC, 2022
• Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh. Fixed-parameter tractability of graph isomorphism in graphs with an excluded minor. STOC, 2022
• Martin Aumüller, Sariel Har-Peled, Sepideh Mahabadi, Rasmus Pagh, Francesco Silvestri. Sampling a Near Neighbor in High Dimensions - Who is the Fairest of Them All?. ACM Trans. Database Syst., 2022
• Anders Aamand, Mikkel Abrahamsen, Thomas D. Ahle, Peter M. R. Rasmussen. Tiling with Squares and Packing Dominos in Polynomial Time. SoCG, 2022
• Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, Dániel Marx, André Nusser. Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves. SoCG, 2022
• Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, André Nusser, Zahra Parsaeian. Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs. SoCG, 2022
• Kevin Buchin, André Nusser, Sampson Wong. Computing Continuous Dynamic Time Warping of Time Series in Polynomial Time. SoCG, 2022
• Matti Karppa, Martin Aumüller, Rasmus Pagh. DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Search. AISTATS, 2022
• Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, Jakub Onufry Wojtaszczyk. Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time. ACM Trans. Algorithms, 2022
• Lorenzo Beretta, Jakub Tetek. Better Sum Estimation via Weighted Sampling. SODA, 2022
• Debarati Das, Maximilian Probst Gutenberg, Christian Wulff-Nilsen. A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs. SODA, 2022
• Marvin Künnemann, André Nusser. Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Improvement via Offline Dynamic Rectangle Union. SODA, 2022
• David Coudert, André Nusser, Laurent Viennot. Computing Graph Hyperbolicity Using Dominating Sets. ALENEX, 2022
• Radu Curticapean, Mingji Xia. Parameterizing the Permanent: Hardness for fixed excluded minors. SOSA, 2022
• Mikkel Abrahamsen, Anna Adamaszek, Tillmann Miltzow. The Art Gallery Problem is ∃ℝ-complete. J. ACM, 2022
• Rasmus Pagh, Nina Mesing Stausholm. Infinitely Divisible Noise in the Low Privacy Regime. ALT, 2022
• Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan. A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates. Algorithmica, 2022
• Stephen Alstrup, Søren Dahlgaard, Arnold Filtser, Morten Stöckel, Christian Wulff-Nilsen. Constructing light spanners deterministically in near-linear time. Theor. Comput. Sci., 2022
• Andrzej Grzesik, Tereza Klimosová, Marcin Pilipczuk, Michal Pilipczuk. Polynomial-time Algorithm for Maximum Weight Independent Set on P₆-free Graphs. ACM Trans. Algorithms, 2022
• Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas. Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits. FOCS, 2021
• Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista A. Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oliveira, Hubert Eichner, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaïd Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konecný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Hang Qi, Daniel Ramage, Ramesh Raskar, Mariana Raykova, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, Sen Zhao. Advances and Open Problems in Federated Learning. Found. Trends Mach. Learn., 2021
• Jakub Tetek, Marek Sklenka, Tomas Gavenciak. Performance of Bounded-Rational Agents With the Ability to Self-Modify. SafeAI@AAAI, 2021
• Jiehua Chen, Wojciech Czerwinski, Yann Disser, Andreas Emil Feldmann, Danny Hermelin, Wojciech Nadara, Marcin Pilipczuk, Michal Pilipczuk, Manuel Sorge, Bartlomiej Wróblewski, Anna Zych-Pawlewicz. Efficient fully dynamic elimination forests with applications to detecting long paths and cycles. SODA, 2021
• André Nusser. Fine-grained complexity and algorithm engineering of geometric similarity measures. , 2021
• Thore Husfeldt. The Presburger Award 2021 - Laudatio for Shayan Oveis Gharan. Bull. EATCS, 2021
• Ioana O. Bercea, Guy Even. Upper Tail Analysis of Bucket Sort and Random Tries. CIAC, 2021
• Hugo Jacob, Thomas Bellitto, Oscar Defrain, Marcin Pilipczuk. Close Relatives (Of Feedback Vertex Set), Revisited. IPEC, 2021
• Ioana O. Bercea, Guy Even. Dynamic Dictionaries for Multisets and Counting Filters with Constant Time Operations. WADS, 2021
• Marcin Pilipczuk, Ni Luh Dewi Sintiari, Stéphan Thomassé, Nicolas Trotignon. (Theta, triangle)-free and (even hole, K₄)-free graphs. Part 2: Bounds on treewidth. J. Graph Theory, 2021
• Ioana O. Bercea, Guy Even. Upper tail analysis of bucket sort and random tries. Theor. Comput. Sci., 2021
• Andrzej Grzesik, Tereza Klimosová, Marcin Pilipczuk, Michal Pilipczuk. Covering Minimal Separators and Potential Maximal Cliques in $P_t$-Free Graphs. Electron. J. Comb., 2021
• Karl Bringmann, Marvin Künnemann, André Nusser. Walking the dog fast in practice: Algorithm engineering of the Fréchet distance. J. Comput. Geom., 2021
• Mikkel Abrahamsen, Linda Kleist, Tillmann Miltzow. Training Neural Networks is ER-complete. NeurIPS, 2021
• Martin Aumüller, Christian Janos Lebeda, Rasmus Pagh. Differentially Private Sparse Vectors with Low Error, Optimal Space, and Fast Access. CCS, 2021
• Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, Ameya Velingker. On the Power of Multiple Anonymous Messages: Frequency Estimation and Selection in the Shuffle Model of Differential Privacy. EUROCRYPT (3), 2021
• Mikkel Abrahamsen. Covering Polygons is Even Harder. FOCS, 2021
• Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis, Nikos Parotsidis, Mikkel Thorup. Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor. FOCS, 2021
• Rasmus Pagh, Nina Mesing Stausholm. Efficient Differentially Private F₀ Linear Sketching. ICDT, 2021
• Shaohua Li, Marcin Pilipczuk. Hardness of Metric Dimension in Graphs of Constant Treewidth. IPEC, 2021
• Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström. Solving hard cut problems via flow-augmentation. SODA, 2021
• Stefan Kratsch, Tomás Masarík, Irene Muzi, Marcin Pilipczuk, Manuel Sorge. Optimal Discretization is Fixed-parameter Tractable. SODA, 2021
• Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski. Quasi-polynomial-time algorithm for Independent Set in P_t-free graphs via shrinking the space of induced paths. SOSA, 2021
• Jacob Holm, Eva Rotenberg. Good r-Divisions Imply Optimal Amortized Decremental Biconnectivity. STACS, 2021
• Shaohua Li, Marcin Pilipczuk, Manuel Sorge. Cluster Editing Parameterized Above Modification-Disjoint P₃-Packings. STACS, 2021
• Anders Aamand, Jakob Bæk Tejs Knudsen, Mikkel Thorup. Load balancing with dynamic set of balls and bins. STOC, 2021
• Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski. Finding large induced sparse subgraphs in c_>t -free graphs in quasipolynomial time. STOC, 2021
• Christian Hansen, Casper Hansen, Jakob Grue Simonsen, Stephen Alstrup, Christina Lioma. Unsupervised Multi-Index Semantic Hashing. WWW, 2021
• Marthe Bonamy, François Dross, Tomás Masarík, Andrea Munaro, Wojciech Nadara, Marcin Pilipczuk, Michal Pilipczuk. Jones' Conjecture in Subcubic Graphs. Electron. J. Comb., 2021
• Wojciech Czerwinski, Wojciech Nadara, Marcin Pilipczuk. Improved Bounds for the Excluded-Minor Approximation of Treedepth. SIAM J. Discret. Math., 2021
• Bart M. P. Jansen, Marcin Pilipczuk, Erik Jan van Leeuwen. A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs. SIAM J. Discret. Math., 2021
• Martin Aumüller, Sariel Har-Peled, Sepideh Mahabadi, Rasmus Pagh, Francesco Silvestri. Fair near neighbor search via sampling. SIGMOD Rec., 2021
• On-Hei Solomon Lo, Jens M. Schmidt, Mikkel Thorup. Compact cactus representations of all non-trivial min-cuts. Discret. Appl. Math., 2021
• Hung Le, Christian Wulff-Nilsen. Optimal Approximate Distance Oracle for Planar Graphs. FOCS, 2021
• Radu Curticapean. A full complexity dichotomy for immanant families. STOC, 2021
• Boel Nelson. Efficient Error Prediction for Differentially Private Algorithms. ARES, 2021
• Anders Aamand, Mikkel Abrahamsen, Jakob Bæk Tejs Knudsen, Peter Michael Reichstein Rasmussen. Classifying Convex Bodies by Their Contact and Intersection Graphs. SoCG, 2021
• Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna, Maarten Löffler, Tillmann Miltzow, Jérôme Urhausen, Jordi L. Vermeulen, Giovanni Viglietta. Chasing Puppies: Mobile Beacon Routing on Closed Curves. SoCG, 2021
• Mikkel Abrahamsen, Lorenzo Beretta. Online Packing to Minimize Area or Perimeter. SoCG, 2021
• Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Pawel Rzazewski, Paul D. Seymour. Induced subgraphs of bounded treewidth and the container method. SODA, 2021
• Anne Driemel, André Nusser, Jeff M. Phillips, Ioannis Psarros. The VC Dimension of Metric Balls under Fréchet and Hausdorff Distances. Discret. Comput. Geom., 2021
• Jacob Evald, Viktor Fredslund-Hansen, Christian Wulff-Nilsen. Near-Optimal Distance Oracles for Vertex-Labeled Planar Graphs. ISAAC, 2021
• Viktor Fredslund-Hansen, Shay Mozes, Christian Wulff-Nilsen. Truly Subquadratic Exact Distance Oracles with Constant Query Time for Planar Graphs. ISAAC, 2021
• Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, S. Venkitesh. A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem. SIAM J. Comput., 2021
• Prasad Chaugule, Nutan Limaye, Aditya Varre. Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes. ACM Trans. Comput. Theory, 2021
• Radu Curticapean, Holger Dell, Thore Husfeldt. Modular Counting of Subgraphs: Matchings, Matching-Splittable Graphs, and Paths. ESA, 2021
• Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, Amer Sinha. Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message. ICML, 2021
• Kasper Green Larsen, Rasmus Pagh, Jakub Tetek. CountSketches, Feature Hashing and the Median of Three. ICML, 2021
• Karl Bringmann, Marvin Künnemann, André Nusser. Discrete Fréchet Distance under Translation: Conditional Hardness and an Improved Algorithm. ACM Trans. Algorithms, 2021
• Emilio Cruciani, Emanuele Natale, André Nusser, Giacomo Scornavacca. Phase transition of the 2-Choices dynamics on core-periphery networks. Distributed Comput., 2021
• Prasad Chaugule, Nutan Limaye, Shourya Pandey. Variants of the Determinant Polynomial and the VP-Completeness. CSR, 2021
• Jacob Evald, Viktor Fredslund-Hansen, Maximilian Probst Gutenberg, Christian Wulff-Nilsen. Decremental APSP in Unweighted Digraphs Versus an Adaptive Adversary. ICALP, 2021
• Angela Bonifati, Rasmus Pagh, Thomas Schwentick. 2021 ACM PODS Alberto O. Mendelzon Test-of-Time Award. PODS, 2021
• Karl Bringmann, André Nusser. Translating Hausdorff Is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation. SoCG, 2021
• Jeremy Kun, Michael P. O'Brien, Marcin Pilipczuk, Blair D. Sullivan. Polynomial Treedepth Bounds in Linear Colorings. Algorithmica, 2021
• Marek Cygan, Pawel Komosa, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh, Magnus Wahlström. Randomized Contractions Meet Lean Decompositions. ACM Trans. Algorithms, 2021
• Loïc Dubois, Gwenaël Joret, Guillem Perarnau, Marcin Pilipczuk, François Pitois. Two lower bounds for $p$-centered colorings. Discret. Math. Theor. Comput. Sci., 2020
• Marcin Pilipczuk, Manuel Sorge. A Double Exponential Lower Bound for the Distinct Vectors Problem. Discret. Math. Theor. Comput. Sci., 2020
• Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, Srikanth Srinivasan. Schur Polynomials Do Not Have Small Formulas If the Determinant Doesn't. CCC, 2020
• Maria Chudnovsky, Marcin Pilipczuk, Michal Pilipczuk, Stéphan Thomassé. Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs. SODA, 2020
• Ioana O. Bercea, Guy Even. A Dynamic Space-Efficient Filter with Constant Time Operations. SWAT, 2020
• Maria Chudnovsky, Marcin Pilipczuk, Michal Pilipczuk, Stéphan Thomassé. On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five. SIAM J. Discret. Math., 2020
• Mohsen Ghaffari, Krzysztof Nowicki, Mikkel Thorup. Faster Algorithms for Edge Connectivity via Random 2-Out Contractions. SODA, 2020
• Mikkel Abrahamsen, Tillmann Miltzow, Nadja Seiferth. Framework for ER-Completeness of Two-Dimensional Packing Problems. FOCS, 2020
• Lukasz Kowalik, Marcin Mucha, Wojciech Nadara, Marcin Pilipczuk, Manuel Sorge, Piotr Wygocki. The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth. IPEC, 2020
• Mikkel Abrahamsen, Stephen Alstrup, Jacob Holm, Mathias Bæk Tejs Knudsen, Morten Stöckel. Near-optimal induced universal graphs for cycles and paths. Discret. Appl. Math., 2020
• Mikkel Abrahamsen, Mark de Berg, Kevin Buchin, Mehran Mehr, Ali D. Mehrabi. Minimum Perimeter-Sum Partitions in the Plane. Discret. Comput. Geom., 2020
• Mikkel Abrahamsen, Panos Giannopoulos, Maarten Löffler, Günter Rote. Geometric Multicut: Shortest Fences for Separating Groups of Objects in the Plane. Discret. Comput. Geom., 2020
• Milutin Brankovic, Kevin Buchin, Koen Klaren, André Nusser, Aleksandr Popov, Sampson Wong. (k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time Warping. SIGSPATIAL/GIS, 2020
• Mingmou Liu, Yitong Yin, Huacheng Yu. Succinct Filters for Sets of Unknown Sizes. ICALP, 2020
• Thomas Bellitto, Shaohua Li, Karolina Okrasa, Marcin Pilipczuk, Manuel Sorge. The Complexity of Connectivity Problems in Forbidden-Transition Graphs And Edge-Colored Graphs. ISAAC, 2020
• Anders Aamand, Jakob Bæk Tejs Knudsen, Mathias Bæk Tejs Knudsen, Peter Michael Reichstein Rasmussen, Mikkel Thorup. Fast hashing with strong concentration bounds. STOC, 2020
• Mingmou Liu, Huacheng Yu. Lower bound for succinct range minimum query. STOC, 2020
• Stefan Kratsch, Shaohua Li, Dániel Marx, Marcin Pilipczuk, Magnus Wahlström. Multi-budgeted Directed Cuts. Algorithmica, 2020
• Shaohua Li, Marcin Pilipczuk. An Improved FPT Algorithm for Independent Feedback Vertex Set. Theory Comput. Syst., 2020
• Christian Hansen, Casper Hansen, Jakob Grue Simonsen, Birger Larsen, Stephen Alstrup, Christina Lioma. Factuality Checking in News Headlines with Eye Tracking. SIGIR, 2020
• Casper Hansen, Christian Hansen, Jakob Grue Simonsen, Stephen Alstrup, Christina Lioma. Content-aware Neural Hashing for Cold-start Recommendation. SIGIR, 2020
• Casper Hansen, Christian Hansen, Jakob Grue Simonsen, Stephen Alstrup, Christina Lioma. Unsupervised Semantic Hashing with Pairwise Reconstruction. SIGIR, 2020
• Thomas D. Ahle, Michael Kapralov, Jakob Bæk Tejs Knudsen, Rasmus Pagh, Ameya Velingker, David P. Woodruff, Amir Zandieh. Oblivious Sketching of High-Degree Polynomial Kernels. SODA, 2020
• Maximilian Probst Gutenberg, Christian Wulff-Nilsen. Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler. SODA, 2020
• Maximilian Probst Gutenberg, Christian Wulff-Nilsen. Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary. SODA, 2020
• Maximilian Probst Gutenberg, Christian Wulff-Nilsen. Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds. SODA, 2020
• Jacob Holm, Eva Rotenberg. Worst-Case Polylog Incremental SPQR-trees: Embeddings, Planarity, and Triconnectivity. SODA, 2020
• Mikkel Abrahamsen, Jacob Holm, Eva Rotenberg, Christian Wulff-Nilsen. Escaping an Infinitude of Lions. Am. Math. Mon., 2020
• Karl Bringmann, Thore Husfeldt, Måns Magnusson. Multivariate Analysis of Orthogonal Range Searching and Graph Distances. Algorithmica, 2020
• Jacob Holm, Eva Rotenberg. Fully-dynamic planarity testing in polylogarithmic time. STOC, 2020
• Kai-Yuan Lai, Hsueh-I Lu, Mikkel Thorup. Three-in-a-tree in near linear time. STOC, 2020
• Thore Husfeldt, Meena Mahajan, Mikolaj Bojanczyk. The Presburger Award for Young Scientists 2021 - Call for Nominations. Bull. EATCS, 2020
• Anders Aamand, Mikkel Abrahamsen, Mikkel Thorup. Disks in Curves of Bounded Convex Curvature. Am. Math. Mon., 2020
• Boel Nelson, Jenni Reuben. SoK: Chasing Accuracy and Privacy, and Catching Both in Differentially Private Histogram Publication. Trans. Data Priv., 2020
• Thomas D. Ahle, Jakob Bæk Tejs Knudsen. Subsets and Supermajorities: Optimal Hashing-based Set Similarity Search. FOCS, 2020
• Aaron Bernstein, Maximilian Probst Gutenberg, Christian Wulff-Nilsen. Near-Optimal Decremental SSSP in Dense Weighted Digraphs. FOCS, 2020
• Edith Cohen, Rasmus Pagh, David P. Woodruff. WOR and p's: Sketches for ℓ_p-Sampling Without Replacement. NeurIPS, 2020
• Edith Cohen, Ofir Geri, Rasmus Pagh. Composable Sketches for Functions of Frequencies: Beyond the Worst Case. ICML, 2020
• Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh. Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead. ICML, 2020
• Tobias Christiani, Rasmus Pagh, Mikkel Thorup. Confirmation Sampling for Exact Nearest Neighbor Search. SISAP, 2020
• Mayank Goswami, Riko Jacob, Rasmus Pagh. On the I/O Complexity of the k-Nearest Neighbors Problem. PODS, 2020
• Yasuo Tabei, Yoshihiro Yamanishi, Rasmus Pagh. Space-Efficient Feature Maps for String Alignment Kernels. Data Sci. Eng., 2020
• Karl Bringmann, Marvin Künnemann, André Nusser. When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance Under Translation. ESA, 2020
• Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, Ameya Velingker. Pure Differentially Private Summation from Anonymous Messages. ITC, 2020
• Thore Husfeldt. Algebraic Algorithms for Finding Patterns in Graphs (Invited Talk). CPM, 2020
• Nikhil Balaji, Andreas Krebs, Nutan Limaye. Skew circuits of small width. Theor. Comput. Sci., 2020
• Martin Aumüller, Rasmus Pagh, Francesco Silvestri. Fair Near Neighbor Search: Independent Range Sampling in High Dimensions. PODS, 2020
• Badih Ghazi, Pasin Manurangsi, Rasmus Pagh, Ameya Velingker. Private Aggregation from Fewer Anonymous Messages. EUROCRYPT (2), 2020
• Marcin Pilipczuk. Surprising Applications of Treewidth Bounds for Planar Graphs. Treewidth, Kernels, and Algorithms, 2020
• Rasmus Pagh, Johan Sivertsen. The Space Complexity of Inner Product Filters. ICDT, 2020
• Yin Tat Lee, Marcin Pilipczuk, David P. Woodruff. Introduction to the Special Issue on SODA'18. ACM Trans. Algorithms, 2020
• Nikolai Karpov, Marcin Pilipczuk, Anna Zych-Pawlewicz. An Exponential Lower Bound for Cut Sparsifiers in Planar Graphs. Algorithmica, 2019
• Wojciech Nadara, Marcin Pilipczuk, Roman Rabinovich, Felix Reidl, Sebastian Siebertz. Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness. ACM J. Exp. Algorithmics, 2019
• Ioana Oriana Bercea, Martin Groß, Samir Khuller, Aounon Kumar, Clemens Rösner, Daniel R. Schmidt, Melanie Schmidt. On the Cost of Essentially Fair Clusterings. APPROX-RANDOM, 2019
• Magnus Stavngaard, August Sørensen, Stephan Lorenzen, Niklas Hjuler, Stephen Alstrup. Detecting Ghostwriters in High Schools. ESANN, 2019
• Tomás Masarík, Irene Muzi, Marcin Pilipczuk, Pawel Rzazewski, Manuel Sorge. Packing Directed Circuits Quarter-Integrally. ESA, 2019
• Lorenzo Beretta, Franco Maria Nardini, Roberto Trani, Rossano Venturini. An Optimal Algorithm to Find Champions of Tournament Graphs. SPIRE, 2019
• Tomas Gavenciak, Jakub Tetek. Compact I/O-Efficient Representation of Separable Graphs and Optimal Tree Layouts. TAMC, 2019
• Mikkel Abrahamsen. Spiral tool paths for high-speed machining of 2D pockets with or without islands. J. Comput. Des. Eng., 2019
• Mikkel Abrahamsen, Bartosz Walczak. Common Tangents of Two Disjoint Polygons in Linear Time and Constant Workspace. ACM Trans. Algorithms, 2019
• Nutan Limaye, Srikanth Srinivasan, Utkarsh Tripathi. More on AC^0[oplus] and Variants of the Majority Function. FSTTCS, 2019
• Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan. A #SAT Algorithm for Small Constant-Depth Circuits with PTF Gates. ITCS, 2019
• Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, S. Venkitesh. A fixed-depth size-hierarchy theorem for AC⁰[⊕] via the coin problem. STOC, 2019
• Guillaume Lagarde, Nutan Limaye, Srikanth Srinivasan. Lower Bounds and PIT for Non-commutative Arithmetic Circuits with Restricted Parse Trees. Comput. Complex., 2019
• Anita Liebenau, Marcin Pilipczuk, Paul D. Seymour, Sophie Spirkl. Caterpillars in Erdős-Hajnal. J. Comb. Theory, Ser. B, 2019
• Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan. Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications. SIAM J. Comput., 2019
• Anders Aamand, Mikkel Thorup. Non-empty Bins with Simple Tabulation Hashing. SODA, 2019
• Glencora Borradaile, Hung Le, Christian Wulff-Nilsen. Greedy spanners are optimal in doubling metrics. SODA, 2019
• Karl Bringmann, Marvin Künnemann, André Nusser. Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability. SODA, 2019
• Andrzej Grzesik, Tereza Klimosová, Marcin Pilipczuk, Michal Pilipczuk. Polynomial-time algorithm for Maximum Weight Independent Set on P6-free graphs. SODA, 2019
• Karl Bringmann, Marvin Künnemann, André Nusser. Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance. SoCG, 2019
• Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen, Mikkel Thorup. Heavy hitters via cluster-preserving clustering. Commun. ACM, 2019
• Thore Husfeldt, Meena Mahajan, Anca Muscholl. The Presburger Award for Young Scientists 2020 - Call for Nominations. Bull. EATCS, 2019
• Christian Hansen, Casper Hansen, Stephen Alstrup, Christina Lioma. Modelling End-of-Session Actions in Educational Systems. EDM, 2019
• Stephan Lorenzen, Niklas Hjuler, Stephen Alstrup. Investigating Writing Style Development in High School. EDM, 2019
• Martin Hora, Václav Koncický, Jakub Tetek. Theoretical Model of Computation and Algorithms for FPGA-Based Hardware Accelerators. TAMC, 2019
• Akanksha Agrawal, Arindam Biswas, Édouard Bonnet, Nick Brettell, Radu Curticapean, Dániel Marx, Tillmann Miltzow, Venkatesh Raman, Saket Saurabh. Parameterized Streaming Algorithms for Min-Ones d-SAT. FSTTCS, 2019
• Michal Ziobro, Marcin Pilipczuk. Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation. ACM J. Exp. Algorithmics, 2019
• Casper Hansen, Christian Hansen, Stephen Alstrup, Jakob Grue Simonsen, Christina Lioma. Contextually Propagated Term Weights for Document Representation. SIGIR, 2019
• Casper Hansen, Christian Hansen, Jakob Grue Simonsen, Stephen Alstrup, Christina Lioma. Unsupervised Neural Generative Semantic Hashing. SIGIR, 2019
• Aaron Bernstein, Jacob Holm, Eva Rotenberg. Online Bipartite Matching with Amortized O(log ² n) Replacements. J. ACM, 2019
• Stephen Alstrup, Haim Kaplan, Mikkel Thorup, Uri Zwick. Adjacency Labeling Schemes and Induced-Universal Graphs. SIAM J. Discret. Math., 2019
• Ivona Bezáková, Radu Curticapean, Holger Dell, Fedor V. Fomin. Finding Detours is Fixed-Parameter Tractable. SIAM J. Discret. Math., 2019
• Jacob Holm, Valerie King, Mikkel Thorup, Or Zamir, Uri Zwick. Random k-out Subgraph Leaves only O(n/k) Inter-Component Edges. FOCS, 2019
• Kevin Buchin, Anne Driemel, Natasja van de L'Isle, André Nusser. klcluster: Center-based Clustering of Trajectories. SIGSPATIAL/GIS, 2019
• Yasuo Tabei, Yoshihiro Yamanishi, Rasmus Pagh. Space-Efficient Feature Maps for String Alignment Kernels. ICDM, 2019
• Andreas Björklund, Thore Husfeldt. Shortest Two Disjoint Paths in Polynomial Time. SIAM J. Comput., 2019
• Vincent Cohen-Addad, Michal Pilipczuk, Marcin Pilipczuk. A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs. FOCS, 2019
• Radu Curticapean, Holger Dell, Fedor V. Fomin, Leslie Ann Goldberg, John Lapinskas. A Fixed-Parameter Perspective on #BIS. Algorithmica, 2019
• Bart M. P. Jansen, Marcin Pilipczuk, Marcin Wrochna. Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor. Algorithmica, 2019
• Tomasz Kociumaka, Marcin Pilipczuk. Deleting Vertices to Graphs of Bounded Genus. Algorithmica, 2019
• Mikkel Thorup, Or Zamir, Uri Zwick. Dynamic Ordered Sets with Approximate Queries, Approximate Heaps and Soft Heaps. ICALP, 2019
• Casper Hansen, Christian Hansen, Stephen Alstrup, Jakob Grue Simonsen, Christina Lioma. Neural Check-Worthiness Ranking with Weak Supervision: Finding Sentences for Fact-Checking. WWW (Companion Volume), 2019
• Ken-ichi Kawarabayashi, Mikkel Thorup. Deterministic Edge Connectivity in Near-Linear Time. J. ACM, 2019
• Martin Aumüller, Tobias Christiani, Rasmus Pagh, Michael Vesterli. PUFFINN: Parameterless and Universally Fast FInding of Nearest Neighbors. ESA, 2019
• Rasmus Pagh, Nina Mesing Stausholm, Mikkel Thorup. Hardness of Bichromatic Closest Pair with Jaccard Similarity. ESA, 2019
• Hubie Chen, Radu Curticapean, Holger Dell. The Exponential-Time Complexity of Counting (Quantum) Graph Homomorphisms. WG, 2019
• Marcin Pilipczuk, Michal Pilipczuk, Marcin Wrochna. Edge Bipartization Faster than $$2^k$$ 2 k. Algorithmica, 2019
• Stephen Alstrup, Søren Dahlgaard, Arnold Filtser, Morten Stöckel, Christian Wulff-Nilsen. Constructing Light Spanners Deterministically in Near-Linear Time. ESA, 2019
• Vincent Cohen-Addad, Marcin Pilipczuk, Michal Pilipczuk. Efficient Approximation Schemes for Uniform-Cost Clustering Problems in Planar Graphs. ESA, 2019
• Wojciech Czerwinski, Wojciech Nadara, Marcin Pilipczuk. Improved Bounds for the Excluded-Minor Approximation of Treedepth. ESA, 2019
• Gábor Bacsó, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Zsolt Tuza, Erik Jan van Leeuwen. Subexponential-Time Algorithms for Maximum Independent Set in $$P_t$$ P t -Free and Broom-Free Graphs. Algorithmica, 2019
• Stefan Funke, Tobias Rupp, André Nusser, Sabine Storandt. PATHFINDER: Storage and Indexing of Massive Trajectory Sets. SSTD, 2019
• Mikkel Abrahamsen, Panos Giannopoulos, Maarten Löffler, Günter Rote. Geometric Multicut. ICALP, 2019
• Radu Curticapean, Holger Dell, Marc Roth. Counting Edge-injective Homomorphisms and Matchings on Restricted Graph Classes. Theory Comput. Syst., 2019
• Christian Hansen, Casper Hansen, Stephen Alstrup, Jakob Grue Simonsen, Christina Lioma. Neural Speed Reading with Structural-Jump-LSTM. ICLR (Poster), 2019
• Prasad Chaugule, Nutan Limaye, Aditya Varre. Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes. COCOON, 2019
• Aaron Bernstein, Maximilian Probst, Christian Wulff-Nilsen. Decremental strongly-connected components and single-source reachability in near-linear time. STOC, 2019
• Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh. Minimum Bisection Is Fixed-Parameter Tractable. SIAM J. Comput., 2019
• Bart M. P. Jansen, Marcin Pilipczuk, Erik Jan van Leeuwen. A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs. STACS, 2019
• Rasmus Pagh. Similarity Sketching. Encyclopedia of Big Data Technologies, 2019
• Suryajith Chillara, Christian Engels, Nutan Limaye, Srikanth Srinivasan. A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits. FOCS, 2018
• Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk. On Subexponential Parameterized Algorithms for Steiner Tree and Directed Subset TSP on Planar Graphs. FOCS, 2018
• Tobias Christiani, Rasmus Pagh, Johan Sivertsen. Scalable and Robust Set Similarity Join. ICDE, 2018
• Emilio Cruciani, Emanuele Natale, André Nusser, Giacomo Scornavacca. On the Emergent Behavior of the 2-Choices Dynamics. ICTCS, 2018
• Wojciech Nadara, Marcin Pilipczuk, Roman Rabinovich, Felix Reidl, Sebastian Siebertz. Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness. SEA, 2018
• Cornelius Brand, Holger Dell, Thore Husfeldt. Extensor-coding. STOC, 2018
• Krzysztof Choromanski, Dvir Falik, Anita Liebenau, Viresh Patel, Marcin Pilipczuk. Excluding Hooks and their Complements. Electron. J. Comb., 2018
• Stephen Alstrup, Agelos Georgakopoulos, Eva Rotenberg, Carsten Thomassen. A Hamiltonian Cycle in the Square of a 2-connected Graph in Linear Time. SODA, 2018
• Aaron Bernstein, Jacob Holm, Eva Rotenberg. Online Bipartite Matching with Amortized Replacements. SODA, 2018
• Jacob Holm, Eva Rotenberg, Mikkel Thorup. Dynamic Bridge-Finding in Õ(log² n) Amortized Time. SODA, 2018
• Rasmus Pagh. CoveringLSH: Locality-Sensitive Hashing without False Negatives. ACM Trans. Algorithms, 2018
• Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann, Vincent Cohen-Addad, Mehran Mehr, Eva Rotenberg, Alan Roytman, Mikkel Thorup. Fast fencing. STOC, 2018
• Mikkel Abrahamsen, Anna Adamaszek, Tillmann Miltzow. The art gallery problem is ∃ ℝ-complete. STOC, 2018
• Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan. A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas. ICALP, 2018
• Stefan Kratsch, Shaohua Li, Dániel Marx, Marcin Pilipczuk, Magnus Wahlström. Multi-Budgeted Directed Cuts. IPEC, 2018
• Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan. Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications. STACS, 2018
• Mingmou Liu, Xiaoyin Pan, Yitong Yin. Randomized Approximate Nearest Neighbor Search with Limited Adaptivity. ACM Trans. Parallel Comput., 2018
• Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, Michal Pilipczuk. Subexponential Parameterized Algorithm for Interval Completion. ACM Trans. Algorithms, 2018
• Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz, Jakub Lacki, Eva Rotenberg. Decremental SPQR-trees for Planar Graphs. ESA, 2018
• Emilio Cruciani, Emanuele Natale, André Nusser, Giacomo Scornavacca. Phase Transition of the 2-Choices Dynamics on Core-Periphery Networks. Bull. EATCS, 2018
• Radu Curticapean, Nathan Lindzey, Jesper Nederlof. A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank. SODA, 2018
• Pawel Gawrychowski, Shay Mozes, Oren Weimann, Christian Wulff-Nilsen. Better Tradeoffs for Exact Distance Oracles in Planar Graphs. SODA, 2018
• Mathias Bæk Tejs Knudsen, Mikkel Thorup. The Entropy of Backwards Analysis. SODA, 2018
• Vahab S. Mirrokni, Mikkel Thorup, Morteza Zadimoghaddam. Consistent Hashing with Bounded Loads. SODA, 2018
• Matej Konecný, Stanislav Kucera, Jana Novotná, Jakub Pekárek, Martin Smolík, Jakub Tetek, Martin Töpfer. On the Simultaneous Minimum Spanning Trees Problem. CALDAM, 2018
• Radu Curticapean. Block interpolation: A framework for tight exponential-time counting complexity. Inf. Comput., 2018
• Anders Aamand, Niklas Hjuler, Jacob Holm, Eva Rotenberg. One-Way Trail Orientations. ICALP, 2018
• Marcin Pilipczuk, Magnus Wahlström. Directed Multicut is W[1]-hard, Even for Four Terminal Pairs. ACM Trans. Comput. Theory, 2018
• Chandra Chekuri, Alina Ene, Marcin Pilipczuk. Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs. SIAM J. Discret. Math., 2018
• Bart M. P. Jansen, Marcin Pilipczuk. Approximation and Kernelization for Chordal Vertex Deletion. SIAM J. Discret. Math., 2018
• Ha-Myung Park, Francesco Silvestri, Rasmus Pagh, Chin-Wan Chung, Sung-Hyon Myaeng, U Kang. Enumerating Trillion Subgraphs On Distributed Systems. ACM Trans. Knowl. Discov. Data, 2018
• Michael Mitzenmacher, Rasmus Pagh. Simple multi-party set reconciliation. Distributed Comput., 2018
• Ioana Oriana Bercea. Improved Bounds for the Traveling Salesman Problem with Neighborhoods on Uniform Disks. CCCG, 2018
• Stephan Lorenzen, Niklas Hjuler, Stephen Alstrup. Tracking Behavioral Patterns among Students in an Online Educational System. EDM, 2018
• David L. Applegate, Aaron Archer, David S. Johnson, Evdokia Nikolova, Mikkel Thorup, Ger Yang. Wireless coverage prediction via parametric shortest paths. MobiHoc, 2018
• Anders Aamand, Mathias Bæk Tejs Knudsen, Mikkel Thorup. Power of d Choices with Simple Tabulation. ICALP, 2018
• Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto. Counting Connected Subgraphs with Maximum-Degree-Aware Sieving. ISAAC, 2018
• Martin Aumüller, Tobias Christiani, Rasmus Pagh, Francesco Silvestri. Distance-Sensitive Hashing. PODS, 2018
• Mikkel Thorup. Sample(x)=(a*x<=t) Is a Distinguisher with Probability 1/8. SIAM J. Comput., 2018
• Marcin Pilipczuk, Michal Pilipczuk. Planar Digraphs. Classes of Directed Graphs, 2018
• Shaohua Li, Marcin Pilipczuk. An Improved FPT Algorithm for Independent Feedback Vertex Set. WG, 2018
• Daniel Lokshtanov, Marcin Pilipczuk, Erik Jan van Leeuwen. Independence and Efficient Domination on P₆-free Graphs. ACM Trans. Algorithms, 2018
• Marcin Pilipczuk, Michal Pilipczuk, Piotr Sankowski, Erik Jan van Leeuwen. Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs. ACM Trans. Algorithms, 2018
• Andreas Björklund, Thore Husfeldt. Counting Shortest Two Disjoint Paths in Cubic Planar Graphs with an NC Algorithm. ISAAC, 2018
• Karl Bringmann, Thore Husfeldt, Måns Magnusson. Multivariate Analysis of Orthogonal Range Searching and Graph Distances. IPEC, 2018
• Radu Curticapean. Counting Problems in Parameterized Complexity. IPEC, 2018
• Samuel McCauley, Jesper W. Mikkelsen, Rasmus Pagh. Set Similarity Search for Skewed Data. PODS, 2018
• Shiri Chechik, Christian Wulff-Nilsen. Near-Optimal Light Spanners. ACM Trans. Algorithms, 2018
• Gramoz Goranci, Monika Henzinger, Mikkel Thorup. Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time. ACM Trans. Algorithms, 2018
• Krzysztof Kiljan, Marcin Pilipczuk. Experimental Evaluation of Parameterized Algorithms for Feedback Vertex Set. SEA, 2018
• Michal Ziobro, Marcin Pilipczuk. Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation. SEA, 2018
• Emilio Cruciani, Emanuele Natale, André Nusser, Giacomo Scornavacca. Phase Transition of the 2-Choices Dynamics on Core-Periphery Networks. AAMAS, 2018
• Glencora Borradaile, Hung Le, Christian Wulff-Nilsen. Minor-Free Graphs Have Light Spanners. FOCS, 2017
• Vincent Cohen-Addad, Søren Dahlgaard, Christian Wulff-Nilsen. Fast and Compact Exact Distance Oracle for Planar Graphs. FOCS, 2017
• Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Mikkel Thorup. Fast Similarity Sketching. FOCS, 2017
• Danupon Nanongkai, Thatchaphol Saranurak, Christian Wulff-Nilsen. Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time. FOCS, 2017
• Nikolai Karpov, Marcin Pilipczuk, Anna Zych-Pawlewicz. An Exponential Lower Bound for Cut Sparsifiers in Planar Graphs. IPEC, 2017
• Radu Curticapean, Holger Dell, Dániel Marx. Homomorphisms are a good basis for counting small subgraphs. STOC, 2017
• Mikkel Abrahamsen, Anna Adamaszek, Tillmann Miltzow. Irrational Guards are Sometimes Needed. SoCG, 2017
• Mikkel Abrahamsen, Mark de Berg, Kevin Buchin, Mehran Mehr, Ali D. Mehrabi. Minimum Perimeter-Sum Partitions in the Plane. SoCG, 2017
• Mikkel Abrahamsen, Mark de Berg, Kevin Buchin, Mehran Mehr, Ali D. Mehrabi. Range-Clustering Queries. SoCG, 2017
• Mikkel Abrahamsen, Jacob Holm, Eva Rotenberg, Christian Wulff-Nilsen. Best Laid Plans of Lions and Men. SoCG, 2017
• Mikkel Abrahamsen, Stephen Alstrup, Jacob Holm, Mathias Bæk Tejs Knudsen, Morten Stöckel. Near-Optimal Induced Universal Graphs for Bounded Degree Graphs. ICALP, 2017
• Bart M. P. Jansen, Marcin Pilipczuk, Marcin Wrochna. Turing Kernelization for Finding Long Paths in Graphs Excluding a Topological Minor. IPEC, 2017
• Mathias Johanson, Jonas Jalminger, Emmanuel Frécon, Boel Nelson, Tomas Olovsson, Mats Gjertz. Joint Subjective and Objective Data Capture and Analytics for Automotive Applications. VTC Fall, 2017
• Boel Nelson, Tomas Olovsson. Introducing Differential Privacy to the Automotive Domain: Opportunities and Challenges. VTC Fall, 2017
• Guillaume Lagarde, Nutan Limaye, Srikanth Srinivasan. Lower Bounds and PIT for Non-Commutative Arithmetic Circuits with Restricted Parse Trees. MFCS, 2017
• Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan. An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas. SIAM J. Comput., 2017
• Hervé Fournier, Nutan Limaye, Meena Mahajan, Srikanth Srinivasan. The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials. Theory Comput., 2017
• Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk. Hitting forbidden subgraphs in graphs of bounded treewidth. Inf. Comput., 2017
• Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Erik Jan van Leeuwen, Marcin Wrochna. Polynomial Kernelization for Removing Induced Claws and Diamonds. Theory Comput. Syst., 2017
• Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz, Jakub Lacki, Eva Rotenberg, Piotr Sankowski. Contracting a Planar Graph Efficiently. ESA, 2017
• Stefan Funke, André Nusser, Sabine Storandt. The Simultaneous Maze Solving Problem. AAAI, 2017
• Thomas D. Ahle, Martin Aumüller, Rasmus Pagh. Parameter-free Locality Sensitive Hashing for Spherical Range Reporting. SODA, 2017
• Mayank Goswami, Rasmus Pagh, Francesco Silvestri, Johan Sivertsen. Distance Sensitive Bloom Filters Without False Negatives. SODA, 2017
• Bart M. P. Jansen, Marcin Pilipczuk. Approximation and Kernelization for Chordal Vertex Deletion. SODA, 2017
• Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Mikkel Thorup. Practical Hash Functions for Similarity Estimation and Dimensionality Reduction. NIPS, 2017
• Anna Adamaszek, Tomasz Kociumaka, Marcin Pilipczuk, Michal Pilipczuk. Hardness of Approximation for Strip Packing. ACM Trans. Comput. Theory, 2017
• Christian Hansen, Casper Hansen, Niklas Hjuler, Stephen Alstrup, Christina Lioma. Sequence Modelling For Analysing Student Interaction with Educational Systems. EDM, 2017
• Marcin Pilipczuk. A tight lower bound for Vertex Planarization on graphs of bounded treewidth. Discret. Appl. Math., 2017
• Ivona Bezáková, Radu Curticapean, Holger Dell, Fedor V. Fomin. Finding Detours is Fixed-Parameter Tractable. ICALP, 2017
• Joachim Gudmundsson, Rasmus Pagh. Range-Efficient Consistent Sampling and Locality-Sensitive Hashing for Polygons. ISAAC, 2017
• Radu Curticapean, Holger Dell, Fedor V. Fomin, Leslie Ann Goldberg, John Lapinskas. A Fixed-Parameter Perspective on #BIS. IPEC, 2017
• Rasmus Pagh, Ninh Pham, Francesco Silvestri, Morten Stöckel. I/O-Efficient Similarity Join. Algorithmica, 2017
• Rasmus Pagh, Francesco Silvestri, Johan Sivertsen, Matthew Skala. Approximate furthest neighbor with application to annulus query. Inf. Syst., 2017
• Radu Curticapean, Holger Dell, Marc Roth. Counting Edge-Injective Homomorphisms and Matchings on Restricted Graph Classes. STACS, 2017
• Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh. Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth. SIAM J. Comput., 2017
• Casper Hansen, Christian Hansen, Stephen Alstrup, Christina Lioma. Smart City Analytics: Ensemble-Learned Prediction of Citizen Home Care. CIKM, 2017
• Leszek Gasieniec, Christos Levcopoulos, Andrzej Lingas, Rasmus Pagh, Takeshi Tokuyama. Efficiently Correcting Matrix Products. Algorithmica, 2017
• Jacob Holm, Eva Rotenberg. Dynamic Planar Embeddings of Dynamic Graphs. Theory Comput. Syst., 2017
• Mikkel Thorup. Fast and Powerful Hashing Using Tabulation (Invited Talk). ICALP, 2017
• Glencora Borradaile, Philip N. Klein, Shay Mozes, Yahav Nussbaum, Christian Wulff-Nilsen. Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time. SIAM J. Comput., 2017
• Mikkel Thorup. Fast and Powerful Hashing using Tabulation. FOGA, 2017
• Tobias Christiani, Rasmus Pagh. Set similarity search beyond MinHash. STOC, 2017
• Christian Wulff-Nilsen. Fully-dynamic minimum spanning forest with improved worst-case update time. STOC, 2017
• Mikkel Thorup. Fast and powerful hashing using tabulation. Commun. ACM, 2017
• Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen. Optimal Induced Universal Graphs and Adjacency Labeling for Trees. J. ACM, 2017
• Ken-ichi Kawarabayashi, Mikkel Thorup. Coloring 3-Colorable Graphs with Less than n^1/5 Colors. J. ACM, 2017
• Alexandr Andoni, Debmalya Panigrahi, Marcin Pilipczuk. Editorial. ACM Trans. Algorithms, 2017
• Dániel Marx, Marcin Pilipczuk. Subexponential Parameterized Algorithms for Graphs of Polynomial Growth. ESA, 2017
• Andreas Krebs, Nutan Limaye, Michael Ludwig. A Unified Method for Placing Problems in Polylogarithmic Depth. FSTTCS, 2017
• Rasmus Pagh. Hardness and Approximation of High-Dimensional Search Problems (Invited Talk). MFCS, 2017
• Pooja Vyavahare, Nutan Limaye, Ajit A. Diwan, D. Manjunath. On the Maximum Rate of Networked Computation in a Capacitated Network. IEEE/ACM Trans. Netw., 2017
• Thore Husfeldt, Iyad A. Kanj. Guest Editorial: Special Issue on Parameterized and Exact Computation. Algorithmica, 2017
• Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto. Narrow sieves for parameterized paths and packings. J. Comput. Syst. Sci., 2017
• Andreas Björklund, Thore Husfeldt, Isak Lyckberg. Computing the permanent modulo a prime power. Inf. Process. Lett., 2017
• Daniel Bahrdt, Michael Becher, Stefan Funke, Filip Krumpe, André Nusser, Martin Seybold, Sabine Storandt. Growing Balls in ℝ^d. ALENEX, 2017

Data from DBLP. Last updated 2023-05-26.