Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
From MaRDI portal
Publication:4571929
DOI10.1137/15M1050987zbMath1396.68052OpenAlexW2809864751WikidataQ122999560 ScholiaQ122999560MaRDI QIDQ4571929
Amir Abboud, Huacheng Yu, Virginia Vassilevska Williams
Publication date: 4 July 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/15m1050987
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Flows in graphs (05C21)
Related Items
Geometric pattern matching reduces to \(k\)-SUM, Finding the largest triangle in a graph in expected quadratic time, Fine-Grained Complexity of Regular Path Queries, How fast can we play Tetris greedily with rectangular pieces?, The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance, Geometric Pattern Matching Reduces to k-SUM., Unnamed Item, Parameterized aspects of triangle enumeration, Unnamed Item, Percolation centrality via Rademacher Complexity, Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 3SUM, 3XOR, triangles
- On a class of \(O(n^2)\) problems in computational geometry
- Necklaces, convolutions, and \(X+Y\)
- Perfect binary space partitions
- On the complexity of fixed parameter clique and dominating set
- Into the square: on the complexity of some quadratic-time solvable problems
- A new polynomial-time algorithm for linear programming
- Finding paths and deleting edges in directed acyclic graphs
- Preprocessing chains for fast dihedral rotations is hard or even impossible.
- Dynamically switching vertices in planar graphs
- Which problems have strongly exponential complexity?
- On a class of \(O(n^ 2)\) problems in computational geometry
- An interior-point method for generalized linear-fractional programming
- Finding a guard that sees most and a shop that sells most
- Subquadratic algorithms for 3SUM
- Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility
- Graph Connectivities, Network Coding, and Expander Graphs
- Finding, Minimizing, and Counting Weighted Subgraphs
- Towards polynomial lower bounds for dynamic problems
- Losing Weight by Gaining Edges
- Improved Deterministic Algorithms for Decremental Reachability and Strongly Connected Components
- Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
- Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance
- Near-optimal fully-dynamic graph connectivity
- Dynamic Subgraph Connectivity with Geometric Applications
- Local Reductions
- Powers of tensors and fast matrix multiplication
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- Improved Dynamic Reachability Algorithms for Directed Graphs
- An improved exponential-time algorithm for k -SAT
- An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
- New Data Structures for Subgraph Connectivity
- On Approximating the Depth and Related Problems
- Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard
- The Complexity of Satisfiability of Small Depth Circuits
- An On-Line Edge-Deletion Problem
- New Lower Bounds for Convex Hull Problems in Odd Dimensions
- A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
- Fast Hamiltonicity Checking Via Bases of Perfect Matchings
- Threesomes, Degenerates, and Love Triangles
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Higher Lower Bounds from the 3SUM Conjecture
- On the Hardness of Partially Dynamic Graph Problems and Connections to Diameter
- POLYGON CONTAINMENT AND TRANSLATIONAL IN-HAUSDORFF-DISTANCE BETWEEN SEGMENT SETS ARE 3SUM-HARD
- On Moderately Exponential Time for SAT
- A New Approach to Incremental Cycle Detection and Related Problems
- Consequences of Faster Alignment of Sequences
- On Hardness of Jumbled Indexing
- Listing Triangles
- Faster all-pairs shortest paths via circuit complexity
- Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
- Exact Weight Subgraphs and the k-Sum Conjecture
- Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
- More Applications of the Polynomial Method to Algorithm Design
- Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
- An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
- Finding orthogonal vectors in discrete structures
- Multiplying matrices faster than coppersmith-winograd
- Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
- Algorithms – ESA 2004
- Automata, Languages and Programming
- Logarithmic Lower Bounds in the Cell-Probe Model
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Decremental maintenance of strongly connected components
- On the complexity of \(k\)-SAT
