Virginia Vassilevska Williams

Discret. Appl. Math., October, 2023

Isometric Hamming embeddings of weighted graphs.

[BibT_eX]

[DOI]

Joseph Berleant

Kristin Sheridan

Anne Condon

Mark Bathe

Discret. Appl. Math., June, 2023

Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, January, 2023

Listing Cliques from Smaller Cliques.

[BibT_eX]

[DOI]

Surya Mathialagan

CoRR, 2023

Fast 2-Approximate All-Pairs Shortest Paths.

[BibT_eX]

[DOI]

Tijn de Vos

CoRR, 2023

New Bounds for Matrix Multiplication: from Alpha to Omega.

[BibT_eX]

[DOI]

Zixuan Xu

Renfei Zhou

CoRR, 2023

Quasipolynomiality of the Smallest Missing Induced Subgraph.

[BibT_eX]

[DOI]

David Eppstein

CoRR, 2023

Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More.

[BibT_eX]

[DOI]

Timothy M. Chan

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Improved girth approximation in weighted undirected graphs.

[BibT_eX]

[DOI]

Avi Kadria

Aaron Sidford

Uri Zwick

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Approximating Min-Diameter: Standard and Bichromatic.

[BibT_eX]

[DOI]

Aaron Berger

Jenny Kaufmann

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

Faster Detours in Undirected Graphs.

[BibT_eX]

[DOI]

Shyan Akmal

Zixuan Xu

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

On Diameter Approximation in Directed Graphs.

[BibT_eX]

[DOI]

Ray Li

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022

Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failures.

[BibT_eX]

[DOI]

Eyob Woldeghebriel

CoRR, 2022

Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OV.

[BibT_eX]

[DOI]

Timothy M. Chan

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation Product.

[BibT_eX]

[DOI]

Kevin Lu

Zixuan Xu

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Algorithmic trade-offs for girth approximation in undirected graphs.

[BibT_eX]

[DOI]

Avi Kadria

Aaron Sidford

Uri Zwick

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

New Lower Bounds and Upper Bounds for Listing Avoidable Vertices.

[BibT_eX]

[DOI]

Mingyang Deng

Ziqian Zhong

Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, 2022

Dynamic Matching Algorithms Under Vertex Updates.

[BibT_eX]

[DOI]

Hung Le

Lazar Milenkovic

Shay Solomon

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules.

[BibT_eX]

[DOI]

Krzysztof Sornat

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, 2022

Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds.

[BibT_eX]

[DOI]

Surya Mathialagan

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

New Additive Approximations for Shortest Paths and Cycles.

[BibT_eX]

[DOI]

Mingyang Deng

Yael Kirkpatrick

Victor Rong

Ziqian Zhong

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failure.

[BibT_eX]

[DOI]

Eyob Woldeghebriel

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Induced Cycles and Paths Are Harder Than You Think.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles.

[BibT_eX]

[DOI]

Ce Jin

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Hardness of Token Swapping on Trees.

[BibT_eX]

[DOI]

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

2021

Better Distance Preservers and Additive Spanners.

[BibT_eX]

[DOI]

Greg Bodwin

ACM Trans. Algorithms, 2021

Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles.

[BibT_eX]

[DOI]

Thuy-Duong Vuong

SIAM J. Comput., 2021

Toward Tight Approximation Bounds for Graph Diameter and Eccentricities.

[BibT_eX]

[DOI]

Gilad Segal

SIAM J. Comput., 2021

EATCS-IPEC Nerode Prize - Call for Nominations.

[BibT_eX]

[DOI]

Maximilian Probst Gutenberg

Bull. EATCS, 2021

New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners.

[BibT_eX]

[DOI]

Thiago Bergamaschi

Monika Henzinger

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

A Refined Laser Method and Faster Matrix Multiplication.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Fine-Grained Complexity and Algorithms for the Schulze Voting Method.

[BibT_eX]

[DOI]

Krzysztof Sornat

Proceedings of the EC '21: The 22nd ACM Conference on Economics and Computation, 2021

Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths.

[BibT_eX]

[DOI]

Yuzhou Gu

Adam Polak

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths.

[BibT_eX]

[DOI]

Timothy M. Chan

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Improved Approximation for Longest Common Subsequence over Small Alphabets.

[BibT_eX]

[DOI]

Shyan Akmal

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Fine-Grained Hardness for Edit Distance to a Fixed Sequence.

[BibT_eX]

[DOI]

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Hardness of Approximate Diameter: Now for Undirected Graphs.

[BibT_eX]

[DOI]

Ray Li

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

