Edmund Ihler

We show that a fully polynomial time approximation scheme given

for an optimization problem can always be simply modified to a

polynomial time algorithm solving the problem optimally if the

computation model is the deterministic Turing Machine or the

logarithmic cost RAM and ...
more >>>

Christian Glaßer, Alan L. Selman, Samik Sengupta

We prove that all of the following assertions are equivalent:

There is a many-one complete disjoint NP-pair;

there is a strongly many-one complete disjoint NP-pair;

there is a Turing complete disjoint NP-pair such that all reductions

are smart reductions;

there is a complete disjoint NP-pair for one-to-one, invertible ...
more >>>

Alina Beygelzimer, Varsha Dani, Tom Hayes, John Langford

There are two approaches to solving a new supervised learning task: either

analyze the task independently or reduce it to a task that has already

been thoroughly analyzed. This paper investigates the latter approach for

classification problems. In addition to obvious theoretical motivations,

there is fairly strong empirical evidence that ...
more >>>

Oded Goldreich

The notion of promise problems was introduced and initially studied

by Even, Selman and Yacobi

(Information and Control, Vol.~61, pages 159-173, 1984).

In this article we survey some of the applications that this

notion has found in the twenty years that elapsed.

These include the notion ...
more >>>

Prasad Raghavendra, David Steurer, Madhur Tulsiani

The Small-Set Expansion Hypothesis (Raghavendra, Steurer, STOC 2010) is a natural hardness assumption concerning the problem of approximating the edge expansion of small sets in graphs. This hardness assumption is closely connected to the Unique Games Conjecture (Khot, STOC 2002). In particular, the Small-Set Expansion Hypothesis implies the Unique ... more >>>

Cody Murray, Ryan Williams

The Minimum Circuit Size Problem (MCSP) is: given the truth table of a Boolean function $f$ and a size parameter $k$, is the circuit complexity of $f$ at most $k$? This is the definitive problem of circuit synthesis, and it has been studied since the 1950s. Unlike many problems of ... more >>>

Eric Allender, Rahul Ilango, Neekon Vafa

The Minimum Circuit Size Problem (MCSP) has been the focus of intense study recently; MCSP is hard for SZK under rather powerful reductions, and is provably not hard under “local” reductions computable in TIME($n^{0.49}$). The question of whether MCSP is NP-hard (or indeed, hard even for small subclasses of P) ... more >>>

Oded Goldreich

We show that testing Hamiltonicity in the bounded-degree graph model requires a linear number of queries. This refers to both the path and the cycle versions of the problem, and similar results hold also for the directed analogues.

In addition, we present an alternative proof for the known fact that ...
more >>>

Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich

One-way functions (OWFs) are central objects of study in cryptography and computational complexity theory. In a seminal work, Liu and Pass (FOCS 2020) proved that the average-case hardness of computing time-bounded Kolmogorov complexity is equivalent to the existence of OWFs. It remained an open problem to establish such an equivalence ... more >>>

Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, Ruizhe Zhang

In this work, we initiate the study of the Minimum Circuit Size Problem (MCSP) in the quantum setting. MCSP is a problem to compute the circuit complexity of Boolean functions. It is a fascinating problem in complexity theory---its hardness is mysterious, and a better understanding of its hardness can have ... more >>>

Vahid Reza Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian

We study the problem of designing worst-case to average-case reductions for quantum algorithms. For all linear problems, we provide an explicit and efficient transformation of quantum algorithms that are only correct on a small (even sub-constant) fraction of their inputs into ones that are correct on all inputs. This stands ... more >>>

Oded Goldreich

For any fixed $t$, we present two fine-grained reductions of the problem of approximately counting the number of $t$-cliques in a graph to the problem of detecting a $t$-clique in a graph.

One of our reductions is slightly better than the prior reduction of Dell, Lapinskas, and Meeks (SODA20) and ...
more >>>