Mihir Bellare, Oded Goldreich, Madhu Sudan

This paper continues the investigation of the connection between proof

systems and approximation. The emphasis is on proving ``tight''

non-approximability results via consideration of measures like the

``free bit complexity'' and the ``amortized free bit complexity'' of

proof systems.

The first part of the paper presents a collection of new ... more >>>

Miklos Ajtai

We show that the shortest vector problem in lattices

with L_2 norm is NP-hard for randomized reductions. Moreover we

also show that there is a positive absolute constant c, so that to

find a vector which is longer than the shortest non-zero vector by no

more than a factor of ...
more >>>

Oded Goldreich

In 1984, Leonid Levin has initiated a theory of average-case complexity.

We provide an exposition of the basic definitions suggested by Levin,

and discuss some of the considerations underlying these definitions.

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy

We show that every language in NP has a probablistic verifier

that checks membership proofs for it using

logarithmic number of random bits and by examining a

<em> constant </em> number of bits in the proof.

If a string is in the language, then there exists a proof ...
more >>>

Venkatesan Guruswami, Daniel Lewin and Madhu Sudan, Luca Trevisan

It is known that there exists a PCP characterization of NP

where the verifier makes 3 queries and has a {\em one-sided}

error that is bounded away from 1; and also that 2 queries

do not suffice for such a characterization. Thus PCPs with

3 ...
more >>>

Madhu Sudan, Luca Trevisan

The error probability of Probabilistically Checkable Proof (PCP)

systems can be made exponentially small in the number of queries

by using sequential repetition. In this paper we are interested

in determining the precise rate at which the error goes down in

an optimal protocol, and we make substantial progress toward ...
more >>>

Ilya Dumer, Daniele Micciancio, Madhu Sudan

We show that the minimum distance of a linear code (or

equivalently, the weight of the lightest codeword) is

not approximable to within any constant factor in random polynomial

time (RP), unless NP equals RP.

Under the stronger assumption that NP is not contained in RQP

(random ...
more >>>

Valentine Kabanets, Jin-Yi Cai

We study the complexity of the circuit minimization problem:

given the truth table of a Boolean function f and a parameter s, decide

whether f can be realized by a Boolean circuit of size at most s. We argue

why this problem is unlikely to be in P (or ...
more >>>

A. Pavan, Alan L. Selman

We use hypotheses of structural complexity theory to separate various

NP-completeness notions. In particular, we introduce an hypothesis from which we describe a set in NP that is Turing complete but not truth-table complete. We provide fairly thorough analyses of the hypotheses that we introduce. Unlike previous approaches, we ...
more >>>

Piotr Berman, Marek Karpinski, Alexander D. Scott

We prove approximation hardness of short symmetric instances

of MAX-3SAT in which each literal occurs exactly twice, and

each clause is exactly of size 3. We display also an explicit

approximation lower bound for that problem. The bound two on

the number ...
more >>>

Scott Contini, Ernie Croot, Igor E. Shparlinski

We present an algorithm to invert the Euler function $\varphi(m)$. The algorithm, for a given integer $n\ge 1$, in polynomial time ``on average'', finds theset $\Psi(n)$ of all solutions $m$ to the equation $\varphi(m) =n$. In fact, in the worst case the set $\Psi(n)$ is exponentially large and cannot be ... more >>>

Michael Schmitt

The computational complexity of learning from binary examples is

investigated for linear threshold neurons. We introduce

combinatorial measures that create classes of infinitely many

learning problems with sample restrictions. We analyze how the

complexity of these problems depends on the values for the measures.

...
more >>>

John Hitchcock, A. Pavan

Under the assumption that NP does not have p-measure 0, we

investigate reductions to NP-complete sets and prove the following:

- Adaptive reductions are more powerful than nonadaptive

reductions: there is a problem that is Turing-complete for NP but

not truth-table-complete.

- Strong nondeterministic reductions are more powerful ... more >>>

Christian Glaßer, Alan L. Selman, Stephen Travers, Klaus W. Wagner

This paper is motivated by the open question

whether the union of two disjoint NP-complete sets always is

NP-complete. We discover that such unions retain

much of the complexity of their single components. More precisely,

they are complete with respect to more general reducibilities.

Christoph Buchheim, Peter J Cameron, Taoyang Wu

We investigate the computational complexity of finding an element of

a permutation group~$H\subseteq S_n$ with a minimal distance to a

given~$\pi\in S_n$, for different metrics on~$S_n$. We assume

that~$H$ is given by a set of generators, such that the problem

cannot be solved in polynomial time ...
more >>>

Debasis Mandal, A. Pavan, Rajeswari Venugopalan

We show that there is a language that is Turing complete for NP but not many-one complete for NP, under a {\em worst-case} hardness hypothesis. Our hypothesis asserts the existence of a non-deterministic, double-exponential time machine that runs in time $O(2^{2^{n^c}})$ (for some $c > 1$) accepting $\Sigma^*$ whose accepting ... 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 >>>

Beate Bollig

Ordered binary decision diagrams (OBDDs) are a popular data structure for Boolean functions.

Some applications work with a restricted variant called complete OBDDs

which is strongly related to nonuniform deterministic finite automata.

One of its complexity measures is the width which has been investigated

in several areas in computer science ...
more >>>

Shuichi Hirahara, Osamu Watanabe

The Minimum Circuit Size Problem (MCSP) is known to be hard for statistical zero knowledge via a BPP-reduction (Allender and Das, 2014), whereas establishing NP-hardness of MCSP via a polynomial-time many-one reduction is difficult (Murray and Williams, 2015) in the sense that it implies ZPP $\neq$ EXP, which is a ... more >>>

John Hitchcock, Hadi Shafei

We study the polynomial-time autoreducibility of NP-complete sets and obtain separations under strong hypotheses for NP. Assuming there is a p-generic set in NP, we show the following:

- For every $k \geq 2$, there is a $k$-T-complete set for NP that is $k$-T autoreducible, but is not $k$-tt autoreducible ... more >>>

John Hitchcock, Hadi Shafei

Nonuniformity is a central concept in computational complexity with powerful connections to circuit complexity and randomness. Nonuniform reductions have been used to study the isomorphism conjecture for NP and completeness for larger complexity classes. We study the power of nonuniform reductions for NP-completeness, obtaining both separations and upper bounds for ... 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 >>>

Rahul Ilango

The Minimum Circuit Size Problem (MCSP) asks whether a (given) Boolean function has a circuit of at most a (given) size. Despite over a half-century of study, we know relatively little about the computational complexity of MCSP. We do know that questions about the complexity of MCSP have significant ramifications ... 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 >>>

Shuichi Hirahara, Rahul Ilango, Bruno Loff

How difficult is it to compute the communication complexity of a two-argument total Boolean function $f:[N]\times[N]\to\{0,1\}$, when it is given as an $N\times N$ binary matrix? In 2009, Kushilevitz and Weinreb showed that this problem is cryptographically hard, but it is still open whether it is NP-hard.

In this ... more >>>

Halley Goldberg, Valentine Kabanets

A central open question within meta-complexity is that of NP-hardness of problems such as MCSP and MK$^t$P. Despite a large body of work giving consequences of and barriers for NP-hardness of these problems under (restricted) deterministic reductions, very little is known in the setting of randomized reductions. In this work, ... more >>>