archive
Every paper Pith has read. Search by title, abstract, or pith.
424 papers in cs.CC · page 2
-
Modularity shows overlap gap on stochastic block model
The stochastic block model has the overlap graph property for modularity
-
Fisher equilibria approximation harder than 1/11 factor
Constant Inapproximability for Fisher Markets
-
Sparsity helps k-independent set only below Turán threshold
When Does Sparsity Help for k-Independent Set in Hypergraphs and Other Boolean CSPs?
-
Vertex attacks turn defensive covering Σ2P-complete
Continuous Defensive Domination Problems
-
XP algorithms and W[1]-hardness classify stationarity testing for PA functions in fixed d
Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses
-
Dimension parameter splits stationarity testing into XP and W[1]-hard cases
Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses
-
LPN weak solvers amplify to strong ones by scaling n and noise rate
Hardness Amplification for (Sparse) LPN
-
LPN hardness amplifies from few instances to almost all
Hardness Amplification for (Sparse) LPN
-
Generative models show an innovation window before memorizing data
The two clocks and the innovation window: When and how generative models learn rules
-
Optimal approx for satisfiable group linear equations
Optimal Inapproximability of Generalized Linear Equations over a Finite Group
-
MIP protocols tolerate any polynomial leakage
Multi-Prover Interactive Proof Systems with Leakage
-
Two-prover proofs verify NEXP with polynomial leakage
Multi-Prover Interactive Proof Systems with Leakage
-
PMMSNP reduces to finite-domain PCSP in poly time
Towards infinite PCSP: a dichotomy for monochromatic cliques
-
Streaming max-cut needs linear space in dense graphs
Streaming Complexity Separations for Dense and Sparse Graphs
-
Canonization and pruning verify Reed conjecture up to pathwidth 5
State Canonization and Early Pruning in Width-Based Automated Theorem Proving
-
Catalytic models with reset errors match standard classes
Understanding Robust Catalytic Computing
-
VNP equals VP over min-plus only with log certificate complements
VP, VNP and Algebraic Branching Programs over Min-Plus Semirings
-
This paper maps the quantum query complexity landscape for finding or detecting…
Quantum algorithms for path and cycle containment problems
-
ETH shows n^Ω(k) lower bound on approximating parameterized MLD
Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding under ETH
-
NL separated from logCFL via pebble automata entropy
Entropy of pebble automata and space complexity
-
Planarizing gadgets do not exist for (k,l)-tight graphs
Planarizing Gadgets for (k, l)-tight Graphs Do Not Exist
-
Algorithm computes Hermite form of relation lattices at matrix mult cost
Computing bases in Hermite normal form of lattices of integer relations
-
-
Right-hand side regularity fixes ODE solving difficulty
Relating the Computational and Logical Difficulty of Solving ODEs: From Polynomial to Discontinuous Right-Hand Sides
-
CORDIC iteration depth trims 33 percent of inference cycles
CARMEN: CORDIC-Accelerated Resource-Efficient Multi-Precision Inference Engine for Deep Learning
-
Bilateral treewidth makes QBF evaluation fixed-parameter tractable
Bilateral Treewidth for QBF: Where Strategies and Resolution Meet
-
Explicit construction shrinks variety-evasive subspace families
An Improved Construction of Variety-Evasive Subspace Families
-
Online algorithms hit exact limit for independent sets in dense hypergraphs
Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs
-
Benchmark measures unsafe completeness in scoped agent retrieval
Partial Evidence Bench: Benchmarking Authorization-Limited Evidence in Agentic Systems
-
Few-state machines rank conjecture decidability via Busy Beaver
Measuring Decidability as Related to Busy Beaver Numbers
-
Local homophily on graphs simulates Boolean circuits
Local Homophily on Bicolored Graphs is $\mathbf{P}$-complete
-
Deterministic structure matches randomized Online Orthogonal Vectors
Online Orthogonal Vectors Revisited
-
Riesz energy point selection is NP-hard in the plane
On the Complexity of Minimum Riesz s-Energy Subset Selection in Euclidean and Ultrametric Spaces
-
Transformers simulate constant-depth arithmetic circuits with average attention
Average Attention Transformers and Arithmetic Circuits
-
CNF formulas require superpolynomial roABP size in IPS
Hard CNF Instances for Ideal Proof Systems
-
Deep Transformers match explicit reasoning without steps
The Scaling Properties of Implicit Deductive Reasoning in Transformers
-
Waring length improves rigid homotopy complexity
Rigid homotopies for sampling from algebraic varieties: a Waring structure complexity model
-
Algorithm finds matroid basis in n^{3/7} parallel rounds
An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases
-
The paper tests whether a Pix2Pix image-translation model trained on one reservoir…
Robustness and Transferability of Pix2Geomodel for Bidirectional Facies Property Translation in a Complex Reservoir
-
No online algorithm finds common induced subgraphs beyond 2 log n
Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs
-
Exact induced norms found for key matrix classes
On the Induced Norms of Matrices and Grothendieck problems
-
Two open problems proven XNLP-complete in scheduling and graphs
The Parameterized Complexity of Scheduling with Precedence Delays: Shuffle Product and Directed Bandwidth
-
Quantum estimator nears optimal complexity for Tsallis entropy
Quantum Multi-Level Estimation of Functionals of Discrete Distributions
-
Optimal polytree found in O((2+ε)^n) time for constant in-degree
Exact and Approximate Algorithms for Polytree Learning
-
EQC claims tightened but still lag classical solvers
A Critical Comment on 'Entropy Computing: A Paradigm for Optimization in Open Photonic Systems'
-
Optimal union probability bounds are NP-hard to find
Optimal Union Probability Interval Is NP-Hard
-
MPC with limited machines needs higher local exponents for superlinear tasks
On Solving Problems of Substantially Super-linear Complexity in $N^{o(1)}$ Rounds in the MPC Model
-
Exponential circuit size is typical in symmetric exponential time
Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time
-
Stoquastic sparse Hamiltonians are StoqMA-complete
The Complexity of Stoquastic Sparse Hamiltonians
-
Self-referential instances force near-full input scan for dominating set
Solution independence and self-referential instances