Classical verifier checks a beyond-PH quantum language via an oracle
The public-coin protocol has perfect completeness and soundness error at most 1/4, with near-optimal message count.
Stories per day · 30 days
Relatedopenai4exponential-time-hypothesis2formal-verification2lean2anthropic1cryptography1fourier-sampling1harmonic-analysis1interactive-proofs1oracles1preprint1quantum-computation1scientific-claims1
11 stories, newest first · one card per story
Stories tagged #complexity-theory
OpenAI and Anthropic claim models refuted the Exponential Time Hypothesis
Computer scientists are reviewing claimed sub-exponential algorithms, including whether they weaken assumptions behind some cryptography.
OpenAI asks experts to check AI proofs in math, CS, and physics
OpenAI says models disproved the Exponential Time Hypothesis and proved local smoothing in every dimension; reviewers have not endorsed the claims.
2
OpenAI math preprint says the Exponential Time Hypothesis is false
The Hacker News link is only a PDF in OpenAI’s math GitHub repo, with 72 points and 21 comments.
OpenAI shares AI math, complexity and physics results with academics
Shepherds chose three release paths; Lean writeups for the math and ETH results are already public.
1
Unitary complexity in polynomial space
Proving quantum commitments exist unconditionally requires solving either the unitary synthesis problem or the BPP vs NEXP question, linking cryptographic assumptions to classical complexity open problems.
On quantum interactive proofs with a laconic prover
A complexity paper characterizes two-message quantum proofs with short prover messages via state distinguishability.
Witness Encryption via Prime-Order Generic Groups
Unconditional witness encryption construction for NP in the generic-group model, plus first superconstant NP-hardness result for homogeneous MinRank.
Thin-shell stability of Gaussian cooling: logconcave sampling with sesteric complexity from a cold start
Thin-shell stability proof along the Gaussian cooling path improves cold-start logconcave sampling complexity to near n^2.5 from n^2.75.
Differential Privacy Meets Fixed Parameter Tractability: Algorithms and Lower Bounds
Theory paper combines differential privacy with fixed-parameter tractable encoders, improving approximation guarantees for combinatorial optimization and proving new lower bounds.
Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead
Theorists prove multi-step lookahead RL planning is NP-hard for every fixed rational discount factor yet give a randomized polynomial-time approximation scheme.