Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > A-Z > N:
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

N
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

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 >>>

TR19-126 | 19th September 2019
Irit Dinur, Roy Meshulam

#### Near Coverings and Cosystolic Expansion -- an example of topological property testing

We study the stability of covers of simplicial complexes. Given a map f:Y?X that satisfies almost all of the local conditions of being a cover, is it close to being a genuine cover of X? Complexes X for which this holds are called cover-stable. We show that this is equivalent ... more >>>

TR18-144 | 18th August 2018
Mert Saglam

#### Near log-convexity of measured heat in (discrete) time and consequences

Let $u,v \in \mathbb{R}^\Omega_+$ be positive unit vectors and $S\in\mathbb{R}^{\Omega\times\Omega}_+$ be a symmetric substochastic matrix. For an integer $t\ge 0$, let $m_t = \smash{\left\langle v,S^tu\right\rangle}$, which we view as the heat measured by $v$ after an initial heat configuration $u$ is let to diffuse for $t$ time steps according to ... 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

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 >>>

TR18-132 | 17th July 2018
Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse

#### Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits

Revisions: 2

The classical lemma of Ore-DeMillo-Lipton-Schwartz-Zippel states that any nonzero polynomial $f(x_1,\ldots, x_n)$ of degree at most $s$ will evaluate to a nonzero value at some point on a grid $S^n \subseteq \mathbb{F}^n$ with $|S| > s$. Thus, there is a deterministic polynomial identity test (PIT) for all degree-$s$ size-$s$ ... 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 >>>

TR22-150 | 7th November 2022
Aaron (Louie) Putterman, Edward Pyne

#### Near-Optimal Derandomization of Medium-Width Branching Programs

We give a deterministic white-box algorithm to estimate the expectation of a read-once branching program of length $n$ and width $w$ in space
$$\tilde{O}\left(\log n+\sqrt{\log n}\cdot\log w\right).$$
In particular, we obtain an almost optimal space $\tilde{O}(\log n)$ derandomization of programs up to width $w=2^{\sqrt{\log n}}$.
Previously, ... 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 >>>

TR19-003 | 2nd January 2019
Alexander A. Sherstov, Pei Wu

#### Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0

The threshold degree of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is the minimum degree of a real polynomial $p$ that represents $f$ in sign: $\mathrm{sgn}\; p(x)=(-1)^{f(x)}.$ A related notion is sign-rank, defined for a Boolean matrix $F=[F_{ij}]$ as the minimum rank of a real matrix $M$ with $\mathrm{sgn}\; M_{ij}=(-1)^{F_{ij}}$. Determining the maximum ... more >>>

TR18-183 | 5th November 2018
Dean Doron, Pooya Hatami, William Hoza

#### Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas

Revisions: 2

