OOIR: Observatory of International Research

Papers

(The median citation count of SIAM Journal on Computing is 0. The table below lists those papers that are above that threshold based on CrossRef citation counts [max. 250 papers]. The publications cover those that have been published in the past four years, i.e., from 2022-08-01 to 2026-08-01.)

Article	Citations
Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier	19
Flow-Augmentation III: Complexity Dichotomy for Boolean CSPs Parameterized by the Number of Unsatisfied Constraints	17
Testing Graph Properties with the Container Method	15
Tight Revenue Gaps among Multiunit Mechanisms	15
Induced Subgraphs of Bounded Treewidth and the Container Method	12
Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion	11
Competitively Chasing Convex Bodies	11
An Exponential Time Parameterized Algorithm for Planar Disjoint Paths	11
Revisionist Simulations: A New Approach to Proving Space Lower Bounds	10
Minimum Cuts in Surface Graphs	10
Algorithms for Subpath Convex Hull Queries and Ray-Shooting among Segments	9
Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem	9
Complexity Classification of Counting Graph Homomorphisms Modulo a Prime Number	9
Dot-Product Proofs and Their Applications	7
A Single-Exponential Time 2-Approximation Algorithm for Treewidth	7
Dynamic Geometric Set Cover, Revisited	7
Parameterized Complexity of Untangling Knots	6
Circuits Resilient to Short-Circuit Errors	6
Toward Derandomizing Markov Chain Monte Carlo	5
The Approximate Degree of DNF and CNF Formulas	5
Separating MAX 2-AND, MAX DI-CUT, and MAX CUT	5
Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance	5
An Improved Upper Bound for the Universal TSP on the Grid	5
On the Privacy of Noisy Stochastic Gradient Descent for Convex Optimization	5
Further Collapses in $\boldsymbol{\mathsf{TFNP}}$	5

One-Way Functions and (Im)perfect Obfuscation	5
Generalized Singleton Bound and List-Decoding Reed–Solomon Codes Beyond the Johnson Radius	5
Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes	5
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification	5
On the Complexity of Equilibrium Computation in First-Price Auctions	4
Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time	4
Finding Maximum Edge-Disjoint Paths Between Multiple Terminals	4
Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm	4
Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension	4
Ghost Value Augmentation for ${k}$-Edge-Connectivity	4
On Min Sum Vertex Cover and Generalized Min Sum Set Cover	4
Non-Black-Box Worst-Case to Average-Case Reductions Within $\mathsf{NP}$	4
Balanced Allocation: Patience Is Not a Virtue	3
Settling the Complexity of Nash Equilibrium in Congestion Games	3
Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games via Weighted Block Laplacians	3
Doubly Efficient Private Information Retrieval and Fully Homomorphic Ram Computation from Ring LWE	3
The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination	3
Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions	3
PTAS for Minimum Cost MultiCovering with Disks	3
Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions	3
Generic Reed–Solomon Codes Achieve List-Decoding Capacity	3
Resolving Matrix Spencer Conjecture up to Poly-Logarithmic Rank	3
Distributed Edge Coloring in Time Polylogarithmic in ${\Delta }$	3
Nondeterministic Quasi-Polynomial Time is Average-Case Hard for $\textsf{ACC}$ Circuits	3
QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge	3
Almost-Optimal Sublinear Additive Spanners	3
Improved Optimal Testing Results from Global Hypercontractivity	3
Quantum Eigenvalue Processing	3
Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices: Garbled Circuits of Optimal Size, Laconic Functional Evaluation, and More	3
Semidefinite Programming and Linear Equations vs. Homomorphism Problems	3
Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error	3
Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree	2
Special Section on the Sixtieth Annual Symposium on Foundations of Computer Science (FOCS 2019)	2
Constant Inapproximability for PPA	2
Space Complexity of Vertex Connectivity Oracles	2
Rapid Mixing of Glauber Dynamics via Spectral Independence for All Degrees	2
Semialgebraic Proofs, IPS Lower Bounds, and the $\boldsymbol{\tau}$-Conjecture: Can a Natural Number be Negative?	2
Online Edge Coloring Is (Nearly) as Easy as Offline	2
Quantum Time-Space Tradeoffs for Matrix Problems	2
Fast Metric Embedding into the Hamming Cube	2
Inapproximability of Matrix $\boldsymbol{p \rightarrow q}$ Norms	2
Constant-Depth Arithmetic Circuits for Linear Algebra Problems	2
Agreement Tests on Graphs and Hypergraphs	2
Want to Gather? No Need to Chatter!	2
Relaxed Local Correctability from Local Testing	2
Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in $\boldsymbol{H}$-Free Graphs	2
Erratum: A Full Dichotomy for $\textsf{Holant}^\mathbf{c}$, Inspired by Quantum Computation	2
Quantum Speedups for Linear Programming via Interior Point Methods	2
Exact Algorithms and Lower Bounds for Stable Instances of Euclidean $\boldsymbol{k}$- means	2
Spectral Methods from Tensor Networks	2

