We connect the study of pseudodeterministic algorithms to two major open problems about
the structural complexity of BPTIME: proving hierarchy theorems and showing the existence …

We construct a PCP for NTIME (2 n) with constant soundness, 2 n poly (n) proof length, and
poly (n) queries where the verifier's computation is simple: the queries are a projection of the …

We present a protocol that transforms any quantum multi-prover interactive proof into a
nonlocal game in which questions consist of logarithmic number of bits and answers of …

For each positive integer n, let ℒ N (n) be the class of sets accepted by a family of automata
of type N, each with a read-only input with endmarkers and n two-way input heads. The …

In this work we consider the interplay between multiprover interactive proofs, quantum
entanglement, and zero knowledge proofs-notions that are central pillars of complexity …

To characterize the computational complexity of satisfiability problems for probabilistic and
causal reasoning within the Pearl's Causal Hierarchy, arXiv: 2305.09508 [cs. AI] introduce a …

Abstract Let L ⊆ Σ* be accepted in time f (n) by a nondeterministic Turing machine. Then
there is a monadic existential second-order sentence σ in the language of+ such that for …

We show a hierarchy for probabilistic time with one bit of advice, specifically we show that for
all real numbers 1/spl les//spl alpha//spl les//spl beta/, BPTIME (n/sup/spl alpha//)/l/spl …

We make the first progress on probabilistic-degree lower bounds and correlation bounds for
polynomials since the papers by Razborov and Smolensky in the 80's. The bounds hold for …

In this paper I present probably the simplest possible abstract formal proof that P≠ NP, and
NP= EXPTIME, in the context of the Zermelo-Frankel set theory and deterministic Turing …