We give an explicit pseudorandom generator (PRG) for constant-depth read-once formulas over the basis $\{\wedge, \vee, \neg\}$ with unbounded fan-in. The seed length of our PRG is $\widetilde{O}(\log(n/\varepsilon))$. Previously, PRGs with near-optimal seed length were known only for the depth-2 case (Gopalan et al. FOCS '12). For a constant depth ... 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 >>>

TR23-017 | 21st February 2023
Deepanshu Kush, Shubhangi Saraf

#### Near-Optimal Set-Multilinear Formula Lower Bounds

The seminal work of Raz (J. ACM 2013) as well as the recent breakthrough results by Limaye, Srinivasan, and Tavenas (FOCS 2021, STOC 2022) have demonstrated a potential avenue for obtaining lower bounds for general algebraic formulas, via strong enough lower bounds for set-multilinear formulas.

In this paper, we make ... more >>>

TR18-065 | 8th April 2018
Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma

#### Near-Optimal Strong Dispersers, Erasure List-Decodable Codes and Friends

Revisions: 1

A code $\mathcal{C}$ is $(1-\tau,L)$ erasure list-decodable if for every codeword $w$, after erasing any $1-\tau$ fraction of the symbols of $w$,
the remaining $\tau$-fraction of its symbols have at most $L$ possible completions into codewords of $\mathcal{C}$.
Non-explicitly, there exist binary $(1-\tau,L)$ erasure list-decodable codes having rate $O(\tau)$ and ... more >>>

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

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 >>> TR19-099 | 29th July 2019 Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman #### Nearly Optimal Pseudorandomness From Hardness Revisions: 3 Existing proofs that deduce$\mathbf{BPP}=\mathbf{P}$from circuit lower bounds convert randomized algorithms into deterministic algorithms with a large polynomial slowdown. We convert randomized algorithms into deterministic ones with little slowdown. Specifically, assuming exponential lower bounds against nondeterministic circuits, we convert any randomized algorithm over inputs of length$n$running in ... 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 >>> TR20-191 | 27th December 2020 Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay #### Negations Provide Strongly Exponential Savings We show that there is a family of monotone multilinear polynomials over$n$variables in VP, such that any monotone arithmetic circuit for it would be of size$2^{\Omega(n)}$. Before our result, strongly exponential lower bounds on the size of monotone circuits were known only for computing explicit polynomials in ... 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 >>> TR20-085 | 5th June 2020 Gal Vardi, Ohad Shamir #### Neural Networks with Small Weights and Depth-Separation Barriers In studying the expressiveness of neural networks, an important question is whether there are functions which can only be approximated by sufficiently deep networks, assuming their size is bounded. However, for constant depths, existing results are limited to depths$2$and$3$, and achieving results for higher depths has been ... 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 >>> TR18-153 | 22nd August 2018 Krishnamoorthy Dinesh, Samir Otiv, Jayalal Sarma #### New Bounds for Energy Complexity of Boolean Functions Revisions: 1 For a Boolean function$f:\{0,1\}^n \to \{0,1\}$computed by a circuit$C$over a finite basis$\cal{B}$, the energy complexity of$C$(denoted by$\mathbf{EC}_{{\cal B}}(C)$) is the maximum over all inputs$\{0,1\}^n$the numbers of gates of the circuit$C$(excluding the inputs) that output a one. Energy Complexity ... more >>> TR20-117 | 4th August 2020 Yuriy Dementiev, Artur Ignatiev, Vyacheslav Sidelnik, Alexander Smal, Mikhail Ushakov #### New bounds on the half-duplex communication complexity Revisions: 3 In this work, we continue the research started in [HIMS18], where the authors suggested to study the half-duplex communication complexity. Unlike the classical model of communication complexity introduced by Yao, in the half-duplex model, Alice and Bob can speak or listen simultaneously, as if they were talking using a walkie-talkie. ... 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 PSPACE. There has been a long line of research trying to explain ... more >>> TR18-205 | 3rd December 2018 Siddhesh Chaubal, Anna Gal #### New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity Nisan and Szegedy conjectured that block sensitivity is at most polynomial in sensitivity for any Boolean function. There is a huge gap between the best known upper bound on block sensitivity in terms of sensitivity - which is exponential, and the best known separating examples - which give only a ... 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 >>> TR20-033 | 12th March 2020 Suryajith Chillara #### New Exponential Size Lower Bounds against Depth Four Circuits of Bounded Individual Degree Revisions: 2 Kayal, Saha and Tavenas [Theory of Computing, 2018] showed that for all large enough integers$n$and$d$such that$d\geq \omega(\log{n})$, any syntactic depth four circuit of bounded individual degree$\delta = o(d)$that computes the Iterated Matrix Multiplication polynomial ($IMM_{n,d}$) must have size$n^{\Omega\left(\sqrt{d/\delta}\right)}$. Unfortunately, this bound ... 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

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 >>> TR23-001 | 5th January 2023 Prerona Chatterjee, Pavel Hrubes #### New Lower Bounds against Homogeneous Non-Commutative Circuits We give several new lower bounds on size of homogeneous non-commutative circuits. We present an explicit homogeneous bivariate polynomial of degree$d$which requires homogeneous non-commutative circuit of size$\Omega(d/\log d)$. For an$n$-variate polynomial with$n>1$, the result can be improved to$\Omega(nd)$, if$d\leq n$, or$\Omega(nd \frac{\log ... more >>>

TR22-183 | 19th December 2022
Lijie Chen

#### New Lower Bounds and Derandomization for ACC, and a Derandomization-centric View on the Algorithmic Method

In this paper, we obtain several new results on lower bounds and derandomization for ACC^0 circuits (constant-depth circuits consisting of AND/OR/MOD_m gates for a fixed constant m, a frontier class in circuit complexity):

1. We prove that any polynomial-time Merlin-Arthur proof system with an ACC^0 verifier (denoted by ... 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 >>>

TR20-015 | 18th February 2020
Emanuele Viola

#### New lower bounds for probabilistic degree and AC0 with parity gates

Revisions: 5

We prove new lower bounds for computing some functions $f:\{0,1\}^{n}\to\{0,1\}$ in $E^{NP}$ by polynomials modulo $2$, constant-depth circuits with parity gates ($AC^{0}[\oplus]$), and related classes. Results include:

(1) $\Omega(n/\log^{2}n)$ lower bounds probabilistic degree. This is optimal up to a factor $O(\log^{2}n)$. The previous best lower bound was $\Omega(\sqrt{n})$ proved in ... 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 >>>

TR22-027 | 22nd February 2022
Guy Blanc, Dean Doron

#### New Near-Linear Time Decodable Codes Closer to the GV Bound

Revisions: 1

We construct a family of binary codes of relative distance $\frac{1}{2}-\varepsilon$ and rate $\varepsilon^{2} \cdot 2^{-\log^{\alpha}(1/\varepsilon)}$ for $\alpha \approx \frac{1}{2}$ that are decodable, probabilistically, in near linear time. This improves upon the rate of the state-of-the-art near-linear time decoding near the GV bound due to Jeronimo, Srivastava, and Tulsiani, who ... more >>>

TR21-094 | 6th July 2021
Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

#### New Non-FPT Lower Bounds for Some Arithmetic Formulas

An Algebraic Formula for a polynomial $P\in F[x_1,\ldots,x_N]$ is an algebraic expression for $P(x_1,\ldots,x_N)$ using variables, field constants, additions and multiplications. Such formulas capture an algebraic analog of the Boolean complexity class $\mathrm{NC}^1.$ Proving lower bounds against this model is thus an important problem.

It is known that, to prove ... 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, N. V. Vinodchandran, 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 >>>

TR22-023 | 19th February 2022
Erfan Khaniki

#### Nisan--Wigderson generators in Proof Complexity: New lower bounds

A map $g:\{0,1\}^n\to\{0,1\}^m$ ($m>n$) is a hard proof complexity generator for a proof system $P$ iff for every string $b\in\{0,1\}^m\setminus Rng(g)$, formula $\tau_b(g)$ naturally expressing $b\not\in Rng(g)$ requires superpolynomial size $P$-proofs. One of the well-studied maps in the theory of proof complexity generators is Nisan--Wigderson generator. Razborov (Annals of Mathematics ... 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 >>>

TR18-012 | 20th January 2018
Valentine Kabanets, Zhenjian Lu

#### Nisan-Wigderson Pseudorandom Generators for Circuits with Polynomial Threshold Gates

We show how the classical Nisan-Wigderson (NW) generator [Nisan & Wigderson, 1994] yields a nontrivial pseudorandom generator (PRG) for circuits with sublinearly many polynomial threshold function (PTF) gates. For the special case of a single PTF of degree $d$ on $n$ inputs, our PRG for error $\epsilon$ has the seed ... more >>>

TR20-035 | 23rd February 2020
Justin Holmgren

#### No-Signaling MIPs and Faster-Than-Light Communication, Revisited

We revisit one original motivation for the study of no-signaling multi-prover
interactive proofs (NS-MIPs): specifically, that two spatially separated
provers are guaranteed to be no-signaling by the physical principle that
information cannot travel from one point to another faster than light.

We observe that with ... more >>>

TR19-111 | 16th August 2019
Klim Efremenko, Gillat Kol, Raghuvansh Saxena

#### Noisy Beeps

We study the effect of noise on the $n$-party beeping model. In this model, in every round, each party may decide to either beep' or not. All parties hear a beep if and only if at least one party beeps. The beeping model is becoming increasingly popular, as it offers ... 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 >>>

TR22-174 | 23rd November 2022
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

#### Noisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds

Revisions: 2

Much of today's communication is carried out over large wireless systems with different input-output behaviors. In this work, we compare the power of central abstractions of wireless communication through the general notion of boolean symmetric $f$-channels: In every round of the $f$-channel, each of its $n$ parties decides to either ... 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 >>>

TR22-098 | 12th July 2022

We give the first polynomial-time *non-adaptive* proper learning algorithm of Boolean sparse multivariate polynomial under the uniform distribution. Our algorithm, for $s$-sparse polynomial over $n$ variables, makes $q=(s/\epsilon)^{\gamma(s,\epsilon)}\log n$ queries where $2.66\le \gamma(s,\epsilon)\le 6.922$ and runs in $\tilde O(n)\cdot poly(s,1/\epsilon)$ time. We also show that for any $\epsilon=1/s^{O(1)}$ any non-adaptive ... more >>>

TR22-049 | 4th April 2022
Xinyu Mao, Noam Mazor, Jiapeng Zhang

#### Non-Adaptive Universal One-Way Hash Functions from Arbitrary One-Way Functions

Revisions: 2

Two of the most useful cryptographic primitives that can be constructed from one-way functions are pseudorandom generators (PRGs) and universal one-way hash functions (UOWHFs). The three major efficiency measures of these primitives are: seed length, number of calls to the one-way function, and adaptivity of these calls. Although a long ... more >>>

TR20-160 | 2nd November 2020
Oded Goldreich, Avi Wigderson

Revisions: 3

We study the relation between the query complexity of adaptive and non-adaptive testers in the dense graph model.
It has been known for a couple of decades that the query complexity of non-adaptive testers is at most quadratic in the query complexity of adaptive testers.
We show that ... 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 >>>

TR18-138 | 10th August 2018
Shuichi Hirahara

#### Non-black-box Worst-case to Average-case Reductions within NP

Revisions: 1

There are significant obstacles to establishing an equivalence between the worst-case and average-case hardness of NP: Several results suggest that black-box worst-case to average-case reductions are not likely to be used for reducing any worst-case problem outside coNP to a distributional NP problem.

This paper overcomes the barrier. We ... 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

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-
morphic).
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 >>>

TR19-031 | 4th March 2019
Lijie Chen

#### Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits

Revisions: 1

Following the seminal work of [Williams, J. ACM 2014], in a recent breakthrough, [Murray and Williams, STOC 2018] proved that NQP (non-deterministic quasi-polynomial time) does not have polynomial-size ACC^0 circuits.

We strengthen the above lower bound to an average case one, by proving that for all constants c, ... more >>>

TR18-009 | 9th January 2018
Saikrishna Badrinarayanan, Yael Kalai, Dakshita Khurana, Amit Sahai, Daniel Wichs

#### Non-Interactive Delegation for Low-Space Non-Deterministic Computation

We construct a delegation scheme for verifying non-deterministic computations, with complexity proportional only to the non-deterministic space of the computation. Specifi cally, letting $n$ denote the input length, we construct a delegation scheme for any language veri fiable in non-deterministic time and space $(T(n);S(n))$ with communication complexity $poly(S(n))$, verifi er ... more >>>

TR18-203 | 1st December 2018
Yael Kalai, Dakshita Khurana

#### Non-Interactive Non-Malleability from Quantum Supremacy

We construct non-interactive non-malleable commitments with respect to replacement, without setup in the plain model, under well-studied assumptions.

First, we construct non-interactive non-malleable commitments with respect to commitment for $\epsilon \log \log n$ tags for a small constant $\epsilon>0$, under the following assumptions:

- Sub-exponential hardness of factoring or discrete ... 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

#### 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 >>>

TR19-030 | 19th February 2019
Claude Crépeau, Nan Yang

#### Non-Locality in Interactive Proofs

In multi-prover interactive proofs (MIPs), the verifier is usually non-adaptive. This stems from an implicit problem which we call “contamination” by the verifier. We make explicit the verifier contamination problem, and identify a solution by constructing a generalization of the MIP model. This new model quantifies non-locality as a new ... more >>>

TR20-023 | 10th February 2020
Marshall Ball, Eshan Chattopadhyay, Jyun-Jie Liao, Tal Malkin, Li-Yang Tan

#### Non-Malleability against Polynomial Tampering

Revisions: 1

We present the first explicit construction of a non-malleable code that can handle tampering functions that are bounded-degree polynomials.

Prior to our work, this was only known for degree-1 polynomials (affine tampering functions), due to Chattopadhyay and Li (STOC 2017). As a direct corollary, we obtain an explicit non-malleable ... more >>>

TR14-102 | 4th August 2014

#### 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

#### 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 >>>

TR18-040 | 21st February 2018
Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, Li-Yang Tan

#### Non-Malleable Codes for Small-Depth Circuits

We construct efficient, unconditional non-malleable codes that are secure against tampering functions computed by small-depth circuits. For constant-depth circuits of polynomial size (i.e.~$\mathsf{AC^0}$ tampering functions), our codes have codeword length $n = k^{1+o(1)}$ for a $k$-bit message. This is an exponential improvement of the previous best construction due to Chattopadhyay ... 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 >>>

TR18-070 | 13th April 2018

#### Non-Malleable Extractors and Codes in the Interleaved Split-State Model and More

Revisions: 3

We present explicit constructions of non-malleable codes with respect to the following tampering classes. (i) Linear functions composed with split-state adversaries: In this model, the codeword is first tampered by a split-state adversary, and then the whole tampered codeword is further tampered by a linear function. (ii) Interleaved split-state adversary: ... 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>
<ul>
<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

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 >>>

TR18-013 | 18th January 2018

#### Nondeterminisic Sublinear Time Has Measure 0 in P

The measure hypothesis is a quantitative strengthening of the P $\neq$ NP conjecture which asserts that NP is a nonnegligible subset of EXP. Cai, Sivakumar, and Strauss (1997) showed that the analogue of this hypothesis in P is false. In particular, they showed that NTIME[$n^{1/11}$] has measure 0 in P. ... more >>>

TR19-043 | 12th March 2019
Toniann Pitassi, Morgan Shirley, Thomas Watson

#### Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity

Revisions: 1

We study the Boolean Hierarchy in the context of two-party communication complexity, as well as the analogous hierarchy defined with one-sided error randomness instead of nondeterminism. Our results provide a complete picture of the relationships among complexity classes within and across these two hierarchies. In particular, we prove a query-to-communication ... 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 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 >>>

TR19-100 | 31st July 2019
Hervé Fournier, Guillaume Malod, Maud Szusterman, Sébastien Tavenas

#### Nonnegative rank measures and monotone algebraic branching programs

Inspired by Nisan's characterization of noncommutative complexity (Nisan 1991), we study different notions of nonnegative rank, associated complexity measures and their link with monotone computations. In particular we answer negatively an open question of Nisan asking whether nonnegative rank characterizes monotone noncommutative complexity for algebraic branching programs. We also prove ... 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 >>>

TR18-011 | 18th January 2018

#### Nonuniform Reductions and NP-Completeness

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 >>>

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 >>>

TR20-102 | 9th July 2020
Stasys Jukna

#### Notes on Hazard-Free Circuits

Revisions: 2

The problem of constructing hazard-free Boolean circuits (those avoiding electronic glitches) dates back to the 1940s and is an important problem in circuit design. Recently, Ikenmeyer et al. [J. ACM, 66:4 (2019), Article 25] have shown that the hazard-free circuit complexity of any Boolean function $f(x)$ is lower-bounded by the ... 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 >>>

TR22-094 | 3rd July 2022
Stasys Jukna

#### Notes on Monotone Read-k Circuits

Revisions: 2

A monotone Boolean $(\lor,\land)$ circuit $F$ computing a Boolean function $f$ is a read-$k$ circuit if the polynomial produced (purely syntactically) by the arithmetic $(+,\times)$ version of $F$ has the property that for every prime implicant of $f$, the polynomial contains a monomial with the same set of variables, each ... 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

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
quantum-mechanical nonlinearities, hidden variables, relativistic time
dilation, analog computing, Malament-Hogarth spacetimes, quantum
gravity, closed timelike curves, and "anthropic computing." The ... more >>>

TR19-050 | 20th March 2019
Titus Dose, Christian Glaßer

#### NP-Completeness, Proof Systems, and Disjoint NP-Pairs

The article investigates the relation between three well-known hypotheses.
1) Hunion: the union of disjoint complete sets for NP is complete for NP
2) Hopps: there exist optimal propositional proof systems
3) Hcpair: there exist complete disjoint NP-pairs

