archive
Every paper Pith has read. Search by title, abstract, or pith.
424 papers in cs.CC · page 9
-
CLIQUE has no polynomial-time deterministic solution
On P Versus NP
-
Low-degree likelihood ratio predicts runtime for inference tasks
Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio
-
Isolation sets of size k exist in A_{k,t} for k ≥ 4t-3
On maximal isolation sets in the uniform intersection matrix
-
Nash equilibrium existence in IP games is Σ₂ᵖ-complete
A note on the complexity of integer programming games
-
Directed APSP approximation equals exact Min-Max matrix product
Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max
-
pVASS termination time is linear or at least quadratic
Deciding Fast Termination for Probabilistic VASS with Nondeterminism
-
NP-hardness holds for Nash problems in symmetric win-lose games
The Complexity of Computational Problems about Nash Equilibria in Symmetric Win-Lose Games
-
k-dimensional Weisfeiler-Leman runs in O(n^{k+1} log n)
The $k$-Dimensional Weisfeiler-Leman Algorithm
-
Linear-time in-place algorithms for graph searches and connectivity
Optimal In-place Algorithms for Basic Graph Problems
-
Deleting or editing edges to reach RBMGs is NP-hard
Complexity of Modification Problems for Reciprocal Best Match Graphs
-
PCP with imperfect completeness made perfect at O(r) query cost
Imperfect Gaps in Gap-ETH and PCPs
-
Metric Dimension is W[1]-hard by treewidth
Metric Dimension Parameterized by Treewidth
-
AC^0[⊕] circuits need superpolynomial size for Andreev's Problem
On the $\text{AC}^0[\oplus]$ complexity of Andreev's Problem
-
Expanders let sum-of-squares approximate k-CSPs at bounded levels
Approximating Constraint Satisfaction Problems on High-Dimensional Expanders
-
Open problem links FFT lower bound to representation theory
Interesting Open Problem Related to Complexity of Computing the Fourier Transform and Group Theory
-
More correct labels shrink the compute gap in weak supervision
More Supervision, Less Computation: Statistical-Computational Tradeoffs in Weakly Supervised Learning
-
Algorithms decide reversibility of large 1D automata in polynomial time
Efficient methods to determine the reversibility of general 1D linear cellular automata in polynomial complexity
-
Poly-time oracle algorithm finds nearby points in small sets
Computational Concentration of Measure: Optimal Bounds, Reductions, and More
-
Order type realizability drops to expected NP time under noise
Smoothed Analysis of Order Types
-
SNAP reaches (ε,√ε)-SOSPs in O(1/ε^{2.5}) iterations
SNAP: Finding Approximate Second-Order Stationary Solutions Efficiently for Non-convex Linearly Constrained Problems
-
Client verifies polynomial evaluation in log d rounds with sublinear work
Interactive Verifiable Polynomial Evaluation
-
O(n log n) algorithm computes linear MIM-width of trees
Linear MIM-Width of Trees
-
No PTAS for interval-restricted scheduling unless P=NP
Inapproximability Results for Scheduling with Interval and Resource Restrictions
-
Oracle separates NIPZK from BQP
Oracle Separations Between Quantum and Non-interactive Zero-Knowledge Classes
-
Sparse random graphs have vector chromatic number ½√d + o(1)
Vector Colorings of Random, Ramanujan, and Large-Girth Irregular Graphs
-
FPT counts minimum (S,T)-cuts of size p in 2^{O(p^2)}n time
Fixed-parameter tractability of counting small minimum $(S,T)$-cuts
-
Jaccard closest pair needs quadratic time for close thresholds
Hardness of Bichromatic Closest Pair with Jaccard Similarity
-
Log-concave D learns deg-1 PTFs but not deg-2
Learning from satisfying assignments under continuous distributions
-
Poly-time algorithm for directed 2-linkage with fixed excesses
The directed 2-linkage problem with length constraints
-
Upper bounds close gap on graph minor theorem strength
Upper bounds on the graph minor theorem
-
Automata decide asymmetric unification for XOR with homomorphism
On Asymmetric Unification for the Theory of XOR with a Homomorphism
-
Computational phase transition leaves signature in Gibbs distributions
Computational Phase Transition Signature in Gibbs Sampling
-
Optimal colorings stay hard to recover from deleted neighbors
Finding Optimal Solutions With Neighborly Help
-
Poly-size circuit approximates unitary for two orthogonal states
Approximating Unitary Preparations of Orthogonal Black Box States
-
2D hidden linear function in QNC0 but not AC0
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
-
Simulation model shows P=NP cannot be proved
Computer-Simulation Model Theory (P= NP is not provable)