Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics

2024-9-13

Resolving Matrix Spencer Conjecture up to Poly-Logarithmic Rank

2024-9-12

Complexity Classification Transfer for CSPs via Algebraic Products

2024-9-12

Traversing Combinatorial 0/1-Polytopes via Optimization

2024-9-9

Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence

2024-9-9

Removing Additive Structure in 3SUM-Based Reductions

2024-9-5

Algorithms and Certificates for Boolean CSP Refutation: Smoothed Is No Harder than Random

2024-9-5

Online Primal Dual Meets Online Matching with Stochastic Rewards: Configuration LP to the Rescue

2024-9-4

Fast Generalized DFTs for All Finite Groups

2024-9-4

The Power of Two Choices in Graphical Allocation

2024-8-26

PTAS for Minimum Cost MultiCovering with Disks

2024-8-22

Approximate Gomory–Hu Tree is Faster than \(\boldsymbol{n}\,\boldsymbol{-\, 1}\) Maximum Flows

2024-8-20

Algorithms for Subpath Convex Hull Queries and Ray-Shooting among Segments

2024-8-13

Fast FPT-Approximation of Branchwidth

2024-8-8

Revisionist Simulations: A New Approach to Proving Space Lower Bounds

2024-8-1

Economical Convex Coverings and Applications

2024-7-31

Approximating Maximum Independent Set for Rectangles in the Plane

2024-7-23

On the Privacy of Noisy Stochastic Gradient Descent for Convex Optimization

2024-7-19

Circuits Resilient to Short-Circuit Errors

2024-7-16

Two Variable Logic with Ultimately Periodic Counting

2024-7-8

On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing

2024-7-4

How to Trap a Gradient Flow

2024-7-3

Complexity Classification of Counting Graph Homomorphisms Modulo a Prime Number

2024-7-1

Proof Complexity and the Binary Encoding of Combinatorial Principles

2024-6-24

AdWords in a Panorama

2024-6-17

Rapid Mixing of Glauber Dynamics via Spectral Independence for All Degrees

2024-6-13

Semialgebraic Proofs, IPS Lower Bounds, and the \(\boldsymbol{\tau}\)-Conjecture: Can a Natural Number be Negative?

2024-6-5

Induced Subgraphs of Bounded Treewidth and the Container Method

2024-5-31

Cluster Before You Hallucinate: Node-Capacitated Network Design and Energy Efficient Routing

2024-5-20

Further Collapses in \(\boldsymbol{\mathsf{TFNP}}\)

2024-5-2

Sublinear Time Approximation of the Cost of a Metric \({k}\)-Nearest Neighbor Graph

2024-4-17

Online List Labeling: Breaking the \({\log^2 n}\) Barrier

2024-4-11

Almost Optimal SuperConstant-Pass Streaming Lower Bounds for Reachability

2024-4-9

Rigid Matrices from Rectangular PCPs

2024-4-3

Rounds vs. Communication Tradeoffs for Maximal Independent Sets

2024-3-25

Parameterized Complexity of Untangling Knots

2024-3-21

Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings

2024-3-19

Sharp Thresholds in Random Simple Temporal Graphs

2024-3-19

Fast Metric Embedding into the Hamming Cube

2024-3-14

Reachability Preservers: New Extremal Bounds and Approximation Algorithms

2024-3-13

Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions

2024-3-13

Fixed-Parameter Algorithms for the Kneser and Schrijver Problems

2024-3-13

Counting Small Induced Subgraphs with Hereditary Properties

2024-3-12

Four-Coloring \(\boldsymbol{P_6}\)-Free Graphs. II. Finding an Excellent Precoloring

2024-2-28

On Matrix Multiplication and Polynomial Identity Testing

2024-2-27

Four-Coloring \(P_6\)-Free Graphs. I. Extending an Excellent Precoloring

2024-2-27

Testing Thresholds for High-Dimensional Sparse Random Geometric Graphs

2024-2-27

Online Edge Coloring via Tree Recurrences and Correlation Decay

2024-2-26

Flow Time Scheduling and Prefix Beck–Fiala

2024-2-26

Nondeterministic Quasi-Polynomial Time is Average-Case Hard for \(\textsf{ACC}\) Circuits

2024-2-23