Matching Triangles and Basing Hardness on an Extremely Popular Conjecture (Q4571929): Difference between revisions

@@ Property / author @@
-Virginia Vassilevska Williams
@@ Property / author: Virginia Vassilevska Williams / rank @@
-Normal rank
@@ Property / author @@
+Virginia Vassilevska Williams
@@ Property / author: Virginia Vassilevska Williams / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
+Normal rank
@@ Property / cites work @@
+Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
+Normal rank
@@ Property / cites work @@
+Exact Weight Subgraphs and the k-Sum Conjecture
@@ Property / cites work: Exact Weight Subgraphs and the k-Sum Conjecture / rank @@
+Normal rank
@@ Property / cites work @@
+Losing Weight by Gaining Edges
@@ Property / cites work: Losing Weight by Gaining Edges / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
+Normal rank
@@ Property / cites work @@
+Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
+Normal rank
@@ Property / cites work @@
+More Applications of the Polynomial Method to Algorithm Design
+Normal rank
@@ Property / cites work @@
+Consequences of Faster Alignment of Sequences
@@ Property / cites work: Consequences of Faster Alignment of Sequences / rank @@
+Normal rank
@@ Property / cites work @@
+On Hardness of Jumbled Indexing
@@ Property / cites work: On Hardness of Jumbled Indexing / rank @@
+Normal rank
@@ Property / cites work @@
+On Approximating the Depth and Related Problems
@@ Property / cites work: On Approximating the Depth and Related Problems / rank @@
+Normal rank
@@ Property / cites work @@
+Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
+Normal rank
@@ Property / cites work @@
+Subquadratic algorithms for 3SUM
@@ Property / cites work: Subquadratic algorithms for 3SUM / rank @@
+Normal rank
@@ Property / cites work @@
+POLYGON CONTAINMENT AND TRANSLATIONAL IN-HAUSDORFF-DISTANCE BETWEEN SEGMENT SETS ARE 3SUM-HARD
+Normal rank
@@ Property / cites work @@
+A New Approach to Incremental Cycle Detection and Related Problems
+Normal rank
@@ Property / cites work @@
+Listing Triangles
@@ Property / cites work: Listing Triangles / rank @@
+Normal rank
@@ Property / cites work @@
+Into the square: on the complexity of some quadratic-time solvable problems
+Normal rank
@@ Property / cites work @@
+Necklaces, convolutions, and \(X+Y\)
@@ Property / cites work: Necklaces, convolutions, and \(X+Y\) / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of Satisfiability of Small Depth Circuits
+Normal rank
@@ Property / cites work @@
+Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility
+Normal rank
@@ Property / cites work @@
+Dynamic Subgraph Connectivity with Geometric Applications
+Normal rank
@@ Property / cites work @@
+Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard
+Normal rank
@@ Property / cites work @@
+Finding a guard that sees most and a shop that sells most
+Normal rank
@@ Property / cites work @@
+Graph Connectivities, Network Coding, and Expander Graphs
+Normal rank
@@ Property / cites work @@
+Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
+Normal rank
@@ Property / cites work @@
+Fast Hamiltonicity Checking Via Bases of Perfect Matchings
+Normal rank
@@ Property / cites work @@
+On the Hardness of Partially Dynamic Graph Problems and Connections to Diameter
+Normal rank
@@ Property / cites work @@
+On Moderately Exponential Time for SAT
@@ Property / cites work: On Moderately Exponential Time for SAT / rank @@
+Normal rank
@@ Property / cites work @@
+Perfect binary space partitions
@@ Property / cites work: Perfect binary space partitions / rank @@
+Normal rank
@@ Property / cites work @@
+New Data Structures for Subgraph Connectivity
@@ Property / cites work: New Data Structures for Subgraph Connectivity / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of fixed parameter clique and dominating set
+Normal rank
@@ Property / cites work @@
+New Lower Bounds for Convex Hull Problems in Odd Dimensions
+Normal rank
@@ Property / cites work @@
+An On-Line Edge-Deletion Problem
@@ Property / cites work: An On-Line Edge-Deletion Problem / rank @@
+Normal rank
@@ Property / cites work @@
+Dynamically switching vertices in planar graphs
@@ Property / cites work: Dynamically switching vertices in planar graphs / rank @@
+Normal rank
@@ Property / cites work @@
+On a class of \(O(n^ 2)\) problems in computational geometry
+Normal rank
@@ Property / cites work @@
+On a class of \(O(n^2)\) problems in computational geometry
+Normal rank
@@ Property / cites work @@
+Powers of tensors and fast matrix multiplication
@@ Property / cites work: Powers of tensors and fast matrix multiplication / rank @@
+Normal rank
@@ Property / cites work @@
+Threesomes, Degenerates, and Love Triangles
@@ Property / cites work: Threesomes, Degenerates, and Love Triangles / rank @@
+Normal rank
@@ Property / cites work @@
+Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance
+Normal rank
@@ Property / cites work @@
+A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
+Normal rank
@@ Property / cites work @@
+An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs
+Normal rank
@@ Property / cites work @@
+Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
+Normal rank
@@ Property / cites work @@
+Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
+Normal rank
@@ Property / cites work @@
+Q4250220
@@ Property / cites work: Q4250220 / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of \(k\)-SAT
@@ Property / cites work: On the complexity of \(k\)-SAT / rank @@
+Normal rank
@@ Property / cites work @@
+Which problems have strongly exponential complexity?
+Normal rank
@@ Property / cites work @@
+Finding paths and deleting edges in directed acyclic graphs
+Normal rank
@@ Property / cites work @@
+SUM, 3XOR, triangles
@@ Property / cites work: 3SUM, 3XOR, triangles / rank @@
+Normal rank
@@ Property / cites work @@
+Local Reductions
@@ Property / cites work: Local Reductions / rank @@
+Normal rank
@@ Property / cites work @@
+A new polynomial-time algorithm for linear programming
+Normal rank
@@ Property / cites work @@
+An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
+Normal rank
@@ Property / cites work @@
+Higher Lower Bounds from the 3SUM Conjecture
@@ Property / cites work: Higher Lower Bounds from the 3SUM Conjecture / rank @@
+Normal rank
@@ Property / cites work @@
+Improved Deterministic Algorithms for Decremental Reachability and Strongly Connected Components
+Normal rank
@@ Property / cites work @@
+Q5365080
@@ Property / cites work: Q5365080 / rank @@
+Normal rank
@@ Property / cites work @@
+Preprocessing chains for fast dihedral rotations is hard or even impossible.
+Normal rank
@@ Property / cites work @@
+An interior-point method for generalized linear-fractional programming
+Normal rank
@@ Property / cites work @@
+Q5417690
@@ Property / cites work: Q5417690 / rank @@
+Normal rank
@@ Property / cites work @@
+An improved exponential-time algorithm for             <i>k</i>             -SAT
+Normal rank
@@ Property / cites work @@
+Towards polynomial lower bounds for dynamic problems
+Normal rank
@@ Property / cites work @@
+Logarithmic Lower Bounds in the Cell-Probe Model
@@ Property / cites work: Logarithmic Lower Bounds in the Cell-Probe Model / rank @@
+Normal rank
@@ Property / cites work @@
+Decremental maintenance of strongly connected components
+Normal rank
@@ Property / cites work @@
+Fast approximation algorithms for the diameter and radius of sparse graphs
+Normal rank
@@ Property / cites work @@
+Improved Dynamic Reachability Algorithms for Directed Graphs
+Normal rank
@@ Property / cites work @@
+Algorithms – ESA 2004
@@ Property / cites work: Algorithms – ESA 2004 / rank @@
+Normal rank
@@ Property / cites work @@
+Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
+Normal rank
@@ Property / cites work @@
+Near-optimal fully-dynamic graph connectivity
@@ Property / cites work: Near-optimal fully-dynamic graph connectivity / rank @@
+Normal rank
@@ Property / cites work @@
+Finding, Minimizing, and Counting Weighted Subgraphs
+Normal rank
@@ Property / cites work @@
+Automata, Languages and Programming
@@ Property / cites work: Automata, Languages and Programming / rank @@
+Normal rank
@@ Property / cites work @@
+Faster all-pairs shortest paths via circuit complexity
+Normal rank
@@ Property / cites work @@
+Finding orthogonal vectors in discrete structures
@@ Property / cites work: Finding orthogonal vectors in discrete structures / rank @@
+Normal rank
@@ Property / cites work @@
+Multiplying matrices faster than coppersmith-winograd
+Normal rank
@@ Property / cites work @@
+All pairs shortest paths using bridging sets and rectangular matrix multiplication
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1137/15m1050987
+Normal rank
@@ Property / OpenAlex ID @@
+W2809864751
@@ Property / OpenAlex ID: W2809864751 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:4571929