Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z - Other

TR14-118 | 9th September 2014
Albert Atserias, Massimo Lauria, Jakob Nordström

Narrow Proofs May Be Maximally Long

We prove that there are 3-CNF formulas over n variables that can be refuted in resolution in width w but require resolution proofs of size n^Omega(w). This shows that the simple counting argument that any formula refutable in width w must have a proof in size n^O(w) is essentially tight. ... more >>>

TR05-066 | 4th June 2005
Jakob Nordström

Narrow Proofs May Be Spacious: Separating Space and Width in Resolution

Revisions: 2 , Comments: 1

The width of a resolution proof is the maximal number of literals in any clause of the proof. The space of a proof is the maximal number of memory cells used if the proof is only allowed to resolve on clauses kept in memory. Both of these measures have previously ... more >>>

TR06-005 | 13th December 2005
Edith Elkind, Leslie Ann Goldberg, Paul Goldberg

Nash Equilibria in Graphical Games on Trees Revisited

Graphical games have been proposed as a game-theoretic model of large-scale
distributed networks of non-cooperative agents. When the number of players is
large, and the underlying graph has low degree, they provide a concise way to
represent the players' payoffs. It has recently been shown that the problem of
finding ... more >>>

TR94-010 | 12th December 1994
Alexander Razborov, Steven Rudich

Natural Proofs

We introduce the notion of {\em natural} proof.
We argue that the known proofs of lower bounds on the complexity of explicit
Boolean functions in non-monotone models
fall within our definition of natural.
We show based on a hardness assumption
that natural proofs can't prove superpolynomial lower bounds ... more >>>

TR10-196 | 8th December 2010
Bin Fu

NE is not NP Turing Reducible to Nonexpoentially Dense NP Sets