3SUM and Related Problems in Fine-Grained Complexity (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 37th International Symposium on Computational Geometry, 2021

2020

Dynamic Parameterized Problems and Algorithms.

[BibT_eX]

[DOI]

Matthias Mnich

ACM Trans. Algorithms, 2020

Faster Replacement Paths and Distance Sensitivity Oracles.

[BibT_eX]

[DOI]

Maximilian Probst Gutenberg

ACM Trans. Algorithms, 2020

New algorithms and hardness for incremental single-source shortest paths in directed graphs.

[BibT_eX]

[DOI]

Proceedings of the Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Equivalences between triangle and range query problems.

[BibT_eX]

[DOI]

Lech Duraj

Krzysztof Kleiner

Adam Polak

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Distributed Distance Approximation.

[BibT_eX]

[DOI]

Proceedings of the 24th International Conference on Principles of Distributed Systems, 2020

Monochromatic Triangles, Intermediate Matrix Products, and Convolutions.

[BibT_eX]

[DOI]

Adam Polak

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

OV Graphs Are (Probably) Hard Instances.

[BibT_eX]

[DOI]

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Towards Optimal Set-Disjointness and Set-Intersection Data Structures.

[BibT_eX]

[DOI]

Tsvi Kopelowitz

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Conditionally Optimal Approximation Algorithms for the Girth of a Directed Graph.

[BibT_eX]

[DOI]

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Monochromatic Triangles, Triangle Listing and APSP.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

New Techniques for Proving Fine-Grained Average-Case Hardness.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Introduction to the Special Issue on SODA 2017.

[BibT_eX]

[DOI]

Dániel Marx

Neal E. Young

ACM Trans. Algorithms, 2019

SETH vs Approximation.

[BibT_eX]

[DOI]

Aviad Rubinstein

SIGACT News, 2019

Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product.

[BibT_eX]

[DOI]

Karl Bringmann

Barna Saha

SIAM J. Comput., 2019

Public-Key Cryptography in the Fine-Grained Setting.

[BibT_eX]

[DOI]

Rio LaVigne

IACR Cryptol. ePrint Arch., 2019

EATCS-IPEC Nerode Prize 2019 - Call for Nominations.

[BibT_eX]

[DOI]

Jianer Chen

Hans L. Bodlaender

Bull. EATCS, 2019

Graph pattern detection: hardness for all induced patterns and faster non-induced cycles.

[BibT_eX]

[DOI]

Thuy-Duong Vuong

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication.

[BibT_eX]

[DOI]

Proceedings of the 2019 on International Symposium on Symbolic and Algebraic Computation, 2019

Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems.

[BibT_eX]

[DOI]

Nikhil Vyas

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Approximation Algorithms for Min-Distance Problems.

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Algorithms and Hardness for Diameter in Dynamic Graphs.

[BibT_eX]

[DOI]

Bertie Ancona

Monika Henzinger

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Bribery in Balanced Knockout Tournaments.

[BibT_eX]

[DOI]

Christine Konicki

Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, 2019

2018

Subtree Isomorphism Revisited.

[BibT_eX]

[DOI]

Thomas Dueholm Hansen

Or Zamir

ACM Trans. Algorithms, 2018

Some Open Problems in Fine-Grained Complexity.

[BibT_eX]

[DOI]

SIGACT News, 2018

Matching Triangles and Basing Hardness on an Extremely Popular Conjecture.

[BibT_eX]

[DOI]

Huacheng Yu

SIAM J. Comput., 2018

If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser.

[BibT_eX]

[DOI]

SIAM J. Comput., 2018

Subcubic Equivalences Between Path, Matrix, and Triangle Problems.

[BibT_eX]

[DOI]

J. ACM, 2018

Nearly Optimal Separation Between Partially and Fully Retroactive Data Structures.

[BibT_eX]

[DOI]

Lijie Chen

Erik D. Demaine

Yuzhou Gu

Yuancheng Yu

Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, 2018

Towards tight approximation bounds for graph diameter and eccentricities.

[BibT_eX]

[DOI]

Gilad Segal

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Approximating Cycles in Directed Graphs: Fast Algorithms for Girth and Roundtrip Spanners.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Tight Hardness for Shortest Cycles and Paths in Sparse Graphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Optimal Vertex Fault Tolerant Spanners (for fixed stretch).

[BibT_eX]

[DOI]

Greg Bodwin

Michael Dinitz

Merav Parter

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Fine-grained I/O Complexity via Reductions: New Lower Bounds, Faster Algorithms, and a Time Hierarchy.

[BibT_eX]

[DOI]

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Further Limitations of the Known Approaches for Matrix Multiplication.

[BibT_eX]

[DOI]

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Fine-grained Algorithms and Complexity.

[BibT_eX]

[DOI]

Proceedings of the 21st International Conference on Database Theory, 2018

Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication.

[BibT_eX]

[DOI]

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

Who Can Win a Single-Elimination Tournament?

[BibT_eX]

[DOI]

Michael P. Kim

Warut Suksompong

SIAM J. Discret. Math., 2017

Metatheorems for Dynamic Weighted Matching.

[BibT_eX]

[DOI]

Daniel Stubbs

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Conditional Hardness for Sensitivity Problems.

[BibT_eX]

[DOI]

Monika Henzinger

Stefan Neumann

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Preserving Distances in Very Faulty Graphs.

[BibT_eX]

[DOI]

Greg Bodwin

Merav Parter

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Parameterized Complexity of Group Activity Selection.

[BibT_eX]

[DOI]

Hooyeon Lee

Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, 2017

Complexity of the Stable Invitations Problem.

[BibT_eX]

[DOI]

Hooyeon Lee

Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, 2017

2016

Knockout Tournaments.

[BibT_eX]

[DOI]

Proceedings of the Handbook of Computational Social Choice, 2016

Special Section on the Fifty-Fourth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013).