Tracing Isomanifolds in $\mathbb{R}$ ^d in Time Polynomial in d using Coxeter–Freudenthal–Kuhn Triangulations	2
Corrigendum: Metric Embedding via Shortest Path Decompositions	2
A Logarithmic Lower Bound for Oblivious RAM (For All Parameters)	2
Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding	2
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation	2
Fitting Metrics and Ultrametrics with Minimum Disagreements	2
Approximate Graph Coloring and the Crystal with a Hollow Shadow	2
A Unified Framework of Light Spanners I: Fast (Yet Optimal) Constructions	2
Deterministic Massively Parallel Connectivity	2
Laplace Transform–Based Quantum Eigenvalue Transformation via Linear Combination of Hamiltonian Simulation	2
$\boldsymbol{\Pi_2^P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem	2
Isomorphism Testing for Graphs Excluding Small Minors	2
On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited	2
Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares	2
Sublinear Time Approximation of the Cost of a Metric ${k}$-Nearest Neighbor Graph	2
Special Section on the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (2020)	1
Twin-Width III: Max Independent Set, Min Dominating Set, and Coloring	1
On CDCL-Based Proof Systems with the Ordered Decision Strategy	1
An Improved Parameterized Algorithm for Treewidth	1
Order-Competitive Ratio	1
Proof Complexity and the Binary Encoding of Combinatorial Principles	1
Almost-Ramanujan Expanders From Arbitrary Expanders via Operator Amplification	1
On the Nisan–Ronen Conjecture for Submodular Valuations	1
The Orthogonal Vectors Conjecture and Nonuniform Circuit Lower Bounds	1
Constant Depth Formula and Partial Function Versions of MCSP Are Hard	1
On Matrix Multiplication and Polynomial Identity Testing	1
NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach	1
Algorithms and Certificates for Boolean CSP Refutation: Smoothed Is No Harder than Random	1
An Optimal Separation of Randomized and Quantum Query Complexity	1
Discrepancy Minimization via a Self-Balancing Walk	1
An FPT Algorithm for the Embeddability of Graphs Into Two-Dimensional Simplicial Complexes	1
Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving	1
Sublinear Algorithms for Local Graph-Centrality Estimation	1
Optimal (degree+1)-Coloring in Congested Clique	1
Online Edge Coloring via Tree Recurrences and Correlation Decay	1
Counting Small Induced Subgraphs with Hereditary Properties	1
Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings	1
Faster Isomorphism for ${p}$-Groups of Class 2 and Exponent ${p}$	1
Gapped Clique Homology on Weighted Graphs Is ${\text{QMA}_1}$-Hard and Contained in QMA	1
Cheeger’s Inequalities for Vertex Expansion and Reweighted Eigenvalues	1
Two Variable Logic with Ultimately Periodic Counting	1
Reducing Tarski to Unique Tarski (In the Black-Box Model)	1
Parallel Repetition for the GHZ Game: Exponential Decay	1
The Shortest Even Cycle Problem Is Tractable	1
Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion	1
Super-Logarithmic Lower Bounds for Dynamic Graph Problems	1
The Minimal Faithful Permutation Degree of Groups Without Abelian Normal Subgroups	1
Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence	1
On the Computability of Continuous Maximum Entropy Distributions with Applications	1
Internal Pattern Matching Queries in a Text and Applications	0
Four-Coloring $P_6$-Free Graphs. I. Extending an Excellent Precoloring	0
Differentially Private Sampling from Distributions	0
Symmetries, Graph Properties, and Quantum Speedups	0
AdWords in a Panorama	0
Rigid Matrices from Rectangular PCPs	0
Small but Unwieldy: A Lower Bound on Adjacency Labels for Small Classes	0
Special Section on the Fifty-Ninth Annual IEEE Symposium on Foundations of Computer Science (2018)	0
Unambiguous DNFs and Alon–Saks–Seymour	0
Reachability Preservers: New Extremal Bounds and Approximation Algorithms	0
Why Extension-Based Proofs Fail	0
Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension	0
Tree-Depth and the Formula Complexity of Subgraph Isomorphism	0
Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction	0
Average Sensitivity of Graph Algorithms	0
Greedy Algorithm Almost Dominates in Smoothed Contextual Bandits	0
Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity	0
A $\boldsymbol{\phi }$ -Competitive Algorithm for Scheduling Packets with Deadlines	0
Reverse Mathematics of Complexity Lower Bounds	0
Lower Bounds for Regular Resolution over Parities	0
Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\boldsymbol{\sqrt {n}}$ Dimension Threshold	0
Computational Complexity of the Hylland–Zeckhauser Mechanism for One-Sided Matching Markets	0
One-Way Functions and Zero Knowledge	0
Almost Optimal SuperConstant-Pass Streaming Lower Bounds for Reachability	0
Agnostic Proper Learning of Monotone Functions: Beyond the Black-Box Correction Barrier	0
ABE for Circuits with poly$ {(\lambda )}$-Sized Keys from LWE	0
Traversing Combinatorial 0/1-Polytopes via Optimization	0
Approximating Maximum Independent Set for Rectangles in the Plane	0
Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover	0
Adversarial Laws of Large Numbers and Optimal Regret in Online Classification	0
Online List Labeling: Breaking the ${\log^2 n}$ Barrier	0

Four-Coloring $\boldsymbol{P_6}$-Free Graphs. II. Finding an Excellent Precoloring	0
From Contention Resolution to Matroid Secretary and Back	0
Fixed-Parameter Algorithms for the Kneser and Schrijver Problems	0
A ${d}^{{1/2+{o}(1)}}$ Monotonicity Tester for Boolean Functions on ${d}$-Dimensional Hypergrids	0
Algebraic Algorithms for Fractional Linear Matroid Parity via Noncommutative Rank	0
Fast FPT-Approximation of Branchwidth	0
Faster Isomorphism Testing of p -Groups of Frattini Class 2	0
Improved Girth Approximation in Weighted Undirected Graphs	0
FIXP-Membership via Convex Optimization: Games, Cakes, and Markets	0
Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu	0
Exact-Size Sampling of Enriched Trees in Linear Time	0
Hardness vs. Randomness, Revised: Uniform, Non-Black-Box, and Instance-wise	0
The Power of Proportional Fairness for Nonclairvoyant Polytope Scheduling	0
A Subquadratic Upper Bound on Hurwitz’s Problem and Related Noncommutative Polynomials	0
Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles	0
Agnostically Learning Multi-Index Models with Queries	0
Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics	0
Counting Subgraphs in Somewhere Dense Graphs	0
Complete Characterization of Fairness in Secure Two-Party Computation of Boolean Functions	0
Polynomial-Time Approximation Schemes for Facility Location on Planar Graphs	0
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders	0
${\mathcal{O}}$${(\log\,\log\,{{n}})}$ Passes Are Optimal for Semistreaming Maximal Independent Set	0
Fast Generalized DFTs for All Finite Groups	0
Complexity Classification Transfer for CSPs via Algebraic Products	0
Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg–Rao	0
Online Primal Dual Meets Online Matching with Stochastic Rewards: Configuration LP to the Rescue	0
Prophet Secretary for Combinatorial Auctions and Matroids	0
An ETH-Tight Exact Algorithm for Euclidean TSP	0
Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs	0
Removing Additive Structure in 3SUM-Based Reductions	0
SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle	0
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering	0
Linear Independence, Alternants and Applications	0
Efficient Two-Sided Markets with Limited Information	0
Locally Consistent Parsing for Text Indexing in Small Space	0
Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs	0
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture	0
Testing Thresholds for High-Dimensional Sparse Random Geometric Graphs	0
Approximation Algorithms for LCS and LIS with Truly Improved Running Times	0
The Optimal Error Resilience of Interactive Communication over Binary Channels	0
Jamming-Resistant Backoff with Polylogarithmic Sending and Listening Cost	0
Cluster Before You Hallucinate: Node-Capacitated Network Design and Energy Efficient Routing	0
CLAP: A New Algorithm for Promise CSPs	0
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity	0
A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics	0
An Approximate Generalization of the Okamura–Seymour Theorem	0
Topology and Adjunction in Promise Constraint Satisfaction	0
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection	0
Kronecker Products, Low-Depth Circuits, and Matrix Rigidity	0
Combinatorial Contracts	0
Deterministic Algorithm and Faster Algorithm for Submodular Maximization Subject to a Matroid Constraint	0
Special Section on The Sixty-Third Annual IEEE Symposium on Foundations of Computer Science (2022)	0
Rounds vs. Communication Tradeoffs for Maximal Independent Sets	0
Decidability of Membership Problems for Flat Rational Subsets of $\boldsymbol{{\textrm{GL}}(2,\boldsymbol{{\mathbb{Q}}})}$ and Singular Matrices	0
On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing	0
Proximity Search for Maximal Subgraph Enumeration	0
The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem	0
Quantum Lower Bounds by Sample-to-Query Lifting	0
How to Trap a Gradient Flow	0
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics	0
The Minimum Formula Size Problem is (ETH) Hard	0
Clustering Mixtures with Almost Optimal Separation in Polynomial Time	0
Uniform Restricted Chase Termination	0
Edge-Disjoint Paths in Expanders: Online with Removals	0
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness	0
A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games	0
Approximate Gomory–Hu Tree is Faster than $\boldsymbol{n}\,\boldsymbol{-\, 1}$ Maximum Flows	0
Deterministic $\boldsymbol{(\unicode{x00BD}+\varepsilon)}$ -Approximation for Submodular Maximization over a Matroid	0
Sharp Thresholds in Random Simple Temporal Graphs	0
Interior Point Methods Are Not Worse than Simplex	0
Special Section on the Fifty-First Annual ACM Sympositum on the Theory of Computing (STOC 2019)	0
Packing Cycles in Planar and Bounded-Genus Graphs	0
The Economic Limits of Permissionless Consensus	0
Shortest Paths Without a Map, but with an Entropic Regularizer	0
Optimal Resizable Arrays	0
Multi-Item Nontruthful Auctions Achieve Good Revenue	0
A Near-Optimal Algorithm for Shortest Paths Among Curved Obstacles in the Plane	0
A Direct Product Theorem for Quantum Communication Complexity with Applications to Device-Independent Cryptography	0
Tree Evaluation is in Space ${O}$${(\log n \cdot \log \log n)}$	0
Special Section on the Sixty-Fourth Annual Ieee Symposium on Foundations of Computer Science (2023)	0
Hop-Constrained Oblivious Routing	0
Flow Time Scheduling and Prefix Beck–Fiala	0
A Strong Version of Cobham’s Theorem	0
Economical Convex Coverings and Applications	0
Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches	0
The Power of Two Choices in Graphical Allocation	0
A Nearly Quadratic-Time FPTAS for Knapsack	0
Collapsing the Bounded Width Hierarchy for Infinite-Domain Constraint Satisfaction Problems: When Symmetries Are Enough	0
Toward Better Depth Lower Bounds: A KRW-like Theorem For Strong Composition	0
Consensus-Halving: Does It Ever Get Easier?	0
Competitive Analysis with a Sample and the Secretary Problem	0
Lower Bounds on Tree Covers	0
Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ${\ell_{{p}}}$ Norms	0

Tracing Isomanifolds in \(\mathbb{R}\) ^d in Time Polynomial in d using Coxeter–Freudenthal–Kuhn Triangulations	2
Corrigendum: Metric Embedding via Shortest Path Decompositions	2
A Logarithmic Lower Bound for Oblivious RAM (For All Parameters)	2
Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding	2
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation	2
Fitting Metrics and Ultrametrics with Minimum Disagreements	2
Approximate Graph Coloring and the Crystal with a Hollow Shadow	2
A Unified Framework of Light Spanners I: Fast (Yet Optimal) Constructions	2
Deterministic Massively Parallel Connectivity	2
Laplace Transform–Based Quantum Eigenvalue Transformation via Linear Combination of Hamiltonian Simulation	2
\(\boldsymbol{\Pi_2^P}\) vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem	2
Isomorphism Testing for Graphs Excluding Small Minors	2
On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited	2
Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares	2
Sublinear Time Approximation of the Cost of a Metric \({k}\)-Nearest Neighbor Graph	2
Special Section on the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (2020)	1
Twin-Width III: Max Independent Set, Min Dominating Set, and Coloring	1
On CDCL-Based Proof Systems with the Ordered Decision Strategy	1
An Improved Parameterized Algorithm for Treewidth	1
Order-Competitive Ratio	1
Proof Complexity and the Binary Encoding of Combinatorial Principles	1
Almost-Ramanujan Expanders From Arbitrary Expanders via Operator Amplification	1
On the Nisan–Ronen Conjecture for Submodular Valuations	1
The Orthogonal Vectors Conjecture and Nonuniform Circuit Lower Bounds	1
Constant Depth Formula and Partial Function Versions of MCSP Are Hard	1
On Matrix Multiplication and Polynomial Identity Testing	1
NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach	1
Algorithms and Certificates for Boolean CSP Refutation: Smoothed Is No Harder than Random	1
An Optimal Separation of Randomized and Quantum Query Complexity	1
Discrepancy Minimization via a Self-Balancing Walk	1
An FPT Algorithm for the Embeddability of Graphs Into Two-Dimensional Simplicial Complexes	1
Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving	1
Sublinear Algorithms for Local Graph-Centrality Estimation	1
Optimal (degree+1)-Coloring in Congested Clique	1
Online Edge Coloring via Tree Recurrences and Correlation Decay	1
Counting Small Induced Subgraphs with Hereditary Properties	1
Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings	1
Faster Isomorphism for \({p}\)-Groups of Class 2 and Exponent \({p}\)	1
Gapped Clique Homology on Weighted Graphs Is \({\text{QMA}_1}\)-Hard and Contained in QMA	1
Cheeger’s Inequalities for Vertex Expansion and Reweighted Eigenvalues	1
Two Variable Logic with Ultimately Periodic Counting	1
Reducing Tarski to Unique Tarski (In the Black-Box Model)	1
Parallel Repetition for the GHZ Game: Exponential Decay	1
The Shortest Even Cycle Problem Is Tractable	1
Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion	1
Super-Logarithmic Lower Bounds for Dynamic Graph Problems	1
The Minimal Faithful Permutation Degree of Groups Without Abelian Normal Subgroups	1
Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence	1
On the Computability of Continuous Maximum Entropy Distributions with Applications	1
Internal Pattern Matching Queries in a Text and Applications	0
Four-Coloring \(P_6\)-Free Graphs. I. Extending an Excellent Precoloring	0
Differentially Private Sampling from Distributions	0
Symmetries, Graph Properties, and Quantum Speedups	0
AdWords in a Panorama	0
Rigid Matrices from Rectangular PCPs	0
Small but Unwieldy: A Lower Bound on Adjacency Labels for Small Classes	0
Special Section on the Fifty-Ninth Annual IEEE Symposium on Foundations of Computer Science (2018)	0
Unambiguous DNFs and Alon–Saks–Seymour	0
Reachability Preservers: New Extremal Bounds and Approximation Algorithms	0
Why Extension-Based Proofs Fail	0
Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension	0
Tree-Depth and the Formula Complexity of Subgraph Isomorphism	0
Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction	0
Average Sensitivity of Graph Algorithms	0
Greedy Algorithm Almost Dominates in Smoothed Contextual Bandits	0
Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity	0
A \(\boldsymbol{\phi }\) -Competitive Algorithm for Scheduling Packets with Deadlines	0
Reverse Mathematics of Complexity Lower Bounds	0
Lower Bounds for Regular Resolution over Parities	0
Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the \(\boldsymbol{\sqrt {n}}\) Dimension Threshold	0
Computational Complexity of the Hylland–Zeckhauser Mechanism for One-Sided Matching Markets	0
One-Way Functions and Zero Knowledge	0
Almost Optimal SuperConstant-Pass Streaming Lower Bounds for Reachability	0
Agnostic Proper Learning of Monotone Functions: Beyond the Black-Box Correction Barrier	0
ABE for Circuits with poly\( {(\lambda )}\)-Sized Keys from LWE	0
Traversing Combinatorial 0/1-Polytopes via Optimization	0
Approximating Maximum Independent Set for Rectangles in the Plane	0
Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover	0
Adversarial Laws of Large Numbers and Optimal Regret in Online Classification	0
Online List Labeling: Breaking the \({\log^2 n}\) Barrier	0

Four-Coloring \(\boldsymbol{P_6}\)-Free Graphs. II. Finding an Excellent Precoloring	0
From Contention Resolution to Matroid Secretary and Back	0
Fixed-Parameter Algorithms for the Kneser and Schrijver Problems	0
A \({d}^{{1/2+{o}(1)}}\) Monotonicity Tester for Boolean Functions on \({d}\)-Dimensional Hypergrids	0
Algebraic Algorithms for Fractional Linear Matroid Parity via Noncommutative Rank	0
Fast FPT-Approximation of Branchwidth	0
Faster Isomorphism Testing of p -Groups of Frattini Class 2	0
Improved Girth Approximation in Weighted Undirected Graphs	0
FIXP-Membership via Convex Optimization: Games, Cakes, and Markets	0
Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu	0
Exact-Size Sampling of Enriched Trees in Linear Time	0
Hardness vs. Randomness, Revised: Uniform, Non-Black-Box, and Instance-wise	0
The Power of Proportional Fairness for Nonclairvoyant Polytope Scheduling	0
A Subquadratic Upper Bound on Hurwitz’s Problem and Related Noncommutative Polynomials	0
Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles	0
Agnostically Learning Multi-Index Models with Queries	0
Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics	0
Counting Subgraphs in Somewhere Dense Graphs	0
Complete Characterization of Fairness in Secure Two-Party Computation of Boolean Functions	0
Polynomial-Time Approximation Schemes for Facility Location on Planar Graphs	0
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders	0
\({\mathcal{O}}\)\({(\log\,\log\,{{n}})}\) Passes Are Optimal for Semistreaming Maximal Independent Set	0
Fast Generalized DFTs for All Finite Groups	0
Complexity Classification Transfer for CSPs via Algebraic Products	0
Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg–Rao	0
Online Primal Dual Meets Online Matching with Stochastic Rewards: Configuration LP to the Rescue	0
Prophet Secretary for Combinatorial Auctions and Matroids	0
An ETH-Tight Exact Algorithm for Euclidean TSP	0
Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs	0
Removing Additive Structure in 3SUM-Based Reductions	0
SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle	0
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering	0
Linear Independence, Alternants and Applications	0
Efficient Two-Sided Markets with Limited Information	0
Locally Consistent Parsing for Text Indexing in Small Space	0
Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs	0
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture	0
Testing Thresholds for High-Dimensional Sparse Random Geometric Graphs	0
Approximation Algorithms for LCS and LIS with Truly Improved Running Times	0
The Optimal Error Resilience of Interactive Communication over Binary Channels	0
Jamming-Resistant Backoff with Polylogarithmic Sending and Listening Cost	0
Cluster Before You Hallucinate: Node-Capacitated Network Design and Energy Efficient Routing	0
CLAP: A New Algorithm for Promise CSPs	0
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity	0
A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics	0
An Approximate Generalization of the Okamura–Seymour Theorem	0
Topology and Adjunction in Promise Constraint Satisfaction	0
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection	0
Kronecker Products, Low-Depth Circuits, and Matrix Rigidity	0
Combinatorial Contracts	0
Deterministic Algorithm and Faster Algorithm for Submodular Maximization Subject to a Matroid Constraint	0
Special Section on The Sixty-Third Annual IEEE Symposium on Foundations of Computer Science (2022)	0
Rounds vs. Communication Tradeoffs for Maximal Independent Sets	0
Decidability of Membership Problems for Flat Rational Subsets of \(\boldsymbol{{\textrm{GL}}(2,\boldsymbol{{\mathbb{Q}}})}\) and Singular Matrices	0
On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing	0
Proximity Search for Maximal Subgraph Enumeration	0
The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem	0
Quantum Lower Bounds by Sample-to-Query Lifting	0
How to Trap a Gradient Flow	0
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics	0
The Minimum Formula Size Problem is (ETH) Hard	0
Clustering Mixtures with Almost Optimal Separation in Polynomial Time	0
Uniform Restricted Chase Termination	0
Edge-Disjoint Paths in Expanders: Online with Removals	0
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness	0
A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games	0
Approximate Gomory–Hu Tree is Faster than \(\boldsymbol{n}\,\boldsymbol{-\, 1}\) Maximum Flows	0
Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid	0
Sharp Thresholds in Random Simple Temporal Graphs	0
Interior Point Methods Are Not Worse than Simplex	0
Special Section on the Fifty-First Annual ACM Sympositum on the Theory of Computing (STOC 2019)	0
Packing Cycles in Planar and Bounded-Genus Graphs	0
The Economic Limits of Permissionless Consensus	0
Shortest Paths Without a Map, but with an Entropic Regularizer	0
Optimal Resizable Arrays	0
Multi-Item Nontruthful Auctions Achieve Good Revenue	0
A Near-Optimal Algorithm for Shortest Paths Among Curved Obstacles in the Plane	0
A Direct Product Theorem for Quantum Communication Complexity with Applications to Device-Independent Cryptography	0
Tree Evaluation is in Space \({O}\)\({(\log n \cdot \log \log n)}\)	0
Special Section on the Sixty-Fourth Annual Ieee Symposium on Foundations of Computer Science (2023)	0
Hop-Constrained Oblivious Routing	0
Flow Time Scheduling and Prefix Beck–Fiala	0
A Strong Version of Cobham’s Theorem	0
Economical Convex Coverings and Applications	0
Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches	0
The Power of Two Choices in Graphical Allocation	0
A Nearly Quadratic-Time FPTAS for Knapsack	0
Collapsing the Bounded Width Hierarchy for Infinite-Domain Constraint Satisfaction Problems: When Symmetries Are Enough	0
Toward Better Depth Lower Bounds: A KRW-like Theorem For Strong Composition	0
Consensus-Halving: Does It Ever Get Easier?	0
Competitive Analysis with a Sample and the Secretary Problem	0
Lower Bounds on Tree Covers	0
Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All \({\ell_{{p}}}\) Norms	0