A long standing open problem in the computational complexity theory
is to separate NE from BPP, which is a subclass of $NP_T (NP\cap P/poly)$.
In this paper, we show that $NE\not\subseteq NP_T (NP \cap$ Nonexponentially-Dense-Class),
where Nonexponentially-Dense-Class is the class of languages A without exponential density
(for ... more >>>

TR05-001 | 1st January 2005
Mario Szegedy

Near optimality of the priority sampling procedure

Based on experimental results N. Duffield, C. Lund and M. Thorup \cite{dlt2} conjectured
that the variance of their highly successful priority sampling procedure
is not larger than the variance of the threshold sampling procedure with sample size one smaller.
The conjecture's significance is that the latter procedure is provably optimal ... more >>>

TR03-001 | 8th January 2003
Vince Grolmusz

Near Quadratic Matrix Multiplication Modulo Composites

Comments: 1

We show how one can use non-prime-power, composite moduli for
computing representations of the product of two $n\times n$ matrices
using only $n^{2+o(1)}$ multiplications.

more >>>

TR15-081 | 12th May 2015
Mark Braverman, Ankit Garg, Young Kun Ko, Jieming Mao, Dave Touchette

Near-optimal bounds on bounded-round quantum communication complexity of disjointness

We prove a near optimal round-communication tradeoff for the two-party quantum communication complexity of disjointness. For protocols with $r$ rounds, we prove a lower bound of $\tilde{\Omega}(n/r)$ on the communication required for computing disjointness of input size $n$, which is optimal up to logarithmic factors. The previous best lower bound ... more >>>

TR09-133 | 9th December 2009
Anindya De, Thomas Vidick

Near-optimal extractors against quantum storage

We give near-optimal constructions of extractors secure against quantum bounded-storage adversaries. One instantiation gives the first such extractor to achieve an output length Theta(K-b), where K is the source's entropy and b the adversary's storage, depending linearly on the adversary's amount of storage, together with a poly-logarithmic seed length. Another ... more >>>

TR17-082 | 4th May 2017
Daniel Kane, Shachar Lovett, Shay Moran

Near-optimal linear decision trees for k-SUM and related problems

We construct near optimal linear decision trees for a variety of decision problems in combinatorics and discrete geometry.
For example, for any constant $k$, we construct linear decision trees that solve the $k$-SUM problem on $n$ elements using $O(n \log^2 n)$ linear queries.
Moreover, the queries we use are comparison ... more >>>

TR16-135 | 31st August 2016
Christoph Berkholz, Jakob Nordström

Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps

We prove near-optimal trade-offs for quantifier depth versus number of variables in first-order logic by exhibiting pairs of n-element structures that can be distinguished by a k-variable first-order sentence but where every such sentence requires quantifier depth at least n^?(k/log k). Our trade-offs also apply to first-order counting logic, and ... more >>>

TR00-005 | 17th January 2000
Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson

Near-Optimal Separation of Treelike and General Resolution

We present the best known separation
between tree-like and general resolution, improving
on the recent $\exp(n^\epsilon)$ separation of \cite{BEGJ98}.
This is done by constructing a natural family of contradictions, of
size $n$, that have $O(n)$-size resolution
refutations, but only $\exp (\Omega(n/\log n))$-size tree-like refutations.
This result ... more >>>

TR15-076 | 28th April 2015
Mahdi Cheraghchi, Piotr Indyk

Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform

For every fixed constant $\alpha > 0$, we design an algorithm for computing the $k$-sparse Walsh-Hadamard transform of an $N$-dimensional vector $x \in \mathbb{R}^N$ in time $k^{1+\alpha} (\log N)^{O(1)}$. Specifically, the algorithm is given query access to $x$ and computes a $k$-sparse $\tilde{x} \in \mathbb{R}^N$ satisfying $\|\tilde{x} - \hat{x}\|_1 \leq ... more >>>

TR15-155 | 22nd September 2015
Venkatesan Guruswami, Euiwoong Lee

Nearly Optimal NP-Hardness of Unique Coverage

The {\em Unique Coverage} problem, given a universe $V$ of elements and a collection $E$ of subsets of $V$, asks to find $S \subseteq V$ to maximize the number of $e \in E$ that intersects $S$ in {\em exactly one} element. When each $e \in E$ has cardinality at most ... more >>>

TR15-195 | 3rd December 2015
Robin Kothari

Nearly optimal separations between communication (or query) complexity and partitions

We show a nearly quadratic separation between deterministic communication complexity and the logarithm of the partition number, which is essentially optimal. This improves upon a recent power 1.5 separation of Göös, Pitassi, and Watson (FOCS 2015). In query complexity, we establish a nearly quadratic separation between deterministic (and even randomized) ... more >>>

TR12-072 | 5th June 2012
Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco Servedio

Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces

The \emph{Chow parameters} of a Boolean function $f: \{-1,1\}^n \to \{-1,1\}$ are its $n+1$ degree-0 and degree-1 Fourier coefficients. It has been known since 1961 \cite{Chow:61, Tannenbaum:61} that the (exact values of the) Chow parameters of any linear threshold function $f$ uniquely specify $f$ within the space of all Boolean ... more >>>

TR10-093 | 3rd June 2010
Sourav Chakraborty, David García Soriano, Arie Matsliah

Nearly Tight Bounds for Testing Function Isomorphism

In this paper we study the problem of testing structural equivalence (isomorphism) between a pair of Boolean
functions $f,g:\zo^n \to \zo$. Our main focus is on the most studied case, where one of the functions is given (explicitly), and the other function can be queried.

We prove that for every ... more >>>

TR07-063 | 2nd July 2007
Tomas Feder, Carlos Subi

Nearly Tight Bounds on the Number of Hamiltonian Circuits of the Hypercube and Generalizations

We conjecture that for every perfect matching $M$ of the $d$-dimensional
$n$-vertex hypercube, $d\geq 2$, there exists a second perfect matching $M'$
such that the union of $M$ and $M'$ forms a Hamiltonian circuit of the
$d$-dimensional hypercube. We prove this conjecture in the case where there are
two dimensions ... more >>>

TR08-087 | 31st July 2008
Tomas Feder, Carlos Subi

Nearly Tight Bounds on the Number of Hamiltonian Circuits of the Hypercube and Generalizations (revised)

It has been shown that for every perfect matching $M$ of the $d$-dimensional
$n$-vertex hypercube, $d\geq 2, n=2^d$, there exists a second perfect matching
$M'$ such that the union of $M$ and $M'$ forms a Hamiltonian circuit of the
$d$-dimensional hypercube. We prove a generalization of a special case of ... more >>>

TR07-009 | 8th January 2007
Nathan Segerlind

Nearly-Exponential Size Lower Bounds for Symbolic Quantifier Elimination Algorithms and OBDD-Based Proofs of Unsatisfiability

Revisions: 1 , Comments: 1

We demonstrate a family of propositional formulas in conjunctive normal form
so that a formula of size $N$ requires size $2^{\Omega(\sqrt[7]{N/logN})}$
to refute using the tree-like OBDD refutation system of
Atserias, Kolaitis and Vardi
with respect to all variable orderings.
All known symbolic quantifier elimination algorithms for satisfiability
generate ... more >>>

TR15-026 | 21st February 2015
Siyao Guo, Ilan Komargodski

Negation-Limited Formulas

Revisions: 1

Understanding the power of negation gates is crucial to bridge the exponential gap between monotone and non-monotone computation. We focus on the model of formulas over the De Morgan basis and consider it in a negation-limited setting.

We prove that every formula that contains $t$ negation gates can be shrunk ... more >>>

TR96-037 | 14th June 1996
Stasys Jukna, Alexander Razborov

Neither Reading Few Bits Twice nor Reading Illegally Helps Much

We first consider so-called {\em $(1,+s)$-branching programs}
in which along every consistent path at most $s$ variables are tested
more than once. We prove that any such program computing a
characteristic function of a linear code $C$ has size at least
more >>>

TR02-051 | 16th July 2002
Chris Pollett

Nepomnjascij's Theorem and Independence Proofs in Bounded Arithmetic

The use of Nepomnjascij's Theorem in the proofs of independence results
for bounded arithmetic theories is investigated. Using this result and similar ideas, the following statements are proven: (1) At least one of S_1 or TLS does not prove the Matiyasevich-Davis-Robinson-Putnam Theorem and (2) TLS does not prove Sigma^b_{1,1}=Pi^b_{1,1}. Here ... more >>>

TR04-034 | 12th April 2004
April Rasala Lehman, Eric Lehman

Network Coding: Does the Model Need Tuning?

We consider the general network information flow problem, which was
introduced by Ahlswede et. al. We show a periodicity effect: for
every integer m greater than 1, there exists an instance of the
network information flow problem that admits a solution if and only if
the alphabet size is a ... more >>>

TR96-031 | 30th April 1996

Networks of Spiking Neurons: The Third Generation of Neural Network Models

The computational power of formal models for
networks of spiking neurons is compared with
that of other neural network models based on
McCulloch Pitts neurons (i.e. threshold gates)
respectively sigmoidal gates. In particular it
is shown that networks of spiking neurons are
... more >>>

TR01-071 | 24th October 2001
Robert Albin Legenstein

Neural Circuits for Pattern Recognition with Small Total Wire Length

One of the most basic pattern recognition problems is whether a
certain local feature occurs in some linear array to the left of
some other local feature. We construct in this article circuits that
solve this problem with an asymptotically optimal number of
threshold gates. Furthermore it is shown that ... more >>>

TR94-017 | 12th December 1994

Neural Nets with Superlinear VC-Dimension

It has been known for quite a while that the Vapnik-Chervonenkis dimension
(VC-dimension) of a feedforward neural net with linear threshold gates is at
most O(w log w), where w is the total number of weights in the neural net.
We show in this paper that this bound is in ... more >>>

TR01-045 | 26th April 2001
Michael Schmitt

Neural Networks with Local Receptive Fields and Superlinear VC Dimension

Local receptive field neurons comprise such well-known and widely
used unit types as radial basis function neurons and neurons with
center-surround receptive field. We study the Vapnik-Chervonenkis
(VC) dimension of feedforward neural networks with one hidden layer
of these units. For several variants of local receptive field
neurons we show ... more >>>

TR00-031 | 31st May 2000
Eduardo D. Sontag

Neural Systems as Nonlinear Filters

Experimental data show that biological synapses behave quite
differently from the symbolic synapses in all common artificial
neural network models. Biological synapses are dynamic, i.e., their
``weight'' changes on a short time scale by several hundred percent
in dependence of the past input to the synapse. ... more >>>

TR12-106 | 27th August 2012
Alan Guo, Madhu Sudan

New affine-invariant codes from lifting

Comments: 1

In this work we explore error-correcting codes derived from
the ``lifting'' of ``affine-invariant'' codes.
Affine-invariant codes are simply linear codes whose coordinates
are a vector space over a field and which are invariant under
affine-transformations of the coordinate space. Lifting takes codes
defined over a vector space of small dimension ... more >>>

TR12-149 | 8th November 2012
Alan Guo, Swastik Kopparty, Madhu Sudan

New affine-invariant codes from lifting

Comments: 1

In this work we explore error-correcting codes derived from
the ``lifting'' of ``affine-invariant'' codes.
Affine-invariant codes are simply linear codes whose coordinates
are a vector space over a field and which are invariant under
affine-transformations of the coordinate space. Lifting takes codes
defined over a vector space of small dimension ... more >>>

TR13-108 | 9th August 2013
Rahul Santhanam, Ryan Williams

New Algorithms for QBF Satisfiability and Implications for Circuit Complexity

Revisions: 1

We revisit the complexity of the satisfiability problem for quantified Boolean formulas. We show that satisfiability
of quantified CNFs of size $\poly(n)$ on $n$ variables with $O(1)$
quantifier blocks can be solved in time $2^{n-n^{\Omega(1)}}$ by zero-error
randomized algorithms. This is the first known improvement over brute force search in ... more >>>

TR95-030 | 20th June 1995
Marek Karpinski, Alexander Zelikovsky

New Approximation Algorithms for the Steiner Tree Problems

The Steiner tree problem asks for the shortest tree connecting
a given set of terminal points in a metric space. We design
new approximation algorithms for the Steiner tree problems
using a novel technique of choosing Steiner points in dependence
on the possible deviation from ... more >>>

TR00-046 | 19th June 2000
Philipp Woelfel

New Bounds on the OBDD-Size of Integer Multiplication via Universal Hashing

Ordered binary decision diagrams (OBDDs) belong to the most important
representation types for Boolean functions. Although they allow
important operations such as satisfiability test and equality test to
be performed efficiently, their limitation lies in the fact, that they
may require exponential size for important functions. Bryant ... more >>>

TR06-108 | 24th August 2006
Dan Gutfreund, Amnon Ta-Shma

New connections between derandomization, worst-case complexity and average-case complexity

We show that a mild derandomization assumption together with the
worst-case hardness of NP implies the average-case hardness of a
language in non-deterministic quasi-polynomial time. Previously such
connections were only known for high classes such as EXP and

There has been a long line of research trying to explain ... more >>>

TR06-097 | 9th August 2006
Emanuele Viola

New correlation bounds for GF(2) polynomials using Gowers uniformity

We study the correlation between low-degree GF(2) polynomials p and explicit functions. Our main results are the following:

(I) We prove that the Mod_m unction on n bits has correlation at most exp(-Omega(n/4^d)) with any GF(2) polynomial of degree d, for any fixed odd integer m. This improves on the ... more >>>

TR09-090 | 6th October 2009
Russell Impagliazzo, Valentine Kabanets, Avi Wigderson

New Direct-Product Testers and 2-Query PCPs

The “direct product code” of a function f gives its values on all k-tuples (f(x1), . . . , f(xk)).
This basic construct underlies “hardness amplification” in cryptography, circuit complexity and
PCPs. Goldreich and Safra [GS00] pioneered its local testing and its PCP application. A recent
result by Dinur and ... more >>>

TR15-151 | 14th September 2015
Eshan Chattopadhyay, David Zuckerman

New Extractors for Interleaved Sources

Revisions: 1

We study how to extract randomness from a $C$-interleaved source, that is, a source comprised of $C$ independent sources whose bits or symbols are interleaved. We describe a simple approach for constructing such extractors that yields:

(1) For some $\delta>0, c > 0$,
explicit extractors for $2$-interleaved sources on $\{ ... more >>>

TR16-029 | 7th March 2016
Joshua Brakensiek, Venkatesan Guruswami

New hardness results for graph and hypergraph colorings

Finding a proper coloring of a $t$-colorable graph $G$ with $t$ colors is a classic NP-hard problem when $t\ge 3$. In this work, we investigate the approximate coloring problem in which the objective is to find a proper $c$-coloring of $G$ where $c \ge t$. We show that for all ... more >>>

TR16-159 | 18th October 2016
Daniel Grier, Luke Schaeffer

New Hardness Results for the Permanent Using Linear Optics

In 2011, Aaronson gave a striking proof, based on quantum linear optics, showing that the problem of computing the permanent of a matrix is #P-hard. Aaronson's proof led naturally to hardness of approximation results for the permanent, and it was arguably simpler than Valiant's seminal proof of the same fact ... more >>>

TR13-045 | 26th March 2013
Marek Karpinski, Michael Lampis, Richard Schmied

New Inapproximability Bounds for TSP

In this paper, we study the approximability of the metric Traveling Salesman Problem, one of the most widely studied problems in combinatorial optimization. Currently, the best known hardness of approximation bounds are 185/184 for the symmetric case (due to Lampis) and 117/116 for the asymmetric case (due to Papadimitriou and ... more >>>

TR12-147 | 7th November 2012
Xin Li

New Independent Source Extractors with Exponential Improvement

We study the problem of constructing explicit extractors for independent general weak random sources. For weak sources on $n$ bits with min-entropy $k$, perviously the best known extractor needs to use at least $\frac{\log n}{\log k}$ independent sources \cite{Rao06, BarakRSW06}. In this paper we give a new extractor that only ... more >>>

TR17-073 | 28th April 2017
Eric Allender, Shuichi Hirahara

New Insights on the (Non)-Hardness of Circuit Minimization and Related Problems

The Minimum Circuit Size Problem (MCSP) and a related problem (MKTP) that deals with time-bounded Kolmogorov complexity are prominent candidates for NP-intermediate status. We show that, under very modest cryptographic assumptions (such as the existence of one-way functions), the problem of approximating the minimum circuit size (or time-bounded Kolmogorov complexity) ... more >>>

TR12-112 | 7th September 2012
Andrew Drucker

New Limits to Classical and Quantum Instance Compression

Revisions: 3

Given an instance of a hard decision problem, a limited goal is to $compress$ that instance into a smaller, equivalent instance of a second problem. As one example, consider the problem where, given Boolean formulas $\psi^1, \ldots, \psi^t$, we must determine if at least one $\psi^j$ is satisfiable. An $OR-compression ... more >>>

TR06-127 | 7th October 2006
Sergey Yekhanin

New Locally Decodable Codes and Private Information Retrieval Schemes

A q-query Locally Decodable Code (LDC) encodes an n-bit message
x as an N-bit codeword C(x), such that one can
probabilistically recover any bit x_i of the message
by querying only q bits of the codeword C(x), even after
some constant fraction of codeword bits has been corrupted.

We give ... more >>>

TR95-002 | 1st January 1995
Detlef Sieling

New Lower Bounds and Hierarchy Results for Restricted Branching Programs

In unrestricted branching programs all variables may be tested
arbitrarily often on each path. But exponential lower bounds are only
known, if on each path the number of tests of each variable is bounded
(Borodin, Razborov and Smolensky (1993)). We examine branching programs
in which for each path the ... more >>>

TR07-006 | 12th January 2007
David P. Woodruff

New Lower Bounds for General Locally Decodable Codes

For any odd integer q > 1, we improve the lower bound for general q-query locally decodable codes C: {0,1}^n -> {0,1}^m from m = Omega(n/log n)^{(q+1)/(q-1)} to m = Omega(n^{(q+1)/(q-1)})/log n. For example, for q = 3 we improve the previous bound from Omega(n^2/log^2 n) to Omega(n^2/log n). For ... more >>>

TR12-034 | 5th April 2012
Abhishek Bhowmick, Zeev Dvir, Shachar Lovett

New Lower Bounds for Matching Vector Codes

Revisions: 5

We prove new lower bounds on the encoding length of Matching Vector (MV) codes. These recently discovered families of Locally Decodable Codes (LDCs) originate in the works of Yekhanin [Yek] and Efremenko [Efr] and are the only known families of LDCs with a constant number of queries and sub-exponential encoding ... more >>>

TR13-015 | 18th January 2013
Iordanis Kerenidis, Mathieu Laurière, David Xiao

New lower bounds for privacy in communication protocols

Communication complexity is a central model of computation introduced by Yao in 1979, where
two players, Alice and Bob, receive inputs x and y respectively and want to compute $f(x; y)$ for some fixed
function f with the least amount of communication. Recently people have revisited the question of the ... more >>>

TR02-060 | 15th July 2002
Ke Yang

New Lower Bounds for Statistical Query Learning

We prove two lower bounds on the Statistical Query (SQ) learning
model. The first lower bound is on weak-learning. We prove that for a
concept class of SQ-dimension $d$, a running time of
$\Omega(d/\log d)$ is needed. The SQ-dimension of a concept class is
defined to be the maximum number ... more >>>

TR17-076 | 21st April 2017
Tianren Liu, Vinod Vaikuntanathan, Hoeteck Wee

New Protocols for Conditional Disclosure of Secrets (and More)

Revisions: 2

We present new protocols for conditional disclosure of secrets (CDS),
where two parties want to disclose a secret to a third party if and
only if their respective inputs satisfy some predicate.

- For general predicates $\text{pred} : [N] \times [N] \rightarrow \{0,1\}$,
we present two protocols that achieve ... more >>>

TR16-167 | 1st November 2016
Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao

New Randomized Data Structure Lower Bounds for Dynamic Graph Connectivity

Revisions: 1

The problem of dynamic connectivity in graphs has been extensively studied in the cell probe model. The task is to design a data structure that supports addition of edges and checks connectivity between arbitrary pair of vertices. Let $w, t_q, t_u$ denote the cell width, expected query time and worst ... more >>>

TR06-059 | 3rd May 2006
Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami

New Results for Learning Noisy Parities and Halfspaces

We address well-studied problems concerning the learnability of parities and halfspaces in the presence of classification noise.

Learning of parities under the uniform distribution with random classification noise,also called the noisy parity problem is a famous open problem in computational learning. We reduce a number of basic problems regarding ... more >>>

TR08-025 | 3rd January 2008
Vikraman Arvind, Partha Mukhopadhyay, Srikanth Srinivasan

New results on Noncommutative and Commutative Polynomial Identity Testing

Revisions: 2

Using ideas from automata theory we design a new efficient
(deterministic) identity test for the \emph{noncommutative}
polynomial identity testing problem (first introduced and studied by
Raz-Shpilka in 2005 and Bogdanov-Wee in 2005). More precisely,
given as input a noncommutative
circuit $C(x_1,\cdots,x_n)$ computing a ... more >>>

TR04-107 | 24th November 2004
Ingo Wegener, Philipp Woelfel

New Results on the Complexity of the Middle Bit of Multiplication

Revisions: 1

It is well known that the hardest bit of integer multiplication is the middle bit, i.e. MUL_{n-1,n}.
This paper contains several new results on its complexity.
First, the size s of randomized read-k branching programs, or, equivalently, its space (log s) is investigated.
A randomized algorithm for MUL_{n-1,n} with k=O(log ... more >>>

TR11-116 | 17th August 2011
Andris Ambainis, Xiaoming Sun

New separation between $s(f)$ and $bs(f)$

In this note we give a new separation between sensitivity and block sensitivity of Boolean functions: $bs(f)=\frac{2}{3}s(f)^2-\frac{1}{3}s(f)$.

more >>>

TR11-024 | 25th February 2011
Rahul Jain

New strong direct product results in communication complexity

We show two new direct product results in two different models of communication complexity. Our first result is in the model of one-way public-coin model. Let $f \subseteq X \times Y \times Z $ be a relation and $\epsilon >0$ be a constant. Let $R^{1,pub}_{\epsilon}(f)$ represent the communication complexity of ... more >>>

TR14-035 | 13th March 2014
Diptarka Chakraborty, A. Pavan, Raghunath Tewari, Vinodchandran Variyam, Lin Yang

New Time-Space Upperbounds for Directed Reachability in High-genus and $H$-minor-free Graphs.

We obtain the following new simultaneous time-space upper bounds for the directed reachability problem.
(1) A polynomial-time,
$\tilde{O}(n^{2/3}g^{1/3})$-space algorithm for directed graphs embedded on orientable surfaces of genus $g$. (2) A polynomial-time, $\tilde{O}(n^{2/3})$-space algorithm for all $H$-minor-free graphs given the tree decomposition, and (3) for $K_{3, 3}$-free and ... more >>>

TR00-037 | 26th May 2000
Jens Gramm, Edward Hirsch, Rolf Niedermeier, Peter Rossmanith

New Worst-Case Upper Bounds for MAX-2-SAT with Application to MAX-CUT

The maximum 2-satisfiability problem (MAX-2-SAT) is:
given a Boolean formula in $2$-CNF, find a truth
assignment that satisfies the maximum possible number
of its clauses. MAX-2-SAT is MAXSNP-complete.
Recently, this problem received much attention in the
contexts of approximation (polynomial-time) algorithms
... more >>>

TR11-017 | 8th February 2011
Fengming Wang

NEXP does not have non-uniform quasi-polynomial-size ACC circuits of o(loglog n) depth

$\mbox{ACC}_m$ circuits are circuits consisting of unbounded fan-in AND, OR and MOD_m gates and unary NOT gates, where m is a fixed integer. We show that there exists a language in non-deterministic exponential time which can not be computed by any non-uniform family of $\mbox{ACC}_m$ circuits of quasi-polynomial size and ... more >>>

TR10-046 | 22nd March 2010
Ján Pich

Nisan-Wigderson generators in proof systems with forms of interpolation

We prove that the Nisan-Wigderson generators based on computationally hard functions and suitable matrices are hard for propositional proof systems that admit feasible interpolation.

more >>>

TR08-004 | 2nd January 2008
Zeev Dvir, Amir Shpilka

Noisy Interpolating Sets for Low Degree Polynomials

A Noisy Interpolating Set (NIS) for degree $d$ polynomials is a
set $S \subseteq \F^n$, where $\F$ is a finite field, such that
any degree $d$ polynomial $q \in \F[x_1,\ldots,x_n]$ can be
efficiently interpolated from its values on $S$, even if an
adversary corrupts a constant fraction of the values. ... more >>>

TR11-044 | 25th March 2011
Shubhangi Saraf, Sergey Yekhanin

Noisy Interpolation of Sparse Polynomials, and Applications

Let $f\in F_q[x]$ be a polynomial of degree $d\leq q/2.$ It is well-known that $f$ can be uniquely recovered from its values at some $2d$ points even after some small fraction of the values are corrupted. In this paper we establish a similar result for sparse polynomials. We show that ... more >>>

TR16-021 | 11th February 2016
Shachar Lovett, Jiapeng Zhang

Noisy Population Recovery from Unknown Noise

The noisy population recovery problem is a statistical inference problem, which is a special case of the problem of learning mixtures of product distributions. Given an unknown distribution on $n$-bit strings with support of size $k$, and given access only to noisy samples from it, where each bit is flipped ... more >>>

TR16-026 | 20th February 2016
Anindya De, Michael Saks, Sijian Tang

Noisy population recovery in polynomial time

In the noisy population recovery problem of Dvir et al., the goal is to learn
an unknown distribution $f$ on binary strings of length $n$ from noisy samples. For some parameter $\mu \in [0,1]$,
a noisy sample is generated by flipping each coordinate of a sample from $f$ independently with
more >>>

TR04-052 | 14th June 2004
Michael Ben Or, Don Coppersmith, Michael Luby, Ronitt Rubinfeld

Non-Abelian Homomorphism Testing, and Distributions Close to their Self-Convolutions

In this paper, we study two questions related to
the problem of testing whether a function is close to a homomorphism.
For two finite groups $G,H$ (not necessarily Abelian),
an arbitrary map $f:G \rightarrow H$, and a parameter $0 < \epsilon <1$,
say that $f$ is $\epsilon$-close to a homomorphism ... more >>>

TR17-050 | 15th March 2017
Joe Boninger, Joshua Brody, Owen Kephart

Non-Adaptive Data Structure Bounds for Dynamic Predecessor Search

In this work, we continue the examination of the role non-adaptivity} plays in maintaining dynamic data structures, initiated by Brody and Larsen [BL15].. We consider nonadaptive data structures for predecessor search in the w-bit cell probe model. Predecessor search is one of the most well-studied data structure problems. For this ... more >>>

TR17-040 | 4th March 2017
Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao

Non-Adaptive Data Structure Lower Bounds for Median and Predecessor Search from Sunflowers

Revisions: 2

We prove new cell-probe lower bounds for data structures that maintain a subset of $\{1,2,...,n\}$, and compute the median of the set. The data structure is said to handle insertions non-adaptively if the locations of memory accessed depend only on the element being inserted, and not on the contents of ... more >>>

TR02-071 | 6th June 2002
Bruno Codenotti, Igor E. Shparlinski

Non-approximability of the Permanent of Structured Matrices over Finite Fields

We show that for several natural classes of ``structured'' matrices, including symmetric, circulant, Hankel and Toeplitz matrices, approximating the permanent modulo a prime $p$ is as hard as computing the exact value. Results of this kind are well known for the class of arbitrary matrices; however the techniques used do ... more >>>

TR13-063 | 19th April 2013
Dung Nguyen, Alan Selman

Non-autoreducible Sets for NEXP

We investigate autoreducibility properties of complete sets for $\cNEXP$ under different polynomial reductions.
Specifically, we show under some polynomial reductions that there is are complete sets for
$\cNEXP$ that are not autoreducible. We obtain the following results:
- There is a $\reduction{p}{tt}$-complete set for $\cNEXP$ that is not $\reduction{p}{btt}$-autoreducible.
more >>>

TR95-043 | 14th September 1995
Eric Allender, Jia Jiao, Meena Mahajan, V. Vinay

Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds

We investigate the phenomenon of depth-reduction in commutative
and non-commutative arithmetic circuits. We prove that in the
commutative setting, uniform semi-unbounded arithmetic circuits of
logarithmic depth are as powerful as uniform arithmetic circuits of
polynomial degree; earlier proofs did not work in the ... more >>>

TR10-021 | 21st February 2010
Pavel Hrubes, Avi Wigderson, Amir Yehudayoff

Non-commutative circuits and the sum-of-squares problem

We initiate a direction for proving lower bounds on the size of non-commutative arithmetic circuits. This direction is based on a connection between lower bounds on the size of \emph{non-commutative} arithmetic circuits and a problem about \emph{commutative} degree four polynomials, the classical sum-of-squares problem: find the smallest $n$ such that ... more >>>

TR16-094 | 6th June 2016
Guillaume Lagarde, Guillaume Malod

Non-commutative computations: lower bounds and polynomial identity testing

Comments: 1

In the setting of non-commutative arithmetic computations, we define a class of circuits that gener-
alize algebraic branching programs (ABP). This model is called unambiguous because it captures the
polynomials in which all monomials are computed in a similar way (that is, all the parse trees are iso-
We ... more >>>

TR97-048 | 13th October 1997
Soren Riis, Meera Sitharam

Non-constant Degree Lower Bounds imply linear Degree Lower Bounds

The semantics of decision problems are always essentially independent of the
underlying representation. Thus the space of input data (under appropriate
indexing) is closed
under action of the symmetrical group $S_n$ (for a specific data-size)
and the input-output relation is closed under the action of $S_n$.
more >>>

TR13-078 | 28th May 2013
Tom Gur, Ron Rothblum

Non-Interactive Proofs of Proximity

Revisions: 1

We initiate a study of non-interactive proofs of proximity. These proof-systems consist of a verifier that wishes to ascertain the validity of a given statement, using a short (sublinear length) explicitly given proof, and a sublinear number of queries to its input. Since the verifier cannot even read the entire ... more >>>

TR16-077 | 12th May 2016
Zvika Brakerski, Justin Holmgren, Yael Tauman Kalai

Non-Interactive RAM and Batch NP Delegation from any PIR

Revisions: 1

We present an adaptive and non-interactive protocol for verifying arbitrary efficient computations in fixed polynomial time. Our protocol is computationally sound and can be based on any computational PIR scheme, which in turn can be based on standard polynomial-time cryptographic assumptions (e.g. the worst case hardness of polynomial-factor approximation of ... more >>>

TR01-052 | 26th April 2001
Mikhail V. Vyugin, Vladimir Vyugin

Non-linear Inequalities between Predictive and Kolmogorov Complexity

Predictive complexity is a generalization of Kolmogorov complexity
which gives a lower bound to ability of any algorithm to predict
elements of a sequence of outcomes. A variety of types of loss
functions makes it interesting to study relations between corresponding
predictive complexities.

Non-linear inequalities between predictive complexity of ... more >>>

TR08-076 | 17th June 2008
Ryan Williams

Non-Linear Time Lower Bound for (Succinct) Quantified Boolean Formulas

We prove a model-independent non-linear time lower bound for a slight generalization of the quantified Boolean formula problem (QBF). In particular, we give a reduction from arbitrary languages in alternating time t(n) to QBFs describable in O(t(n)) bits by a reasonable (polynomially) succinct encoding. The reduction works for many reasonable ... more >>>

TR14-102 | 4th August 2014
Eshan Chattopadhyay, David Zuckerman

Non-Malleable Codes Against Constant Split-State Tampering

Non-malleable codes were introduced by Dziembowski, Pietrzak and Wichs \cite{DPW10} as an elegant generalization of the classical notions of error detection, where the corruption of a codeword is viewed as a tampering function acting on it. Informally, a non-malleable code with respect to a family of tampering functions $\mathcal{F}$ consists ... more >>>

TR16-180 | 15th November 2016
Eshan Chattopadhyay, Xin Li

Non-Malleable Codes and Extractors for Small-Depth Circuits, and Affine Functions

Non-malleable codes were introduced by Dziembowski, Pietrzak and Wichs as an elegant relaxation of error correcting codes, where the motivation is to handle more general forms of tampering while still providing meaningful guarantees. This has led to many elegant constructions and applications in cryptography. However, most works so far only ... more >>>

TR13-081 | 6th June 2013
Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett

Non-malleable Codes from Additive Combinatorics

Non-malleable codes provide a useful and meaningful security guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a ... more >>>

TR13-121 | 4th September 2013
Mahdi Cheraghchi, Venkatesan Guruswami

Non-Malleable Coding Against Bit-wise and Split-State Tampering

Revisions: 1

Non-malleable coding, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), aims for protecting the integrity of information against tampering attacks in situations where error-detection is impossible. Intuitively, information encoded by a non-malleable code either decodes to the original message or, in presence of any tampering, to an unrelated message. Non-malleable ... more >>>

TR15-183 | 16th November 2015
Gil Cohen

Non-Malleable Extractors - New Tools and Improved Constructions

A non-malleable extractor is a seeded extractor with a very strong guarantee - the output of a non-malleable extractor obtained using a typical seed is close to uniform even conditioned on the output obtained using any other seed. The first contribution of this paper consists of two new and improved ... more >>>

TR15-075 | 29th April 2015
Eshan Chattopadhyay, Vipul Goyal, Xin Li

Non-Malleable Extractors and Codes, with their Many Tampered Extensions

Revisions: 1

Randomness extractors and error correcting codes are fundamental objects in computer science. Recently, there have been several natural generalizations of these objects, in the context and study of tamper resilient cryptography. These are \emph{seeded non-malleable extractors}, introduced by Dodis and Wichs \cite{DW09}; \emph{seedless non-malleable extractors}, introduced by Cheraghchi and Guruswami ... more >>>

TR11-166 | 4th December 2011
Xin Li

Non-Malleable Extractors for Entropy Rate $<1/2$

Revisions: 1

Dodis and Wichs \cite{DW09} introduced the notion of a non-malleable extractor to study the problem of privacy amplification with an active adversary. A non-malleable extractor is a much stronger version of a strong extractor. Given a weakly-random string $x$ and a uniformly random seed $y$ as the inputs, the non-malleable ... more >>>

TR16-030 | 7th March 2016
Gil Cohen

Non-Malleable Extractors with Logarithmic Seeds

We construct non-malleable extractors with seed length $d = O(\log{n}+\log^{3}(1/\epsilon))$ for $n$-bit sources with min-entropy $k = \Omega(d)$, where $\epsilon$ is the error guarantee. In particular, the seed length is logarithmic in $n$ for $\epsilon> 2^{-(\log{n})^{1/3}}$. This improves upon existing constructions that either require super-logarithmic seed length even for constant ... more >>>

TR11-096 | 2nd July 2011
Gil Cohen, Ran Raz, Gil Segev

Non-Malleable Extractors with Short Seeds and Applications to Privacy Amplification

Motivated by the classical problem of privacy amplification, Dodis and Wichs (STOC '09) introduced the notion of a non-malleable extractor, significantly strengthening the notion of a strong extractor. A non-malleable extractor is a function $nmExt : \{0,1\}^n \times \{0,1\}^d \rightarrow \{0,1\}^m$ that takes two inputs: a weak source $W$ and ... more >>>

TR14-128 | 10th October 2014
Divesh Aggarwal, Yevgeniy Dodis, Tomasz Kazana , Maciej Obremski

Non-malleable Reductions and Applications

Revisions: 3

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs~\cite{DPW10}, provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either ... more >>>

TR06-090 | 22nd June 2006
Christian Glaßer, Alan L. Selman, Stephen Travers, Liyu Zhang

Non-Mitotic Sets

<p> We study the question of the existence of non-mitotic sets in NP. We show under various hypotheses that:</p>
<li>1-tt-mitoticity and m-mitoticity differ on NP.</li>
<li>1-tt-reducibility and m-reducibility differ on NP.</li>
<li>There exist non-T-autoreducible sets in NP (by a result from Ambos-Spies, these sets are neither ... more >>>

TR04-054 | 5th June 2004
Andrej Muchnik, Alexander Shen, Nikolay Vereshchagin, Mikhail V. Vyugin

Non-reducible descriptions for conditional Kolmogorov complexity

Let a program p on input a output b. We are looking for a
shorter program p' having the same property (p'(a)=b). In
addition, we want p' to be simple conditional to p (this
means that the conditional Kolmogorov complexity K(p'|p) is
negligible). In the present paper, we prove that ... more >>>

TR09-113 | 9th November 2009
Anindya De, Luca Trevisan, Madhur Tulsiani

Non-uniform attacks against one-way functions and PRGs

We study the power of non-uniform attacks against one-way
functions and pseudorandom generators.

Fiat and Naor show that for every function
$f: [N]\to [N]$
there is an algorithm that inverts $f$ everywhere using
(ignoring lower order factors)
time, space and advice at most $N^{3/4}$.

We show that ... more >>>

TR02-057 | 19th September 2002
Richard J. Lipton, Anastasios Viglas

Non-uniform Depth of Polynomial Time and Space Simulations

We discuss some connections between polynomial time and non-uniform, small depth circuits. A connection is shown with simulating deterministic time in small space. The well known result of Hopcroft, Paul and Valiant showing that space is more powerful than time can be improved, by making an assumption about the connection ... more >>>

TR05-154 | 11th December 2005
Albert Atserias

Non-Uniform Hardness for NP via Black-Box Adversaries

We may believe SAT does not have small Boolean circuits.
But is it possible that some language with small circuits
looks indistiguishable from SAT to every polynomial-time
bounded adversary? We rule out this possibility. More
precisely, assuming SAT does not have small circuits, we
show that ... more >>>

TR14-175 | 15th December 2014
Abhishek Bhowmick, Shachar Lovett

Nonclassical polynomials as a barrier to polynomial lower bounds

The problem of constructing explicit functions which cannot be approximated by low degree polynomials has been extensively studied in computational complexity, motivated by applications in circuit lower bounds, pseudo-randomness, constructions of Ramsey graphs and locally decodable codes. Still, most of the known lower bounds become trivial for polynomials of ... more >>>

TR14-105 | 9th August 2014
Craig Gentry

Noncommutative Determinant is Hard: A Simple Proof Using an Extension of Barrington’s Theorem

Comments: 1

We show that, for many noncommutative algebras A, the hardness of computing the determinant of matrices over A follows almost immediately from Barrington’s Theorem. Barrington showed how to express a NC1 circuit as a product program over any non-solvable group. We construct a simple matrix directly from Barrington’s product program ... more >>>

TR15-124 | 3rd August 2015
Vikraman Arvind, Pushkar Joglekar, Raja S

Noncommutative Valiant's Classes: Structure and Complete Problems

Revisions: 1

In this paper we explore the noncommutative analogues, $\mathrm{VP}_{nc}$ and
$\mathrm{VNP}_{nc}$, of Valiant's algebraic complexity classes and show some
striking connections to classical formal language theory. Our main
results are the following:

(1) We show that Dyck polynomials (defined from the Dyck languages of formal language theory) are complete for ... more >>>

TR12-142 | 3rd November 2012
Markus Bläser

Noncommutativity makes determinants hard

We consider the complexity of computing the determinant over arbitrary finite-dimensional algebras. We first consider the case that $A$ is fixed. We obtain the following dichotomy: If $A/rad(A)$ is noncommutative, then computing the determinant over $A$ is hard. ``Hard'' here means $\#P$-hard over fields of characteristic $0$ and $ModP_p$-hard over ... more >>>

TR12-080 | 18th June 2012
Baris Aydinlioglu, Dieter van Melkebeek

Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin Games

In several settings derandomization is known to follow from circuit lower bounds that themselves are equivalent to the existence of pseudorandom generators. This leaves open the question whether derandomization implies the circuit lower bounds that are known to imply it, i.e., whether the ability to derandomize in *any* way implies ... more >>>

TR15-148 | 9th September 2015
Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mikhailin, Ramamohan Paturi, Stefan Schneider

Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility

Revisions: 1

We introduce the Nondeterministic Strong Exponential Time Hypothesis
(NSETH) as a natural extension of the Strong Exponential Time
Hypothesis (SETH). We show that both refuting and proving
NSETH would have interesting consequences.

In particular we show that disproving NSETH would ... more >>>

TR08-075 | 7th July 2008
Olaf Beyersdorff, Johannes Köbler, Sebastian Müller

Nondeterministic Instance Complexity and Proof Systems with Advice

Motivated by strong Karp-Lipton collapse results in bounded arithmetic, Cook and Krajicek have recently introduced the notion of propositional proof systems with advice.
In this paper we investigate the following question: Do there exist polynomially bounded proof systems with advice for arbitrary languages?
Depending on the complexity of the ... more >>>

TR13-126 | 11th September 2013
Arman Fazeli, Shachar Lovett, Alex Vardy

Nontrivial t-designs over finite fields exist for all t

A $t$-$(n,k,\lambda)$ design over $\mathbb{F}_q$ is a collection of $k$-dimensional subspaces of $\mathbb{F}_q^n$, ($k$-subspaces, for short), called blocks, such that each $t$-dimensional subspace of $\mathbb{F}_q^n$ is contained in exactly $\lambda$ blocks. Such $t$-designs over $\mathbb{F}_q$ are the $q$-analogs of conventional combinatorial designs. Nontrivial $t$-$(n,k,\lambda)$ designs over $\mathbb{F}_q$ are currently known ... more >>>

TR15-138 | 25th August 2015
Michal Koucky

Nonuniform catalytic space and the direct sum for space

Revisions: 1

This paper initiates the study of $k$-catalytic branching programs, a nonuniform model of computation that is the counterpart to the uniform catalytic space model of Buhrman, Cleve, Koucky, Loff and Speelman (STOC 2014). A $k$-catalytic branching program computes $k$ boolean functions simultaneously on the same $n$-bit input. Each function has ... more >>>

TR06-064 | 1st May 2006
Moses Charikar, Konstantin Makarychev, Yury Makarychev

Note on MAX 2SAT

In this note we present an approximation algorithm for MAX 2SAT that given a (1 - epsilon) satisfiable instance finds an assignment of variables satisfying a 1 - O(sqrt{epsilon}) fraction of all constraints. This result is optimal assuming the Unique Games Conjecture.

The best previously known result, due ... more >>>

TR95-014 | 27th January 1995
U. Faigle, W. Kern, M. Streng

Note On the Computational Complexity of $j$-Radii of Polytopes in ${\Re}^n$

We show that, for fixed dimension $n$, the approximation of
inner and outer $j$-radii of polytopes in ${\Re}^n$, endowed
with the Euclidean norm, is polynomial.

more >>>

TR97-058 | 2nd December 1997
Oded Goldreich

Notes on Levin's Theory of Average-Case Complexity.

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.

more >>>

TR12-100 | 23rd July 2012
Tomas Jirotka

NP Search Problems

The thesis summarizes known results in the field of NP search problems. We discuss the complexity of integer factoring in detail, and we propose new results which place the problem in known classes and aim to separate it from PLS in some sense. Furthermore, we define several new search problems.

more >>>

TR04-103 | 19th November 2004
Lance Fortnow, Adam Klivans

NP with Small Advice

We prove a new equivalence between the non-uniform and uniform complexity of exponential time. We show that EXP in NP/log if and only if EXP = P^NP|| (polynomial time with non-adaptive queries to SAT). Our equivalence makes use of a recent result due to Shaltiel and Umans showing EXP in ... more >>>

TR05-026 | 15th February 2005
Scott Aaronson

NP-complete Problems and Physical Reality

Can NP-complete problems be solved efficiently in the physical universe?
I survey proposals including soap bubbles, protein folding, quantum
computing, quantum advice, quantum adiabatic algorithms,
quantum-mechanical nonlinearities, hidden variables, relativistic time
dilation, analog computing, Malament-Hogarth spacetimes, quantum
gravity, closed timelike curves, and "anthropic computing." The ... more >>>

TR08-022 | 9th January 2008
Harry Buhrman, John Hitchcock

NP-Hard Sets are Exponentially Dense Unless NP is contained in coNP/poly

We show that hard sets S for NP must have exponential density, i.e. |S<sub>=n</sub>| &#8805; 2<sup>n<sup>&#949;</sup></sup> for some &#949; > 0 and infinitely many n, unless coNP &#8838; NP\poly and the polynomial-time hierarchy collapses. This result holds for Turing reductions that make n<sup>1-&#949;</sup> queries.

In addition we study the instance ... more >>>

TR16-162 | 18th October 2016
Joshua Grochow

NP-hard sets are not sparse unless P=NP: An exposition of a simple proof of Mahaney's Theorem, with applications

Mahaney's Theorem states that, assuming P $\neq$ NP, no NP-hard set can have a polynomially bounded number of yes-instances at each input length. We give an exposition of a very simple unpublished proof of Manindra Agrawal whose ideas appear in Agrawal-Arvind ("Geometric sets of low information content," Theoret. Comp. Sci., ... more >>>

TR96-021 | 13th February 1996
Yongge Wang

NP-hard Sets Are Superterse unless NP Is Small

We show that the class of sets which can be polynomial
time truth table reduced to some $p$-superterse sets has
$p$-measure 0. Hence, no $P$-selective set is $\le_{tt}^p$-hard
for $E$. Also we give a partial affirmative answer to
the conjecture by Beigel, Kummer and ... more >>>

TR10-112 | 15th July 2010
Subhash Khot, Dana Moshkovitz

NP-Hardness of Approximately Solving Linear Equations Over Reals

In this paper, we consider the problem of approximately solving a system of homogeneous linear equations over reals, where each
equation contains at most three variables.

Since the all-zero assignment always satisfies all the equations exactly, we restrict the assignments to be ``non-trivial". Here is
an informal statement of our ... more >>>

TR16-176 | 9th November 2016
Venkata Gandikota, Badih Ghazi, Elena Grigorescu

NP-Hardness of Reed-Solomon Decoding, and the Prouhet-Tarry-Escott Problem

Establishing the complexity of {\em Bounded Distance Decoding} for Reed-Solomon codes is a fundamental open problem in coding theory, explicitly asked by Guruswami and Vardy (IEEE Trans. Inf. Theory, 2005). The problem is motivated by the large current gap between the regime when it is NP-hard, and the regime when ... more >>>

TR98-073 | 14th December 1998
Tomoyuki Yamakami, Andrew Chi-Chih Yao

NQP = co-C_{=}P

Revisions: 2

Adleman, DeMarrais, and Huang introduced the
nondeterministic quantum polynomial-time complexity class NQP as an
analogue of NP. It is known that, with restricted amplitudes, NQP is
characterized in terms of the classical counting complexity class
C_{=}P. In this paper we prove that, with unrestricted amplitudes,
NQP indeed coincides with the ... more >>>

ISSN 1433-8092 | Imprint