[BibT_eX]

[DOI]

Moritz Hardt

Yuval Ishai

Raghu Meka

SIAM J. Comput., 2016

Structure and Hardness in P (Dagstuhl Seminar 16451).

[BibT_eX]

[DOI]

Moshe Lewenstein

Seth Pettie

Dagstuhl Reports, 2016

Deterministic Time-Space Tradeoffs for k-SUM.

[BibT_eX]

[DOI]

CoRR, 2016

Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made.

[BibT_eX]

[DOI]

Thomas Dueholm Hansen

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Fine-Grained Algorithms and Complexity (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

RNA-Folding - From Hardness to Algorithms.

[BibT_eX]

[DOI]

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

Deterministic Time-Space Trade-Offs for k-SUM.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product.

[BibT_eX]

[DOI]

Karl Bringmann

Barna Saha

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

A 7/3-Approximation for Feedback Vertex Sets in Tournaments.

[BibT_eX]

[DOI]

Matthias Mnich

László A. Végh

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

2015

Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter.

[BibT_eX]

[DOI]

CoRR, 2015

Quadratic-Time Hardness of LCS and other Sequence Similarity Measures.

[BibT_eX]

[DOI]

CoRR, 2015

Finding Four-Node Subgraphs in Triangle Time.

[BibT_eX]

[DOI]

Richard Ryan Williams

Huacheng Yu

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 10th International Symposium on Parameterized and Exact Computation, 2015

Very Sparse Additive Spanners and Emulators.

[BibT_eX]

[DOI]

Gregory Bodwin

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

Fixing Tournaments for Kings, Chokers, and More.

[BibT_eX]

[DOI]

Michael P. Kim

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015

Tight Hardness Results for LCS and Other Sequence Similarity Measures.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

Quantum algorithms for shortest paths problems in structured instances.

[BibT_eX]

[DOI]

Aran Nayebi

CoRR, 2014

Better Approximation Algorithms for the Graph Diameter.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Listing Triangles.

[BibT_eX]

[DOI]

Andreas Björklund

Rasmus Pagh

Uri Zwick

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Consequences of Faster Alignment of Sequences.

[BibT_eX]

[DOI]

Oren Weimann

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems.

[BibT_eX]

[DOI]

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

Finding, Minimizing, and Counting Weighted Subgraphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 2013

Fast approximation algorithms for the diameter and radius of sparse graphs.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing Conference, 2013

2012

Approximating the diameter of a graph

[BibT_eX]

[DOI]

CoRR, 2012

Multiplying matrices faster than coppersmith-winograd.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Subquadratic time approximation algorithms for the girth.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Improved Distance Sensitivity Oracles via Fast Single-Source Replacement Paths.

[BibT_eX]

[DOI]

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011

Manipulating Stochastically Generated Single-Elimination Tournaments for Nearly All Players.

[BibT_eX]

[DOI]

Isabelle Stanton

Proceedings of the Internet and Network Economics - 7th International Workshop, 2011

Faster Replacement Paths.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Rigging Tournament Brackets for Weaker Players.

[BibT_eX]

[DOI]

Isabelle Stanton

Proceedings of the IJCAI 2011, 2011

Minimum Weight Cycles and Triangles: Equivalences and Algorithms.

[BibT_eX]

[DOI]

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

Nondecreasing paths in a weighted graph or: How to optimally read a train schedule.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2010

Finding heaviest H-subgraphs in real weighted graphs, with applications.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2010

Fixing a Tournament.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, 2010

2009

All Pairs Bottleneck Paths and Max-Min Matrix Products in Truly Subcubic Time.

[BibT_eX]

[DOI]

Theory Comput., 2009

Efficient algorithms for clique problems.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2009

2008

Uniquely Represented Data Structures for Computational Geometry.

[BibT_eX]

[DOI]

Guy E. Blelloch

Daniel Golovin

Proceedings of the Algorithm Theory, 2008

A New Combinatorial Approach for Sparse Graph Problems.

[BibT_eX]

[DOI]

Guy E. Blelloch

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

2007

All-pairs bottleneck paths for general graphs in truly sub-cubic time.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

2006

Finding heaviest H-subgraphs in real weighted graphs, with applications

[BibT_eX]

[DOI]

CoRR, 2006

Finding a maximum weight triangle in n3-Delta time, with applications.

[BibT_eX]

[DOI]

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Confronting hardness using a hybrid approach.

[BibT_eX]

[DOI]

Shan Leung Maverick Woo

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2005

Explicit Inapproximability Bounds for the Shortest Superstring Problem.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

2004

Consumer electronics industry standards for in-home entertainment networking and device connectivity.

[BibT_eX]

[DOI]