The following results are obtained:
a) The hypotheses are pairwise independent ... 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 >>>

TR20-021 | 21st February 2020
Rahul Ilango, Bruno Loff, Igor Carboni Oliveira

#### NP-Hardness of Circuit Minimization for Multi-Output Functions

Can we design efficient algorithms for finding fast algorithms? This question is captured by various circuit minimization problems, and algorithms for the corresponding tasks have significant practical applications. Following the work of Cook and Levin in the early 1970s, a central question is whether minimizing the circuit size of an ... more >>>

TR18-073 | 21st April 2018
Amey Bhangale

#### NP-hardness of coloring $2$-colorable hypergraph with poly-logarithmically many colors

We give very short and simple proofs of the following statements: Given a $2$-colorable $4$-uniform hypergraph on $n$ vertices,

(1) It is NP-hard to color it with $\log^\delta n$ colors for some $\delta>0$.
(2) It is $quasi$-NP-hard to color it with $O\left({\log^{1-o(1)} n}\right)$ colors.

In terms of ... more >>>

TR22-119 | 24th August 2022
Shuichi Hirahara

#### NP-Hardness of Learning Programs and Partial MCSP

A long-standing open question in computational learning theory is to prove NP-hardness of learning efficient programs, the setting of which is in between proper learning and improper learning. Ko (COLT'90, SICOMP'91) explicitly raised this open question and demonstrated its difficulty by proving that there exists no relativizing proof of NP-hardness ... more >>>

TR18-030 | 9th February 2018
Shuichi Hirahara, Igor Carboni Oliveira, Rahul Santhanam

#### NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits

The Minimum Circuit Size Problem (MCSP) asks for the size of the smallest boolean circuit that computes a given truth table. It is a prominent problem in NP that is believed to be hard, but for which no proof of NP-hardness has been found. A significant number of works have ... 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 >>>

TR20-001 | 31st December 2019
Or Meir, Jakob Nordström, Robert Robere, Susanna de Rezende

#### Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling

Revisions: 2

We establish an exactly tight relation between reversible pebblings of graphs and Nullstellensatz refutations of pebbling formulas, showing that a graph $G$ can be reversibly pebbled in time $t$ and space $s$ if and only if there is a Nullstellensatz refutation of the pebbling formula over $G$ in size $t+1$ ... more >>>

TR21-097 | 7th July 2021
Jacobo Toran, Florian Wörz

#### Number of Variables for Graph Identification and the Resolution of GI Formulas

We show that the number of variables and the quantifier depth needed to distinguish a pair of graphs by first-order logic sentences exactly match the complexity measures of clause width and positive depth needed to refute the corresponding graph isomorphism formula in propositional narrow resolution.

Using this connection, we ... more >>>

ISSN 1433-8092 | Imprint