Under the auspices of the Computational Complexity Foundation (CCF)

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

O
TR14-071 | 7th May 2014
Tetsuo Asano, David Kirkpatrick, Kotaro Nakagawa, Osamu Watanabe

#### O(sqrt(n))-Space and Polynomial-time Algorithm for the Planar Directed Graph Reachability Problem

We show an O(sqrt(n))-space and polynomial-time algorithm for solving the planar directed graph reachability problem. Imai et al. showed in CCC 2013 that the problem is solvable in O(n^{1/2+eps})-space and polynomial-time by using separators for planar graphs, and it has been open whether the space bound can be improved to ... more >>>

TR10-028 | 4th March 2010
Miklos Ajtai

#### Oblivious RAMs without Cryptographic Assumptions

Revisions: 1

Abstract. We show that oblivious on-line simulation with only
polylogarithmic increase in the time and space requirements is possible
on a probabilistic (coin flipping) RAM without using any cryptographic
assumptions. The simulation will fail with a negligible probability.
If $n$ memory locations are used, then the probability of failure is ... more >>>

TR17-118 | 20th July 2017
Xiaotie Deng, Zhe Feng, Rucha Kulkarni

#### Octahedral Tucker is PPA-Complete

The Octahedral Tucker problem considers an n-dimensional hypergrid of side length two, centered at the origin, triangulated by connecting the origin to all outside vertices (applied recursively on each of the lower dimensional hypergrids passing through their origins at the corresponding reduced dimensions). Each vertex is assigned a color in ... more >>>

TR09-139 | 17th December 2009

#### On the Power of Randomized Reductions and the Checkability of SAT

Revisions: 3

The closure of complexity classes is a elicate question and the answer varies depending on the type of reduction considered. The closure of most classes under many-to-one (Karp) reductions is clear, but the question becomes complicated when oracle (Cook) reductions are allowed, and even more so when the oracle reductions ... more >>>

TR14-004 | 30th November 2013

#### On $r$-Simple $k$-Path

An $r$-simple $k$-path is a {path} in the graph of length $k$ that
passes through each vertex at most $r$ times. The \simpath{r}{k}
problem, given a graph $G$ as input, asks whether there exists an
$r$-simple $k$-path in $G$. We first show that this problem is
NP-Complete. We then show ... more >>>

TR05-077 | 15th July 2005

#### On a D-N-optimal acceptor for TAUT

The notion of an optimal acceptor for TAUT (the optimality
property is stated only for input strings from TAUT) comes from the line
of research aimed at resolving the question of whether optimal
propositional proof systems exist. In this paper we introduce two new
types of optimal acceptors, a D-N-optimal ... more >>>

TR11-130 | 25th September 2011
Sergei Lozhkin, Alexander Shiganov

#### On a Modification of Lupanov's Method with More Uniform Distribution of Fan-out

In this paper we suggest a modification of classical Lupanov's method [Lupanov1958]
that allows building circuits over the basis $\{\&,\vee,\neg\}$ for Boolean functions of $n$ variables with size at most
$$\frac{2^n}{n}\left(1+\frac{3\log n + O(1)}{n}\right),$$
and with more uniform distribution of outgoing arcs by circuit gates.

For almost all ... more >>>

TR10-024 | 21st February 2010
Henning Wunderlich, Stefan Arnold

#### On a singular value method in quantum communication complexity

We introduce a new lower bound method for bounded-error quantum communication complexity,
the \emph{singular value method (svm)}, based on sums of squared singular values of the
communication matrix, and we compare it with existing methods.

The first finding is a constant factor improvement of lower bounds based on the
spectral ... more >>>

TR12-144 | 6th November 2012
Rocco Servedio, Emanuele Viola

#### On a special case of rigidity

We highlight the special case of Valiant's rigidity
problem in which the low-rank matrices are truth-tables
of sparse polynomials. We show that progress on this
special case entails that Inner Product is not computable
by small $\acz$ circuits with one layer of parity gates
close to the inputs. We then ... more >>>

TR06-014 | 20th December 2005
Argimiro Arratia, Carlos E. Ortiz

#### On a syntactic approximation to logics that capture complexity classes

We formulate a formal syntax of approximate formulas for the logic with counting
quantifiers, $\mathcal{SOLP}$, studied by us in \cite{aaco06}, where we showed the
following facts:
$(i)$ In the presence of a built--in (linear) order, $\mathcal{SOLP}$ can
describe {\bf NP}--complete problems and fragments of it capture classes like
{\bf P} ... more >>>

TR10-086 | 17th May 2010
Henning Wunderlich

#### On a Theorem of Razborov

In an unpublished Russian manuscript Razborov proved that a matrix family with high
rigidity over a finite field would yield a language outside the polynomial hierarchy
in communication complexity.

We present an alternative proof that strengthens the original result in several ways.
In particular, we replace rigidity by the strictly ... more >>>

TR17-034 | 21st February 2017
Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam

#### On algebraic branching programs of small width

Revisions: 1

In 1979 Valiant showed that the complexity class VP_e of families with polynomially bounded formula size is contained in the class VP_s of families that have algebraic branching programs (ABPs) of polynomially bounded size. Motivated by the problem of separating these classes we study the topological closure VP_e-bar, i.e. the ... more >>>

TR02-046 | 16th July 2002
Marek Karpinski

#### On Approximability of Minimum Bisection Problem

We survey some recent results on the complexity of computing
approximate solutions for instances of the Minimum Bisection problem
and formulate some intriguing and still open questions about the
approximability status of that problem. Some connections to other
optimization problems are also indicated.

more >>>

TR95-016 | 2nd February 1995
U. Faigle, S.P. Fekete, W. Hochstättler, W. Kern

#### On approximately fair cost allocation in Euclidean TSP games

We consider the problem of fair cost allocation for traveling
salesman games for which the triangle inequality holds. We
give examples showing that the core of such games may be
empty, even for the case of Euclidean distances. On the
positive side, we develop an LP-based ... more >>>

TR99-039 | 24th September 1999

#### On approximating CSP-B

We prove that any constraint satisfaction problem
where each variable appears a bounded number of
times admits a nontrivial polynomial time approximation
algorithm.

more >>>

TR07-011 | 19th December 2006
Bodo Manthey

#### On Approximating Restricted Cycle Covers

A cycle cover of a graph is a set of cycles such that every vertex is
part of exactly one cycle. An L-cycle cover is a cycle cover in which
the length of every cycle is in the set L. The weight of a cycle cover
of an edge-weighted graph ... more >>>

TR16-120 | 1st August 2016
Dean Doron, Amir Sarid, Amnon Ta-Shma

#### On approximating the eigenvalues of stochastic matrices in probabilistic logspace

Revisions: 1

Approximating the eigenvalues of a Hermitian operator can be solved
by a quantum logspace algorithm. We introduce the problem of
approximating the eigenvalues of a given matrix in the context of
classical space-bounded computation. We show that:

- Approximating the second eigenvalue of stochastic operators (in a
certain range of ... more >>>

TR10-160 | 28th October 2010
Zeev Dvir, Dan Gutfreund, Guy Rothblum, Salil Vadhan

#### On Approximating the Entropy of Polynomial Mappings

We investigate the complexity of the following computational problem:

Polynomial Entropy Approximation (PEA):
Given a low-degree polynomial mapping
$p : F^n\rightarrow F^m$, where $F$ is a finite field, approximate the output entropy
$H(p(U_n))$, where $U_n$ is the uniform distribution on $F^n$ and $H$ may be any of several entropy measures.

... more >>>

TR05-094 | 9th August 2005
Michal Parnas, Dana Ron

#### On Approximating the Minimum Vertex Cover in Sublinear Time and the Connection to Distributed Algorithms

Revisions: 1

We consider the problem of estimating the size, $VC(G)$, of a
minimum vertex cover of a graph $G$, in sublinear time,
by querying the incidence relation of the graph. We say that
an algorithm is an $(\alpha,\eps)$-approximation algorithm
if it outputs with high probability an estimate $\widehat{VC}$
such that ... more >>>

TR11-078 | 9th May 2011

#### On Approximating the Number of Relevant Variables in a Function

In this work we consider the problem of approximating the number of relevant variables in a function given query access to the function. Since obtaining a multiplicative factor approximation is hard in general, we consider several relaxations of the problem. In particular, we consider relaxations in which we have a ... more >>>

TR98-024 | 28th April 1998
Wenceslas Fernandez de la Vega, Marek Karpinski

#### On Approximation Hardness of Dense TSP and other Path Problems

TSP(1,2), the Traveling Salesman Problem with distances 1 and 2, is
the problem of finding a tour of minimum length in a complete
weighted graph where each edge has length 1 or 2. Let $d_o$ satisfy
$0<d_o<1/2$. We show that TSP(1,2) has no PTAS on the set ... more >>>

TR97-041 | 18th September 1997
Marek Karpinski, Juergen Wirtgen

#### On Approximation Hardness of the Bandwidth Problem

The bandwidth problem is the problem of enumerating
the vertices of a given graph $G$ such that the maximum
difference between the numbers of
adjacent vertices is minimal. The problem has a long
history and a number of applications
and is ... more >>>

TR98-014 | 6th February 1998
Gunter Blache, Marek Karpinski, Juergen Wirtgen

#### On Approximation Intractability of the Bandwidth Problem

The bandwidth problem is the problem of enumerating
the vertices of a given graph $G$ such that the maximum difference
between the numbers of adjacent vertices is minimal. The problem
has a long history and a number of applications.
There was not ... more >>>

TR12-008 | 30th January 2012
Marek Karpinski, Richard Schmied

#### On Approximation Lower Bounds for TSP with Bounded Metrics

Revisions: 1

We develop a new method for proving explicit approximation lower bounds for TSP problems with bounded metrics improving on the best up to now known bounds. They almost match the best known bounds for unbounded metric TSP problems. In particular, we prove the best known lower bound for TSP with ... more >>>

TR04-039 | 21st April 2004
Andrzej Lingas, Martin Wahlén

#### On approximation of the maximum clique minor containment problem and some subgraph homeomorphism problems

We consider the minor'' and homeomorphic'' analogues of the maximum clique problem, i.e., the problems of determining the largest $h$ such that the input graph has a minor isomorphic to $K_h$ or a subgraph homeomorphic to $K_h,$ respectively.We show the former to be approximable within $O(\sqrt {n} \log^{1.5} n)$ by ... more >>>

TR06-066 | 5th May 2006
Vitaly Feldman

#### On Attribute Efficient and Non-adaptive Learning of Parities and DNF Expressions

Revisions: 1

We consider the problems of attribute-efficient PAC learning of two well-studied concept classes: parity functions and DNF expressions over $\{0,1\}^n$. We show that attribute-efficient learning of parities with respect to the uniform distribution is equivalent to decoding high-rate random linear codes from low number of errors, a long-standing open problem ... more >>>

TR17-110 | 22nd June 2017
Alessandro Chiesa, Peter Manohar, Igor Shinkar

#### On Axis-Parallel Tests for Tensor Product Codes

Many low-degree tests examine the input function via its restrictions to random hyperplanes of a certain dimension. Examples include the line-vs-line (Arora, Sudan 2003), plane-vs-plane (Raz, Safra 1997), and cube-vs-cube (Bhangale, Dinur, Livni 2017) tests.

In this paper we study a test introduced by Ben-Sasson and Sudan in 2006 that ... more >>>

TR06-015 | 1st February 2006
Tomas Feder, Carlos Subi

#### On Barnette's conjecture

Barnette's conjecture is the statement that every 3-connected cubic
planar bipartite graph is Hamiltonian. Goodey showed that the conjecture
holds when all faces of the graph have either 4 or 6 sides. We
generalize Goodey's result by showing that when the faces of such a
graph are 3-colored, with adjacent ... more >>>

TR14-108 | 10th August 2014
Andrej Bogdanov, Christina Brzuska

#### On Basing Size-Verifiable One-Way Functions on NP-Hardness

Revisions: 1

We prove that if the hardness of inverting a size-verifiable one-way function can
be based on NP-hardness via a general (adaptive) reduction, then coAM is contained in NP. This
claim was made by Akavia, Goldreich, Goldwasser, and Moshkovitz (STOC 2006), but
was later retracted (STOC 2010).

more >>>

TR09-006 | 19th January 2009
David Xiao

#### On basing ZK != BPP on the hardness of PAC learning

Learning is a central task in computer science, and there are various
formalisms for capturing the notion. One important model studied in
computational learning theory is the PAC model of Valiant (CACM 1984).
On the other hand, in cryptography the notion of learning nothing''
is often modelled by the simulation ... more >>>

TR10-186 | 2nd December 2010
Bill Fefferman, Ronen Shaltiel, Chris Umans, Emanuele Viola

#### On beating the hybrid argument

The {\em hybrid argument}
allows one to relate
the {\em distinguishability} of a distribution (from
uniform) to the {\em
predictability} of individual bits given a prefix. The
argument incurs a loss of a factor $k$ equal to the
bit-length of the
distributions: $\epsilon$-distinguishability implies only
$\epsilon/k$-predictability. ... more >>>

TR15-072 | 23rd April 2015
Roei Tell

#### On Being Far from Far and on Dual Problems in Property Testing

Revisions: 4

For a set $\Pi$ in a metric space and $\delta>0$, denote by $\mathcal{F}_\delta(\Pi)$ the set of elements that are $\delta$-far from $\Pi$. In property testing, a $\delta$-tester for $\Pi$ is required to accept inputs from $\Pi$ and reject inputs from $\mathcal{F}_\delta(\Pi)$. A natural dual problem is the problem of $\delta$-testing ... more >>>

TR07-019 | 10th March 2007
Jin-Yi Cai, Pinyan Lu

#### On Block-wise Symmetric Signatures for Matchgates

We give a classification of block-wise symmetric signatures
in the theory of matchgate computations. The main proof technique
is matchgate identities, a.k.a. useful Grassmann-Pl\"{u}cker
identities.

more >>>

TR98-030 | 9th June 1998
Stasys Jukna, Stanislav Zak

#### On Branching Programs With Bounded Uncertainty

We propose an information-theoretic approach to proving
lower bounds on the size of branching programs (b.p.). The argument
is based on Kraft-McMillan type inequalities for the average amount of
uncertainty about (or entropy of) a given input during various
stages of the computation. ... more >>>

TR03-041 | 29th May 2003
Albert Atserias, Maria Luisa Bonet, Jordi Levy

#### On Chvatal Rank and Cutting Planes Proofs

We study the Chv\'atal rank of polytopes as a complexity measure of
unsatisfiable sets of clauses. Our first result establishes a
connection between the Chv\'atal rank and the minimum refutation
length in the cutting planes proof system. The result implies that
length lower bounds for cutting planes, or even for ... more >>>

TR04-024 | 26th March 2004
Thomas Thierauf, Thanh Minh Hoang

#### On Closure Properties of GapL

We show necessary and sufficient conditions that
certain algebraic functions like the rank or the signature
of an integer matrix can be computed in GapL.

more >>>

TR17-177 | 16th November 2017
Daniel Kane, Roi Livni, Shay Moran, Amir Yehudayoff

#### On Communication Complexity of Classification Problems

This work introduces a model of distributed learning in the spirit of Yao's communication complexity model. We consider a two-party setting, where each of the players gets a list of labelled examples and they communicate in order to jointly perform some learning task. To naturally fit into the framework of ... more >>>

TR05-051 | 18th March 2005
Predrag Tosic

#### On Complexity of Counting Fixed Points in Certain Classes of Graph Automata

Revisions: 2

We study the computational complexity of counting the fixed point configurations in certain discrete dynamical systems. We prove that both exact and approximate counting in Sequential and Synchronous Dynamical Systems (SDSs and SyDS, respectrively) is computationally intractable, even when each node is required to update according to a symmetric Boolean ... more >>>

TR05-074 | 8th June 2005
Li-Sha Huang, Xiaotie Deng

#### On Complexity of Market Equilibria with Maximum Social Welfare

We consider the computational complexity of the market equilibrium
problem by exploring the structural properties of the Leontief
exchange economy. We prove that, for economies guaranteed to have
a market equilibrium, finding one with maximum social welfare or
maximum individual welfare is NP-hard. In addition, we prove that
counting the ... more >>>

TR08-085 | 19th June 2008
Farid Ablayev, Airat Khasianov, Alexander Vasiliev

#### On Complexity of Quantum Branching Programs Computing Equality-like Boolean Functions

Revisions: 1

We consider Generalized Equality, the Hidden Subgroup,
and related problems in the context of quantum Ordered Binary
Decision Diagrams. For the decision versions of considered problems
we show polynomial upper bounds in terms of quantum OBDD width. We
apply a new modification of the fingerprinting technique and present
the algorithms ... more >>>

TR99-044 | 30th September 1999
Farid Ablayev

#### On Complexity of Regular $(1,+k)$-Branching Programs

A regular $(1,+k)$-branching program ($(1,+k)$-ReBP) is an
ordinary branching program with the following restrictions: (i)
along every consistent path at most $k$ variables are tested more
than once, (ii) for each node $v$ on all paths from the source to
$v$ the same set $X(v)\subseteq X$ of variables is ... more >>>

TR00-038 | 24th May 2000

#### On Computation with Pulses

We explore the computational power of formal models for computation
with pulses. Such models are motivated by realistic models for
biological neurons, and by related new types of VLSI (pulse stream
VLSI'').

In preceding work it was shown that the computational power of formal
models for computation with pulses is ... more >>>

TR11-107 | 22nd July 2011
Pavol Duris

#### On Computational Power of Partially Blind Automata

In this paper we deal with 1-way multihead finite automata, in which the symbol under only one head (called read head) controls its move and other heads cannot distinguish the input symbols, they can only distinguish the end-marker from the other input symbols and they are called the blind head. ... more >>>

TR95-029 | 15th June 1995
Oded Goldreich, Leonid Levin, Noam Nisan

#### On Constructing 1-1 One-Way Functions

We show how to construct length-preserving 1-1 one-way
functions based on popular intractability assumptions (e.g., RSA, DLP).
Such 1-1 functions should not
be confused with (infinite) families of (finite) one-way permutations.
What we want and obtain is a single (infinite) 1-1 one-way function.

more >>>

TR03-017 | 27th March 2003
Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener

#### On Converting CNF to DNF

The best-known representations of boolean functions f are those of disjunctions of terms (DNFs) and as conjuctions of clauses (CNFs). It is convenient to define the DNF size of f as the minimal number of terms in a DNF representing f and the CNF size as the minimal number of ... more >>>

TR09-040 | 20th April 2009
Pavel Hrubes, Stasys Jukna, Alexander Kulikov, Pavel Pudlak

#### On convex complexity measures

Khrapchenko's classical lower bound $n^2$ on the formula size of the
parity function~$f$ can be interpreted as designing a suitable
measure of subrectangles of the combinatorial rectangle
$f^{-1}(0)\times f^{-1}(1)$. Trying to generalize this approach we
arrived at the concept of \emph{convex measures}. We prove the
more >>>

TR98-020 | 10th April 1998
Andris Ambainis, David Mix Barrington, Huong LeThanh

#### On Counting $AC^0$ Circuits with Negative Constants

Continuing the study of the relationship between $TC^0$,
$AC^0$ and arithmetic circuits, started by Agrawal et al.
(IEEE Conference on Computational Complexity'97),
we answer a few questions left open in this
paper. Our main result is that the classes Diff$AC^0$ and
Gap$AC^0$ ... more >>>

TR05-121 | 17th October 2005
Martin Dyer, Leslie Ann Goldberg, Michael S. Paterson

#### On counting homomorphisms to directed acyclic graphs

We give a dichotomy theorem for the problem of counting homomorphisms to
directed acyclic graphs. $H$ is a fixed directed acyclic graph.
The problem is, given an input digraph $G$, how many homomorphisms are there
from $G$ to $H$. We give a graph-theoretic classification, showing that
for some digraphs $H$, ... more >>>

TR95-062 | 14th December 1995
Amir M. Ben-Amram, Zvi Galil

#### On Data Structure Tradeoffs and an Application to Union-Find

Consider a problem involving updates and queries of a data structure.
Assume that there exists a family of algorithms which exhibit a
tradeoff between query and update time. We demonstrate a general
technique of constructing from such a family
a single algorithm with best amortized time. We indicate some ... more >>>

TR06-113 | 25th August 2006
Peter Buergisser

#### On defining integers in the counting hierarchy and proving lower bounds in algebraic complexity

Let $\tau(n)$ denote the minimum number of arithmetic operations sufficient to build the integer $n$ from the constant~$1$. We prove that if there are arithmetic circuits for computing the permanent of $n$ by $n$ matrices having size polynomial in $n$, then $\tau(n!)$ is polynomially bounded in $\log n$. Under the ... more >>>

TR17-146 | 1st October 2017
Or Meir

#### On Derandomized Composition of Boolean Functions

Revisions: 1

The composition of two Boolean functions $f:\left\{0,1\right\}^{m}\to\left\{0,1\right\}$, $g:\left\{0,1\right\}^{n}\to\left\{0,1\right\}$
is the function $f \diamond g$ that takes as inputs $m$ strings $x_{1},\ldots,x_{m}\in\left\{0,1\right\}^{n}$
and computes
$(f \diamond g)(x_{1},\ldots,x_{m})=f\left(g(x_{1}),\ldots,g(x_{m})\right).$
This operation has been used several times for amplifying different
hardness measures of $f$ and $g$. This comes at a cost: the ... more >>>

TR13-152 | 7th November 2013
Oded Goldreich, Avi Wigderson

#### On Derandomizing Algorithms that Err Extremely Rarely

Revisions: 2

{\em Does derandomization of probabilistic algorithms become easier when the number of bad'' random inputs is extremely small?}

In relation to the above question, we put forward the following {\em quantified derandomization challenge}:
For a class of circuits $\cal C$ (e.g., P/poly or $AC^0,AC^0[2]$) and a bounding function $B:\N\to\N$ (e.g., ... more >>>

TR02-009 | 17th January 2002
Petr Savicky

#### On determinism versus unambiquous nondeterminism for decision trees

Let $f$ be a Boolean function. Let $N(f)=\dnf(f)+\dnf(\neg f)$ be the
sum of the minimum number of monomials in a disjunctive normal form
for $f$ and $\neg f$. Let $p(f)$ be the minimum size of a partition
of the Boolean cube into disjoint subcubes such that $f$ is constant on
more >>>

TR05-064 | 26th June 2005
Howard Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani

#### On earthmover distance, metric labeling, and 0-extension

We study the classification problem {\sc Metric Labeling} and its special case {\sc 0-Extension} in the context of earthmover metrics. Researchers recently proposed using earthmover metrics to get a polynomial time-solvable relaxation of {\sc Metric Labeling}; until now, however, no one knew if the integrality ratio was constant or not, ... more >>>

TR15-086 | 28th May 2015
Jop Briet

#### On Embeddings of $\ell_1^k$ from Locally Decodable Codes

We show that any $q$-query locally decodable code (LDC) gives a copy of $\ell_1^k$ with small distortion in the Banach space of $q$-linear forms on $\ell_{p_1}^N\times\cdots\times\ell_{p_q}^N$, provided $1/p_1 + \cdots + 1/p_q \leq 1$ and where $k$, $N$, and the distortion are simple functions of the code parameters. We exhibit ... more >>>

TR16-066 | 19th April 2016
Oded Goldreich, Maya Leshkowitz

#### On Emulating Interactive Proofs with Public Coins

The known emulation of interactive proof systems by public-coins interactive proof systems proceeds by selecting, at each round, a message such that each message is selected with probability that is at most polynomially larger than its probability in the original protocol.
Specifically, the possible messages are essentially clustered according to ... more >>>

TR03-043 | 14th May 2003
Elchanan Mossel, Amir Shpilka, Luca Trevisan

#### On epsilon-Biased Generators in NC0

Cryan and Miltersen recently considered the question
of whether there can be a pseudorandom generator in
NC0, that is, a pseudorandom generator such that every
bit of the output depends on a constant number k of bits
of the seed. They show that for k=3 there is always a
distinguisher; ... more >>>

TR04-013 | 10th February 2004
Oded Goldreich, Dana Ron

#### On Estimating the Average Degree of a Graph.

Following Feige, we consider the problem of
estimating the average degree of a graph.
Using neighbor queries'' as well as degree queries'',
we show that the average degree can be approximated
arbitrarily well in sublinear time, unless the graph is extremely sparse
(e.g., unless the graph has a sublinear ... more >>>

TR97-013 | 13th February 1997
Bernd Borchert, Dietrich Kuske, Frank Stephan

#### On Existentially First-Order Definable Languages and their Relation to NP

Pin & Weil [PW95] characterized the automata of existentially
first-order definable languages. We will use this result for the following
characterization of the complexity class NP. Assume that the
Polynomial-Time Hierarchy does not collapse. Then a regular language
L characterizes NP as an unbalanced polynomial-time leaf language
if and ... more >>>

TR06-028 | 21st February 2006
Jonathan Katz, Chiu-Yuen Koo

#### On Expected Constant-Round Protocols for Byzantine Agreement

In a seminal paper, Feldman and Micali (STOC '88) show an n-party Byzantine agreement protocol tolerating t < n/3 malicious parties that runs in expected constant rounds. Here, we show an expected constant-round protocol for authenticated Byzantine agreement assuming honest majority (i.e., $t < n/2$), and relying only on the ... more >>>

TR06-099 | 17th August 2006
Oded Goldreich

#### On Expected Probabilistic Polynomial-Time Adversaries -- A suggestion for restricted definitions and their benefits

Revisions: 1

This paper concerns the possibility of developing a coherent
theory of security when feasibility is associated
with expected probabilistic polynomial-time (expected PPT).
The source of difficulty is that
the known definitions of expected PPT strategies
(i.e., expected PPT interactive machines)
do not support natural results of the ... more >>>

TR17-174 | 13th November 2017
Christian Engels, Mohit Garg, Kazuhisa Makino, Anup Rao

#### On Expressing Majority as a Majority of Majorities

If $k<n$, can one express the majority of $n$ bits as the majority of at most $k$ majorities, each of at most $k$ bits? We prove that such an expression is possible only if $k = \Omega(n^{4/5})$. This improves on a bound proved by Kulikov and Podolskii, who showed that ... more >>>

TR95-058 | 20th November 1995
Amnon Ta-Shma

#### On Extracting Randomness From Weak Random Sources

We deal with the problem of extracting as much randomness as possible
from a defective random source.
We devise a new tool, a merger'', which is a function that accepts
d strings, one of which is uniformly distributed,
and outputs a single string that is guaranteed ... more >>>

TR15-069 | 21st April 2015
Amey Bhangale, Ramprasad Saptharishi, Girish Varma, Rakesh Venkat

#### On Fortification of General Games

Revisions: 1

A recent result of Moshkovitz~\cite{Moshkovitz14} presented an ingenious method to provide a completely elementary proof of the Parallel Repetition Theorem for certain projection games via a construction called fortification. However, the construction used in \cite{Moshkovitz14} to fortify arbitrary label cover instances using an arbitrary extractor is insufficient to prove parallel ... more >>>

TR13-168 | 29th November 2013
Raghav Kulkarni, Avishay Tal

#### On Fractional Block Sensitivity

In this paper we study the fractional block sensitivityof Boolean functions. Recently, Tal (ITCS, 2013) and
Gilmer, Saks, and Srinivasan (CCC, 2013) independently introduced this complexity measure, denoted by $fbs(f)$, and showed
that it is equal (up to a constant factor) to the randomized certificate complexity, denoted by $RC(f)$, which ... more >>>

TR98-061 | 29th September 1998
Robert H. Sloan, Ken Takata, György Turán

#### On frequent sets of Boolean matrices

Given a Boolean matrix and a threshold t, a subset of the
columns is frequent if there are at least t rows having a 1 entry in
each corresponding position. This concept is used in the algorithmic,
combinatorial approach to knowledge discovery and data mining. We
consider the complexity aspects ... more >>>

TR04-005 | 19th January 2004
Stasys Jukna

#### On Graph Complexity

A boolean circuit $f(x_1,\ldots,x_n)$ \emph{represents} a graph $G$
on $n$ vertices if for every input vector $a\in\{0,1\}^n$ with
precisely two $1$'s in, say, positions $i$ and $j$, $f(a)=1$
precisely when $i$ and $j$ are adjacent in $G$; on inputs with more
or less than two ... more >>>

TR15-013 | 28th January 2015
Subhash Khot, Igor Shinkar

#### On Hardness of Approximating the Parameterized Clique Problem

In the $Gap-clique(k, \frac{k}{2})$ problem, the input is an $n$-vertex graph $G$, and the goal is to decide whether $G$ contains a clique of size $k$ or contains no clique of size $\frac{k}{2}$. It is an open question in the study of fixed parameterized tractability whether the $Gap-clique(k, \frac{k}{2})$ problem ... more >>>

TR15-067 | 21st April 2015
Pavel Hrubes

#### On hardness of multilinearization, and VNP completeness in characteristics two

For a boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$, let $\hat{f}$ be the unique multilinear polynomial such that $f(x)=\hat{f}(x)$ holds for every $x\in \{0,1\}^n$. We show that, assuming $\hbox{VP}\not=\hbox{VNP}$, there exists a polynomial-time computable $f$ such that $\hat{f}$ requires super-polynomial arithmetic circuits. In fact, this $f$ can be taken as a monotone 2-CNF, ... more >>>

TR06-131 | 6th October 2006
Konstantin Pervyshev

#### On Heuristic Time Hierarchies

We study the existence of time hierarchies for heuristic (average-case) algorithms. We prove that a time hierarchy exists for heuristics algorithms in such syntactic classes as NP and co-NP, and also in semantic classes AM and MA. Earlier, Fortnow and Santhanam (FOCS'04) proved the existence of a time hierarchy for ... more >>>

TR11-147 | 2nd November 2011
Michael Forbes, Amir Shpilka

#### On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing

We study the problem of obtaining efficient, deterministic, black-box polynomial identity testing algorithms for depth-3 set-multilinear circuits (over arbitrary fields). This class of circuits has an efficient, deterministic, white-box polynomial identity testing algorithm (due to Raz and Shpilka), but has no known such black-box algorithm. We recast this problem as ... more >>>

TR16-124 | 12th August 2016
Subhash Khot

#### On Independent Sets, $2$-to-$2$ Games and Grassmann Graphs

We present a candidate reduction from the $3$-Lin problem to the $2$-to-$2$ Games problem and present a combinatorial hypothesis about
Grassmann graphs which, if correct, is sufficient to show the soundness of the reduction in
a certain non-standard sense. A reduction that is sound in this non-standard sense
implies that ... more >>>

TR01-046 | 2nd July 2001
Oded Goldreich, Salil Vadhan, Avi Wigderson

#### On Interactive Proofs with a Laconic Prover

We continue the investigation of interactive proofs with bounded
communication, as initiated by Goldreich and Hastad (IPL 1998).
Let $L$ be a language that has an interactive proof in which the prover
sends few (say $b$) bits to the verifier.
We prove that the complement $\bar L$ has ... more >>>

TR13-180 | 17th December 2013
Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian

#### On Interactivity in Arthur-Merlin Communication and Stream Computation

Revisions: 1

We introduce {\em online interactive proofs} (OIP), which are a hierarchy of communication complexity models that involve both randomness and nondeterminism (thus, they belong to the Arthur--Merlin family), but are {\em online} in the sense that the basic communication flows from Alice to Bob alone. The complexity classes defined by ... more >>>

TR15-164 | 13th October 2015
Pavel Hrubes, Amir Yehudayoff

#### On isoperimetric profiles and computational complexity

The isoperimetric profile of a graph is a function that measures, for an integer $k$, the size of the smallest edge boundary over all sets of vertices of size $k$. We observe a connection between isoperimetric profiles and computational complexity. We illustrate this connection by an example from communication complexity, ... more >>>

TR08-077 | 23rd May 2008
Felix Brandt, Felix Fischer, Markus Holzer

#### On Iterated Dominance, Matrix Elimination, and Matched Paths

We study computational problems that arise in the context of iterated dominance in anonymous games, and show that deciding whether a game can be solved by means of iterated weak dominance is NP-hard for anonymous games with three actions. For the case of two actions, this problem can be reformulated ... more >>>

TR05-023 | 16th February 2005
Robert H. Sloan, Balázs Szörényi, György Turán

#### On k-term DNF with largest number of prime implicants

It is known that a k-term DNF can have at most 2^k ? 1 prime implicants and this bound is sharp. We determine all k-term DNF having the maximal number of prime implicants. It is shown that a DNF is maximal if and only if it corresponds to a non-repeating ... more >>>

TR14-029 | 4th March 2014
Oded Goldreich, Dana Ron

#### On Learning and Testing Dynamic Environments

Revisions: 3

We initiate a study of learning and testing dynamic environments,
focusing on environment that evolve according to a fixed local rule.
The (proper) learning task consists of obtaining the initial configuration
of the environment, whereas for non-proper learning it suffices to predict
its future values. The testing task consists of ... more >>>

TR96-009 | 17th January 1996

#### On Learning Branching Programs and Small Depth Circuits

This paper studies the learnability of branching programs and small depth
circuits with modular and threshold gates in both the exact and PAC learning
models with and without membership queries. Some of the results extend earlier
works in [GG95,ERR95,BTW95]. The main results are as follows. For
branching programs we ... more >>>

TR01-098 | 19th November 2001
Ke Yang

#### On Learning Correlated Boolean Functions Using Statistical Query

In this paper, we study the problem of using statistical
query (SQ) to learn highly correlated boolean functions, namely, a
class of functions where any
pair agree on significantly more than a fraction 1/2 of the inputs.
We give a limit on how well ... more >>>

TR00-066 | 14th July 2000
Peter Auer

#### On Learning from Ambiguous Information

We investigate a variant of the Probably Almost Correct learning model
where the learner has to learn from ambiguous information. The
ambiguity is introduced by assuming that the learner does not receive
single instances with their correct labels as training data, but that
the learner receives ... more >>>

TR01-006 | 18th October 2000
Rocco Servedio

#### On Learning Monotone DNF under Product Distributions

We show that the class of monotone $2^{O(\sqrt{\log n})}$-term DNF
formulae can be PAC learned in polynomial time under the uniform
distribution. This is an exponential improvement over previous
algorithms in this model, which could learn monotone
$o(\log^2 n)$-term DNF, and is the first efficient algorithm
for ... more >>>

TR00-014 | 16th February 2000
Matthias Krause, Stefan Lucks

#### On Learning versus Distinguishing and the Minimal Hardware Complexity of Pseudorandom Function Generators

\begin{abstract}
A set $F$ of $n$-ary Boolean functions is called a pseudorandom function generator
(PRFG) if communicating
with a randomly chosen secret function from $F$ cannot be
efficiently distinguished from communicating with a truly random function.
We ask for the minimal hardware complexity of a PRFG. This question ... more >>>

TR14-058 | 20th April 2014
Ilya Volkovich

#### On Learning, Lower Bounds and (un)Keeping Promises

We extend the line of research initiated by Fortnow and Klivans \cite{FortnowKlivans09} that studies the relationship between efficient learning algorithms and circuit lower bounds. In \cite{FortnowKlivans09}, it was shown that if a Boolean circuit class $\mathcal{C}$ has an efficient \emph{deterministic} exact learning algorithm, (i.e. an algorithm that uses membership and ... more >>>

TR13-065 | 21st April 2013
Yijia Chen, Joerg Flum

#### On Limitations of the Ehrenfeucht-Fraisse-method in Descriptive Complexity

Ehrenfeucht-Fraisse games and their generalizations have been quite successful in finite model theory and yield various inexpressibility results. However, for key problems such as P $\ne$ NP or NP $\ne$ coNP no progress has been achieved using the games. We show that for these problems it is already hard to ... more >>>

TR97-012 | 19th March 1997
Luca Trevisan

#### On Local versus Global Satisfiability

We prove an extremal combinatorial result regarding
the fraction of satisfiable clauses in boolean CNF
formulae enjoying a locally checkable property, thus
solving a problem that has been open for several years.

We then generalize the problem to arbitrary constraint
satisfaction ... more >>>

TR09-073 | 6th September 2009
Vikraman Arvind, Pushkar Joglekar, Srikanth Srinivasan

#### On Lower Bounds for Constant Width Arithmetic Circuits

The motivation for this paper is to study the complexity of constant-width arithmetic circuits. Our main results are the following.
1. For every k > 1, we provide an explicit polynomial that can be computed by a linear-sized monotone circuit of width 2k but has no subexponential-sized monotone circuit ... more >>>

TR09-134 | 10th December 2009
Zeev Dvir

#### On matrix rigidity and locally self-correctable codes

Revisions: 1

We describe a new approach for the problem of finding {\rm rigid} matrices, as posed by Valiant [Val77], by connecting it to the, seemingly unrelated, problem of proving lower bounds for locally self-correctable codes. This approach, if successful, could lead to a non-natural property (in the sense of Razborov and ... more >>>

TR05-070 | 6th July 2005
Mahdi Cheraghchi

#### On Matrix Rigidity and the Complexity of Linear Forms

The rigidity function of a matrix is defined as the minimum number of its entries that need to be changed in order to reduce the rank of the matrix to below a given parameter. Proving a strong enough lower bound on the rigidity of a matrix implies a nontrivial lower ... more >>>

TR17-183 | 28th November 2017
Sivakanth Gopi, Venkatesan Guruswami, Sergey Yekhanin

#### On Maximally Recoverable Local Reconstruction Codes

In recent years the explosion in the volumes of data being stored online has resulted in distributed storage systems transitioning to erasure coding based schemes. Local Reconstruction Codes (LRCs) have emerged as the codes of choice for these applications. An $(n,r,h,a,q)$-LRC is a $q$-ary code, where encoding is as a ... more >>>

TR09-100 | 16th October 2009
Jakob Nordström, Alexander Razborov

#### On Minimal Unsatisfiability and Time-Space Trade-offs for $k$-DNF Resolution

In the context of proving lower bounds on proof space in $k$-DNF
resolution, [Ben-Sasson and Nordstr&ouml;m 2009] introduced the concept of
minimally unsatisfiable sets of $k$-DNF formulas and proved that a
minimally unsatisfiable $k$-DNF set with $m$ formulas can have at most
$O((mk)^{k+1})$ variables. They also gave an example of ... more >>>

TR15-011 | 22nd January 2015
Subhash Khot, Dor Minzer, Muli Safra

#### On Monotonicity Testing and Boolean Isoperimetric type Theorems

We show a directed and robust analogue of a boolean isoperimetric type theorem of Talagrand. As an application, we
give a monotonicity testing algorithm that makes $\tilde{O}(\sqrt{n}/\epsilon^2)$ non-adaptive queries to a function
$f:\{0,1\}^n \mapsto \{0,1\}$, always accepts a monotone function and rejects a function that is $\epsilon$-far from
being monotone ... more >>>

TR01-049 | 11th July 2001
Stasys Jukna, Georg Schnitger

#### On Multi-Partition Communication Complexity of Triangle-Freeness

We show that recognizing the $K_3$-freeness and $K_4$-freeness of
graphs is hard, respectively, for two-player nondeterministic
communication protocols with exponentially many partitions and for
nondeterministic (syntactic) read-$s$ times branching programs.

The key ingradient is a generalization of a coloring lemma, due to
Papadimitriou and Sipser, which says that for every ... more >>>

TR16-051 | 7th April 2016
Ronald Cramer, Chaoping Xing, chen yuan

#### On Multi-Point Local Decoding of Reed-Muller Codes

Revisions: 2

Reed-Muller codes are among the most important classes of locally correctable codes. Currently local decoding of Reed-Muller codes is based on decoding on lines or quadratic curves to recover one single coordinate. To recover multiple coordinates simultaneously, the naive way is to repeat the local decoding for recovery of a ... more >>>

TR01-066 | 28th September 2001
Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger

#### On Multipartition Communication Complexity

We study k-partition communication protocols, an extension
of the standard two-party best-partition model to k input partitions.
The main results are as follows.

1. A strong explicit hierarchy on the degree of
non-obliviousness is established by proving that,
using k+1 partitions instead of k may decrease
the communication complexity from ... more >>>

TR16-138 | 3rd September 2016
Alexander A. Sherstov

#### On multiparty communication with large versus unbounded error

The communication complexity of $F$ with unbounded error is the limit of the $\epsilon$-error randomized complexity of $F$ as $\epsilon\to1/2.$ Communication complexity with weakly bounded error is defined similarly but with an additive penalty term that depends on $1/2-\epsilon$. Explicit functions are known whose two-party communication complexity with unbounded error ... more >>>

TR13-067 | 2nd May 2013
Oded Goldreich

#### On Multiple Input Problems in Property Testing

Revisions: 1

We consider three types of multiple input problems in the context of property testing.
Specifically, for a property $\Pi\subseteq\{0,1\}^n$, a proximity parameter $\epsilon$, and an integer $m$, we consider the following problems:

\begin{enumerate}
\item Direct $m$-Sum Problem for $\Pi$ and $\epsilon$:
Given a sequence of $m$ inputs, output a sequence ... more >>>

TR96-034 | 28th March 1996

#### On Neural Networks with Minimal Weights

Linear threshold elements are the basic building blocks of artificial neural
networks. A linear threshold element computes a function that is a sign of a
weighted sum of the input variables. The weights are arbitrary integers;
actually, they can be very big integers---exponential in the number of the
input variables. ... more >>>

TR05-058 | 24th May 2005
Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra

#### On Non-Approximability for Quadratic Programs

This paper studies the computational complexity of the following type of
quadratic programs: given an arbitrary matrix whose diagonal elements are zero, find $x \in \{-1,+1\}^n$ that maximizes $x^TA x$. This problem recently attracted attention due to its application in various clustering settings (Charikar and Wirth, 2004) as well as ... more >>>

TR13-094 | 13th June 2013
Brendan Juba

#### On Non-automatizability in PAC-Semantics

We consider the proof search ("automatizability") problem for integrated learning and reasoning, a problem modeling certain kinds of data mining and common sense reasoning (Juba, 2013a). In such a problem, the approximate validity (i.e., under Valiant’s PAC-Semantics (Valiant, 2000)) of an input query formula over a background probability distribution is ... more >>>

TR17-094 | 25th May 2017
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra

#### On Non-Optimally Expanding Sets in Grassmann Graphs

The paper investigates expansion properties of the Grassmann graph,
motivated by recent results of [KMS, DKKMS] concerning hardness
of the Vertex-Cover and of the $2$-to-$1$ Games problems. Proving the
hypotheses put forward by these papers seems to first require a better
understanding of these expansion properties.

We consider the edge ... more >>>

TR97-030 | 25th August 1997
Martin Sauerhoff

#### On Nondeterminism versus Randomness for Read-Once Branching Programs

Randomized branching programs are a probabilistic model of computation
defined in analogy to the well-known probabilistic Turing machines.
In this paper, we present complexity theoretic results for randomized
Our main result shows that nondeterminism can be more powerful than
randomness for read-once branching programs. We present a ... more >>>

TR06-128 | 5th October 2006
Shankar Kalyanaraman, Chris Umans

#### On obtaining pseudorandomness from error-correcting codes.

A number of recent results have constructed randomness extractors
and pseudorandom generators (PRGs) directly from certain
error-correcting codes. The underlying construction in these
results amounts to picking a random index into the codeword and
outputting $m$ consecutive symbols (the codeword is obtained from
the weak random source in the case ... more >>>

TR02-020 | 13th March 2002
Elizaveta Okol'nishnikova

#### On one lower bound for branching programs

The method of obtaining lower bounds on the complexity
of Boolean functions for nondeterministic branching programs
is proposed.
A nonlinear lower bound on the complexity of characteristic
functions of Reed--Muller codes for nondeterministic
branching programs is obtained.

more >>>

TR00-006 | 26th January 2000
E.A. Okol'nishnikiva

#### On operations of geometrical projection and monotone extension

Some operations over Boolean functions are considered. It is shown that
the operation of the geometrical projection and the operation of the
monotone extension can increase the complexity of Boolean functions for
formulas in each finite basis, for switching networks, for branching
programs, and read-$k$-times ... more >>>

TR10-193 | 5th December 2010
Edward Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal

#### On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography

The existence of an optimal propositional proof system is a major open question in proof complexity; many people conjecture that such systems do not exist. Krajicek and Pudlak (1989) show that this question is equivalent to the existence of an algorithm that is optimal on all propositional tautologies. Monroe (2009) ... more >>>

TR11-170 | 16th December 2011

#### On Optimal Multi-Dimensional Mechanism Design

We efficiently solve the optimal multi-dimensional mechanism design problem for independent bidders with arbitrary demand constraints when either the number of bidders is a constant or the number of items is a constant. In the first setting, we need that each bidder's values for the items are sampled from a ... more >>>

TR10-008 | 13th January 2010
Yijia Chen, Joerg Flum

#### On optimal proof systems and logics for PTIME

Revisions: 1

We prove that TAUT has a $p$-optimal proof system if and only if $L_\le$, a logic introduced in [Gurevich, 88], is a P-bounded logic for P. Furthermore, using the method developed in [Chen and Flum, 10], we show that TAUT has no \emph{effective} $p$-optimal proof system under some reasonable complexity-theoretic ... more >>>

TR97-023 | 3rd June 1997
S. Jukna, A. Razborov, Petr Savicky, Ingo Wegener

#### On P versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs

It is known that if a Boolean function f in n variables
has a DNF and a CNF of size at most N then f also has a
(deterministic) decision tree of size $\exp(O(\log n\log^2 N)$.
We show that this simulation {\em cannot} be ... more >>>

TR04-074 | 26th August 2004
Emanuele Viola

#### On Parallel Pseudorandom Generators

Revisions: 1

We study pseudorandom generator (PRG) constructions $G^f : {0,1}^l \to {0,1}^{l+s}$ from one-way functions $f : {0,1}^n \to {0,1}^m$. We consider PRG constructions of the form $G^f(x) = C(f(q_{1}) \ldots f(q_{poly(n)}))$
where $C$ is a polynomial-size constant depth circuit
and $C$ and the $q$'s are generated from $x$ arbitrarily.
more >>>

TR15-039 | 16th March 2015
Anup Rao, Makrand Sinha

#### On Parallelizing Streaming Algorithms

We study the complexity of parallelizing streaming algorithms (or equivalently, branching programs). If $M(f)$ denotes the minimum average memory required to compute a function $f(x_1,x_2, \dots, x_n)$ how much memory is required to compute $f$ on $k$ independent streams that arrive in parallel? We show that when the inputs (updates) ... more >>>

TR07-106 | 10th September 2007
Yijia Chen, Martin Grohe, Magdalena Grüber

#### On Parameterized Approximability

Combining classical approximability questions with parameterized complexity, we introduce a theory of parameterized approximability.
The main intention of this theory is to deal with the efficient approximation of small cost solutions for optimisation problems.

more >>>

TR09-067 | 18th August 2009

#### On Parity Check $(0,1)$-Matrix over $Z_p$

Revisions: 1

We prove that for every prime $p$ there exists a $(0,1)$-matrix
$M$ of size $t_p(n,m)\times n$ where
$$t_p(n,m)=O\left(m+\frac{m\log \frac{n}{m}}{\log \min({m,p})}\right)$$ such that every
$m$ columns of $M$ are linearly independent over $\Z_p$, the field
of integers modulo $p$ (and therefore over any field of
characteristic $p$ and over the real ... more >>>

TR15-132 | 13th August 2015
Daniel Reichman, Igor Shinkar

#### On Percolation and NP-Hardness

Revisions: 2

We consider the robustness of computational hardness of problems
whose input is obtained by applying independent random deletions to worst-case instances.
For some classical NP-hard problems on graphs, such as Coloring, Vertex-Cover, and Hamiltonicity, we examine the complexity of these problems when edges (or vertices) of an arbitrary
graph are ... more >>>

TR08-067 | 4th June 2008
Scott Aaronson

#### On Perfect Completeness for QMA

Whether the class QMA (Quantum Merlin Arthur) is equal to QMA1, or QMA with one-sided error, has been an open problem for years. This note helps to explain why the problem is difficult, by using ideas from real analysis to give a "quantum oracle" relative to which QMA and QMA1 ... more >>>

TR17-013 | 23rd January 2017
Abhishek Bhrushundi, Prahladh Harsha, Srikanth Srinivasan

#### On polynomial approximations over $\mathbb{Z}/2^k\mathbb{Z}$

We study approximation of Boolean functions by low-degree polynomials over the ring $\mathbb{Z}/2^k\mathbb{Z}$. More precisely, given a Boolean function F$:\{0,1\}^n \rightarrow \{0,1\}$, define its $k$-lift to be F$_k:\{0,1\}^n \rightarrow \{0,2^{k-1}\}$ by $F_k(x) = 2^{k-F(x)}$ (mod $2^k$). We consider the fractional agreement (which we refer to as $\gamma_{d,k}(F)$) of $F_k$ with ... more >>>

TR16-068 | 28th April 2016

#### On Polynomial Approximations to $\mathrm{AC}^0$

Revisions: 1

We make progress on some questions related to polynomial approximations of $\mathrm{AC}^0$. It is known, by works of Tarui (Theoret. Comput. Sci. 1993) and Beigel, Reingold, and Spielman (Proc. $6$th CCC 1991), that any $\mathrm{AC}^0$ circuit of size $s$ and depth $d$ has an $\varepsilon$-error probabilistic polynomial over the reals ... more >>>

TR98-054 | 26th August 1998
Igor E. Shparlinski

#### On Polynomial Representations of Boolean Functions Related to Some Number Theoretic Problems

Lower bounds are obtained on the degree and the number of monomials of
Boolean functions, considered as a polynomial over $GF(2)$,
which decide if a given $r$-bit integer is square-free.
Similar lower bounds are also obtained for polynomials
over the reals which provide a threshold representation
more >>>

TR96-043 | 16th August 1996
Edmund Ihler

#### On polynomial time approximation schemes and approximation preserving reductions

We show that a fully polynomial time approximation scheme given
for an optimization problem can always be simply modified to a
polynomial time algorithm solving the problem optimally if the
computation model is the deterministic Turing Machine or the
logarithmic cost RAM and ... more >>>

TR04-031 | 22nd March 2004
Troy Lee, Andrei Romashchenko

#### On Polynomially Time Bounded Symmetry of Information

The information contained in a string $x$ about a string $y$
is defined as the difference between the Kolmogorov complexity
of $y$ and the conditional Kolmogorov complexity of $y$ given $x$,
i.e., $I(x:y)=\C(y)-\C(y|x)$. From the well-known Kolmogorov--Levin Theorem it follows that $I(x:y)$ is symmetric up to a small ... more >>>

TR16-156 | 12th October 2016
Eli Ben-Sasson, Alessandro Chiesa, Michael Forbes, Ariel Gabizon, Michael Riabzev, Nicholas Spooner

#### On Probabilistic Checking in Perfect Zero Knowledge

Revisions: 1

We present the first constructions of *single*-prover proof systems that achieve *perfect* zero knowledge (PZK) for languages beyond NP, under no intractability assumptions:

1. The complexity class #P has PZK proofs in the model of Interactive PCPs (IPCPs) [KR08], where the verifier first receives from the prover a PCP and ... more >>>

TR05-137 | 21st November 2005
Emanuele Viola

#### On Probabilistic Time versus Alternating Time

We prove several new results regarding the relationship between probabilistic time, BPTime(t), and alternating time, \Sigma_{O(1)} Time(t). Our main results are the following:

1) We prove that BPTime(t) \subseteq \Sigma_3 Time(t polylog(t)). Previous results show that BPTime(t) \subseteq \Sigma_2 Time(t^2 log t) (Sipser and Gacs, STOC '83; Lautemann, IPL '83) ... more >>>

TR06-136 | 22nd October 2006
Mihir Bellare, Oded Goldreich

#### On Probabilistic versus Deterministic Provers in the Definition of Proofs Of Knowledge

This note points out a gap between two natural formulations of
the concept of a proof of knowledge, and shows that in all
natural cases (e.g., NP-statements) this gap can be closed.
The aforementioned formulations differ by whether they refer to
(all possible) probabilistic or deterministic prover strategies.
Unlike ... more >>>

TR05-018 | 6th February 2005
Oded Goldreich

#### On Promise Problems (a survey in memory of Shimon Even [1935-2004])

The notion of promise problems was introduced and initially studied
by Even, Selman and Yacobi
(Information and Control, Vol.~61, pages 159-173, 1984).
notion has found in the twenty years that elapsed.
These include the notion ... more >>>

TR13-097 | 25th June 2013
Mikolas Janota, Joao Marques-Silva

#### On Propositional QBF Expansions and Q-Resolution

Over the years, proof systems for propositional satisfiability (SAT)
have been extensively studied. Recently, proof systems for
quantified Boolean formulas (QBFs) have also been gaining attention.
Q-resolution is a calculus enabling producing proofs from
DPLL-based QBF solvers. While DPLL has become a dominating technique
for SAT, QBF has been tackled ... more >>>

TR94-006 | 12th December 1994
Alexander Razborov

#### On provably disjoint NP-pairs

In this paper we study the pairs $(U,V)$ of disjoint ${\bf NP}$-sets
representable in a theory $T$ of Bounded Arithmetic in the sense that
$T$ proves $U\cap V=\emptyset$. For a large variety of theories $T$
we exhibit a natural disjoint ${\bf NP}$-pair which is complete for the
class of disjoint ... more >>>

TR08-041 | 10th April 2008
Oded Goldreich, Dana Ron

#### On Proximity Oblivious Testing

We initiate a systematic study of a special type of property testers.
These testers consist of repeating a basic test
for a number of times that depends on the proximity parameters,
whereas the basic test is oblivious of the proximity parameter.
We refer to such basic ... more >>>

TR00-056 | 20th July 2000
Oded Goldreich, Avi Wigderson

#### On Pseudorandomness with respect to Deterministic Observers.

In the theory of pseudorandomness, potential (uniform) observers
are modeled as probabilistic polynomial-time machines.
In fact many of the central results in
that theory are proven via probabilistic polynomial-time reductions.
In this paper we show that analogous deterministic reductions
are unlikely to hold. We conclude that randomness ... more >>>

TR15-094 | 10th June 2015
Eli Ben-Sasson, iddo Ben-Tov, Ivan Bjerre Damgard, Yuval Ishai, Noga Ron-Zewi

#### On Public Key Encryption from Noisy Codewords

Several well-known public key encryption schemes, including those of Alekhnovich (FOCS 2003), Regev (STOC 2005), and Gentry, Peikert and Vaikuntanathan (STOC 2008), rely on the conjectured intractability of inverting noisy linear encodings. These schemes are limited in that they either require the underlying field to grow with the security parameter, ... more >>>

TR16-043 | 23rd February 2016
Mikolas Janota

#### On Q-Resolution and CDCL QBF Solving

Q-resolution and its variations provide the underlying proof
systems for the DPLL-based QBF solvers. While (long-distance) Q-resolution
models a conflict driven clause learning (CDCL) QBF solver, it is not
known whether the inverse is also true. This paper provides a negative
answer to this question. This contrasts with SAT solving, ... more >>>

TR05-007 | 15th December 2004

#### On Random High Density Subset Sums

In the Subset Sum problem, we are given n integers a_1,...,a_n
and a target number t, and are asked to find the subset of the
a_i's such that the sum is t. A version of the subset sum
problem is the Random Modular Subset Sum problem. In this version,
the ... more >>>

TR98-068 | 12th November 1998
Petr Savicky

#### On Random Orderings of Variables for Parity OBDDs

There are Boolean functions such that almost all orderings of
its variables yield an OBDD of polynomial size, but there are
also some exceptional orderings, for which the size is exponential.
We prove that for parity OBDDs the size for a random ordering
... more >>>

TR95-021 | 20th April 1995
Marek Karpinski, Rutger Verbeek

#### On Randomized Versus Deterministic Computation

In contrast to deterministic or nondeterministic computation, it is
a fundamental open problem in randomized computation how to separate
different randomized time classes (at this point we do not even know
how to separate linear randomized time from ${\mathcal O}(n^{\log n})$
randomized time) or how to ... more >>>

TR15-003 | 3rd January 2015
Oded Goldreich, Emanuele Viola, Avi Wigderson

#### On Randomness Extraction in AC0

We consider randomness extraction by AC0 circuits. The main parameter, $n$, is the length of the source, and all other parameters are functions of it. The additional extraction parameters are the min-entropy bound $k=k(n)$, the seed length $r=r(n)$, the output length $m=m(n)$, and the (output) deviation bound $\epsilon=\epsilon(n)$.

For $k ... more >>> TR94-001 | 12th December 1994 Noam Nisan, Avi Wigderson #### On Rank vs. Communication Complexity This paper concerns the open problem of Lovasz and Saks regarding the relationship between the communication complexity of a boolean function and the rank of the associated matrix. We first give an example exhibiting the largest gap known. We then prove two related theorems. more >>> TR01-044 | 14th June 2001 Pavel Pudlak #### On reducibility and symmetry of disjoint NP-pairs We consider some problems about pairs of disjoint$NP$sets. The theory of these sets with a natural concept of reducibility is, on the one hand, closely related to the theory of proof systems for propositional calculus, and, on the other, it resembles the theory of NP completeness. Furthermore, such more >>> TR12-133 | 21st October 2012 Noga Alon, Gil Cohen #### On Rigid Matrices and Subspace Polynomials Revisions: 1 We introduce a class of polynomials, which we call \emph{subspace polynomials} and show that the problem of explicitly constructing a rigid matrix can be reduced to the problem of explicitly constructing a small hitting set for this class. We prove that small-bias sets are hitting sets for the class of ... more >>> TR13-109 | 11th August 2013 Oded Goldreich, Dana Ron #### On Sample-Based Testers Revisions: 1 The standard definition of property testing endows the tester with the ability to make arbitrary queries to elements'' of the tested object. In contrast, sample-based testers only obtain independently distributed elements (a.k.a. labeled samples) of the tested object. While sample-based testers were defined by Goldreich, Goldwasser, and Ron ({\em JACM}\/ ... more >>> TR98-028 | 28th May 1998 Paul Beame, Faith Fich #### On Searching Sorted Lists: A Near-Optimal Lower Bound We obtain improved lower bounds for a class of static and dynamic data structure problems that includes several problems of searching sorted lists as special cases. These lower bounds nearly match the upper bounds given by recent striking improvements in searching algorithms given by Fredman and Willard's ... more >>> TR01-022 | 15th February 2001 Rahul Santhanam #### On segregators, separators and time versus space We give the first extension of the result due to Paul, Pippenger, Szemeredi and Trotter that deterministic linear time is distinct from nondeterministic linear time. We show that DTIME(n \sqrt(log^{*}(n))) \neq NTIME(n \sqrt(log^{*}(n))). We show that atleast one of the following statements holds: (1) P \neq L ... more >>> TR98-002 | 8th January 1998 Jayram S. Thathachar #### On Separating the Read-k-Times Branching Program Hierarchy We obtain an exponential separation between consecutive levels in the hierarchy of classes of functions computable by polynomial-size syntactic read-$k$-times branching programs, for {\em all\/}$k>0$, as conjectured by various authors~\cite{weg87,ss93,pon95b}. For every$k$, we exhibit two explicit functions that can be computed by linear-sized read-$(\kpluso)$-times branching programs but ... more >>> TR15-090 | 1st June 2015 Alexander Kozachinsky #### On Slepian--Wolf Theorem with Interaction Revisions: 1 In this paper we study interactive one-shot'' analogues of the classical Slepian-Wolf theorem. Alice receives a value of a random variable$X$, Bob receives a value of another random variable$Y$that is jointly distributed with$X$. Alice's goal is to transmit$X$to Bob (with some error probability$\varepsilon$). ... more >>> TR17-142 | 21st September 2017 Johan Hastad #### On small-depth Frege proofs for Tseitin for grids We prove that a small-depth Frege refutation of the Tseitin contradiction on the grid requires subexponential size. We conclude that polynomial size Frege refutations of the Tseitin contradiction must use formulas of almost logarithmic depth. more >>> TR98-029 | 27th May 1998 Piotr Berman, Marek Karpinski #### On Some Tighter Inapproximability Results We prove a number of improved inaproximability results, including the best up to date explicit approximation thresholds for MIS problem of bounded degree, bounded occurrences MAX-2SAT, and bounded degree Node Cover. We prove also for the first time inapproximability of the problem of Sorting by ... more >>> TR98-065 | 6th November 1998 Piotr Berman, Marek Karpinski #### On Some Tighter Inapproximability Results, Further Improvements Improved inaproximability results are given, including the best up to date explicit approximation thresholds for bounded occurence satisfiability problems, like MAX-2SAT and E2-LIN-2, and problems in bounded degree graphs, like MIS, Node Cover and MAX CUT. We prove also for the first time inapproximability more >>> TR16-184 | 16th November 2016 Alexander Razborov #### On Space and Depth in Resolution We show that the total space in resolution, as well as in any other reasonable proof system, is equal (up to a polynomial and$(\log n)^{O(1)}$factors) to the minimum refutation depth. In particular, all these variants of total space are equivalent in this sense. The same conclusion holds for ... more >>> TR03-023 | 12th February 2003 Anna Palbom #### On Spanning Cacti and Asymmetric TSP In an attempt to generalize Christofides algorithm for metric TSP to the asymmetric TSP with triangle inequality we have studied various properties of directed spanning cacti. In this paper we first observe that finding the TSP in a directed, weighted complete graph with triangle inequality is polynomial time equivalent to ... more >>> TR13-070 | 4th May 2013 Iddo Tzameret #### On Sparser Random 3SAT Refutation Algorithms and Feasible Interpolation Revisions: 1 We formalize a combinatorial principle, called the 3XOR principle, due to Feige, Kim and Ofek (2006), as a family of unsatisfiable propositional formulas for which refutations of small size in any propositional proof system that possesses the feasible interpolation property imply an efficient *deterministic* refutation algorithm for random 3SAT with ... more >>> TR03-014 | 28th February 2003 Avrim Blum, Ke Yang #### On Statistical Query Sampling and NMR Quantum Computing We introduce a Statistical Query Sampling'' model, in which the goal of an algorithm is to produce an element in a hidden set$S\subseteq\bit^n$with reasonable probability. The algorithm gains information about$S$through oracle calls (statistical queries), where the algorithm submits a query function$g(\cdot)$and receives ... more >>> TR11-079 | 9th May 2011 Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan #### On Sums of Locally Testable Affine Invariant Properties Affine-invariant properties are an abstract class of properties that generalize some central algebraic ones, such as linearity and low-degree-ness, that have been studied extensively in the context of property testing. Affine invariant properties consider functions mapping a big field$\mathbb{F}_{q^n}$to the subfield$\mathbb{F}_q$and include all properties that form ... more >>> TR11-067 | 25th April 2011 Noga Alon, Amir Shpilka, Chris Umans #### On Sunflowers and Matrix Multiplication Comments: 1 We present several variants of the sunflower conjecture of Erd\H{o}s and Rado and discuss the relations among them. We then show that two of these conjectures (if true) imply negative answers to questions of Coppersmith and Winograd and Cohn et al. regarding possible approaches for obtaining fast matrix multiplication algorithms. ... more >>> TR06-135 | 22nd October 2006 Jin-Yi Cai, Pinyan Lu #### On Symmetric Signatures in Holographic Algorithms The most intriguing aspect of the new theory of matchgate computations and holographic algorithms by Valiant~\cite{Valiant:Quantum} \cite{Valiant:Holographic} is that its reach and ultimate capability are wide open. The methodology produces unexpected polynomial time algorithms solving problems which seem to require exponential time. To sustain our belief in P$\not =$... more >>> TR95-023 | 16th May 1995 Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh Vazirani #### On Syntactic versus Computational views of Approximability We attempt to reconcile the two distinct views of approximation classes: syntactic and computational. Syntactic classes such as MAX SNP allow for clean complexity-theoretic results and natural complete problems, while computational classes such as APX allow us to work with problems whose approximability is well-understood. Our results give a computational ... more >>> TR16-140 | 9th September 2016 Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan #### On SZK and PP Revisions: 3 In both query and communication complexity, we give separations between the class NISZK, containing those problems with non-interactive statistical zero knowledge proof systems, and the class UPP, containing those problems with randomized algorithms with unbounded error. These results significantly improve on earlier query separations of Vereschagin [Ver95] and Aaronson [Aar12] ... more >>> TR97-016 | 29th April 1997 Manindra Agrawal, Eric Allender, Samir Datta #### On TC^0, AC^0, and Arithmetic Circuits Continuing a line of investigation that has studied the function classes #P, #SAC^1, #L, and #NC^1, we study the class of functions #AC^0. One way to define #AC^0 is as the class of functions computed by constant-depth polynomial-size arithmetic circuits of unbounded fan-in addition ... more >>> TR13-166 | 28th November 2013 Arnab Bhattacharyya #### On testing affine-invariant properties An affine-invariant property over a finite field is a property of functions over F_p^n that is closed under all affine transformations of the domain. This class of properties includes such well-known beasts as low-degree polynomials, polynomials that nontrivially factor, and functions of low spectral norm. The last few years has ... more >>> TR13-089 | 17th June 2013 Abhishek Bhrushundi #### On testing bent functions Revisions: 1 A bent function is a Boolean function all of whose Fourier coefficients are equal in absolute value. These functions have been extensively studied in cryptography and play an important role in cryptanalysis and design of cryptographic systems. We study bent functions in the framework of property testing. In particular, we ... more >>> TR10-061 | 10th April 2010 Oded Goldreich #### On Testing Computability by Small Width OBDDs Revisions: 2 We take another step in the study of the testability of small-width OBDDs, initiated by Ron and Tsur (Random'09). That is, we consider algorithms that, given oracle access to a function$f:\{0,1\}^n\to\{0,1\}$, need to determine whether$f$can be implemented by some restricted class of OBDDs or is far from more >>> TR00-020 | 27th March 2000 Oded Goldreich, Dana Ron #### On Testing Expansion in Bounded-Degree Graphs We consider testing graph expansion in the bounded-degree graph model. Specifically, we refer to algorithms for testing whether the graph has a second eigenvalue bounded above by a given threshold or is far from any graph with such (or related) property. We present a natural algorithm aimed ... more >>> TR14-145 | 4th November 2014 Yuan Li, Alexander Razborov, Benjamin Rossman #### On the$AC^0$Complexity of Subgraph Isomorphism Let$P$be a fixed graph (hereafter called a pattern''), and let$Subgraph(P)$denote the problem of deciding whether a given graph$G$contains a subgraph isomorphic to$P$. We are interested in$AC^0$-complexity of this problem, determined by the smallest possible exponent$C(P)$for which$Subgraph(P)$possesses bounded-depth circuits ... more >>> TR03-085 | 28th November 2003 Ke Yang #### On the (Im)possibility of Non-interactive Correlation Distillation We study the problem of non-interactive correlation distillation (NICD). Suppose Alice and Bob each has a string, denoted by$A=a_0a_1\cdots a_{n-1}$and$B=b_0b_1\cdots b_{n-1}$, respectively. Furthermore, for every$k=0,1,...,n-1$,$(a_k,b_k)$is independently drawn from a distribution$\noise$, known as the noise mode''. Alice and Bob wish to distill'' the correlation more >>> TR01-057 | 15th August 2001 Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, Ke Yang #### On the (Im)possibility of Obfuscating Programs Informally, an <i>obfuscator</i> <b>O</b> is an (efficient, probabilistic) "compiler" that takes as input a program (or circuit) <b>P</b> and produces a new program <b>O(P)</b> that has the same functionality as <b>P</b> yet is "unintelligible" in some sense. Obfuscators, if they exist, would have a wide variety of cryptographic ... more >>> TR03-015 | 20th March 2003 Yael Tauman #### On the (In)security of the Fiat-Shamir Paradigm In 1986, Fiat and Shamir suggested a general method for transforming secure 3-round public-coin identification schemes into digital signature schemes. The significant contribution of this method is a means for designing efficient digital signatures, while hopefully achieving security against chosen message attacks. All other known constructions which achieve such security ... more >>> TR14-164 | 30th November 2014 Cody Murray, Ryan Williams #### On the (Non) NP-Hardness of Computing Circuit Complexity The Minimum Circuit Size Problem (MCSP) is: given the truth table of a Boolean function$f$and a size parameter$k$, is the circuit complexity of$f$at most$k$? This is the definitive problem of circuit synthesis, and it has been studied since the 1950s. Unlike many problems of ... more >>> TR07-104 | 15th September 2007 Moses Charikar, Konstantin Makarychev, Yury Makarychev #### On the Advantage over Random for Maximum Acyclic Subgraph In this paper we present a new approximation algorithm for the MAX ACYCLIC SUBGRAPH problem. Given an instance where the maximum acyclic subgraph contains (1/2 + delta) fraction of all edges, our algorithm finds an acyclic subgraph with (1/2 + Omega(delta/ log n)) fraction of all edges. more >>> TR00-017 | 3rd March 2000 Valentin E. Brimkov, Stefan S. Dantchev #### On the Algebraic Complexity of Integer Programming In the framework of the Blum-Shub-Smale real number model \cite{BSS}, we study the {\em algebraic complexity} of the integer linear programming problem (ILP$_{\bf R}$) : Given a matrix$A \in {\bf R}^{m \times n}$and vectors$b \in {\bf R}^m$,$d \in {\bf R}^n$, decide if there is$x ... more >>>

TR11-019 | 5th February 2011
Valentin Brimkov, Andrew Leach, Jimmy Wu, Michael Mastroianni

#### On the Approximability of a Geometric Set Cover Problem

Given a finite set of straight line segments $S$ in $R^{2}$ and some $k\in N$, is there a subset $V$ of points on segments in $S$ with $\vert V \vert \leq k$ such that each segment of $S$ contains at least one point in $V$? This is a special case ... more >>>

TR96-015 | 12th December 1995
Edoardo Amaldi, Viggo Kann

#### On the approximability of some NP-hard minimization problems for linear systems

We investigate the computational complexity of two classes of
combinatorial optimization problems related to linear systems
and study the relationship between their approximability properties.
In the first class (MIN ULR) one wishes, given a possibly infeasible
system of linear relations, to find ... more >>>

TR96-046 | 27th August 1996
Luca Trevisan

#### On the Approximability of the Multi-dimensional Euclidean TSP

Revisions: 1

We consider the Traveling Salesperson Problem (TSP) restricted
to Euclidean spaces of dimension at most k(n), where n is the number of
cities. We are interested in the relation between the asymptotic growth of
k(n) and the approximability of the problem. We show that the problem is ... more >>>

TR06-031 | 27th February 2006
Li-Sha Huang, Shang-Hua Teng

#### On the Approximation and Smoothed Complexity of Leontief Market Equilibria

We show that the problem of finding an \epsilon-approximate Nash equilibrium af an n*n two-person game can be reduced to the computation of an (\epsilon/n)^2-approximate market equilibrium of a Leontief economy. Together with a recent result of Chen, Deng and Teng, this polynomial reduction implies that the Leontief market exchange ... more >>>

TR09-014 | 7th February 2009
Soren Riis

#### On the asymptotic Nullstellensatz and Polynomial Calculus proof complexity

We show that the asymptotic complexity of uniformly generated (expressible in First-Order (FO) logic) propositional tautologies for the Nullstellensatz proof system (NS) as well as for Polynomial Calculus, (PC) has four distinct types of asymptotic behavior over fields of finite characteristic. More precisely, based on some highly non-trivial work by ... more >>>

TR09-035 | 26th March 2009
Nicola Galesi, Massimo Lauria

#### On the Automatizability of Polynomial Calculus

We prove that Polynomial Calculus and Polynomial Calculus with Resolution are not automatizable, unless W[P]-hard problems are fixed parameter tractable by one-side error randomized algorithms. This extends to Polynomial Calculus the analogous result obtained for Resolution by Alekhnovich and Razborov (SIAM J. Computing, 38(4), 2008).

more >>>

TR02-010 | 21st January 2002
Albert Atserias, Maria Luisa Bonet

#### On the Automatizability of Resolution and Related Propositional Proof Systems

Having good algorithms to verify tautologies as efficiently as possible
is of prime interest in different fields of computer science.
In this paper we present an algorithm for finding Resolution refutations
based on finding tree-like Res(k) refutations. The algorithm is based on
the one of Beame and Pitassi \cite{BP96} ... more >>>

TR02-056 | 19th September 2002
Todd Ebert, Wolfgang Merkle, Heribert Vollmer

#### On the Autoreducibility of Random Sequences

A binary sequence A=A(0)A(1).... is called i.o. Turing-autoreducible if A is reducible to itself via an oracle Turing machine that never queries its oracle at the current input, outputs either A(x) or a don't-know symbol on any given input x, and outputs A(x) for infinitely many x. If in addition ... more >>>

TR07-057 | 11th July 2007
Oded Goldreich

#### On the Average-Case Complexity of Property Testing

Revisions: 1

Motivated by a recent study of Zimand (22nd CCC, 2007),
we consider the average-case complexity of property testing
(focusing, for clarity, on testing properties of Boolean strings).
We make two observations:

1) In the context of average-case analysis with respect to
the uniform distribution (on all strings of ... more >>>

TR15-190 | 2nd November 2015
Esther Ezra, Shachar Lovett

#### On the Beck-Fiala Conjecture for Random Set Systems

Motivated by the Beck-Fiala conjecture, we study discrepancy bounds for random sparse set systems. Concretely, these are set systems $(X,\Sigma)$, where each element $x \in X$ lies in $t$ randomly selected sets of $\Sigma$, where $t$ is an integer parameter. We provide new bounds in two regimes of parameters. We ... more >>>

TR12-093 | 1st July 2012
Charanjit Jutla, Vijay Kumar, Atri Rudra

#### On the Circuit Complexity of Composite Galois Field Transformations

We study the circuit complexity of linear transformations between Galois fields GF(2^{mn}) and their isomorphic composite fields GF((2^{m})^n). For such a transformation, we show a lower bound of \Omega(mn) on the number of gates required in any circuit consisting of constant-fan-in XOR gates, except for a class of transformations between ... more >>>

TR96-041 | 24th July 1996
Oded Goldreich, Avi Wigderson

#### On the Circuit Complexity of Perfect Hashing

We consider the size of circuits which perfectly hash
an arbitrary subset $S\!\subset\!\bitset^n$ of cardinality $2^k$
into $\bitset^m$.
We observe that, in general, the size of such circuits is
exponential in $2k-m$,
and provide a matching upper bound.

more >>>

TR13-073 | 14th May 2013
Oded Goldreich

#### On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing

Revisions: 2

A couple of years ago, Blais, Brody, and Matulef put forward a methodology for proving lower bounds on the query complexity
of property testing via communication complexity. They provided a restricted formulation of their methodology
(via simple combining operators'')
and also hinted towards a more general formulation, which we spell ... more >>>

TR16-055 | 11th April 2016
Tim Roughgarden, Omri Weinstein

#### On the Communication Complexity of Approximate Fixed Points

We study the two-party communication complexity of finding an approximate Brouwer fixed point of a composition
of two Lipschitz functions $g\circ f : [0,1]^n \to [0,1]^n$, where Alice holds $f$ and Bob holds $g$. We prove an
exponential (in $n$) lower bound on the deterministic ... more >>>

TR06-037 | 10th February 2006
Xi Chen, Xiaotie Deng

#### On the Complexity of 2D Discrete Fixed Point Problem

While the 3-dimensional analogue of the Sperner problem in the plane was known to be PPAD-complete, the complexity of the 2D-SPERNER itself is not known to be PPAD-complete or not. In this paper, we settle this open problem proposed by Papadimitriou~\cite{PAP90} fifteen years ago. This also allows us to derive ... more >>>

TR09-048 | 29th May 2009
Parikshit Gopalan, Shachar Lovett, Amir Shpilka

#### On the Complexity of Boolean Functions in Different Characteristics

Every Boolean function on $n$ variables can be expressed as a unique multivariate polynomial modulo $p$ for every prime $p$. In this work, we study how the degree of a function in one characteristic affects its complexity in other characteristics. We establish the following general principle: functions with low degree ... more >>>

TR11-004 | 10th January 2011

#### On the complexity of computational problems regarding distributions (a survey)

We consider two basic computational problems
regarding discrete probability distributions:
(1) approximating the statistical difference (aka variation distance)
between two given distributions,
and (2) approximating the entropy of a given distribution.
Both problems are considered in two different settings.
In the first setting the approximation algorithm
more >>>

TR00-086 | 26th September 2000
Michael Schmitt

#### On the Complexity of Computing and Learning with Multiplicative Neural Networks

In a great variety of neuron models neural inputs are
combined using the summing operation. We introduce the concept of
multiplicative neural networks which contain units that multiply
their inputs instead of summing them and, thus, allow inputs to
interact nonlinearly. The class of multiplicative networks
comprises such widely known ... more >>>

TR12-069 | 23rd March 2012
Lakhdar Saïs, Mohand-Saïd Hacid, francois hantry

#### On the complexity of computing minimal unsatisfiable LTL formulas

We show that (1) the Minimal False QCNF search problem (MF-search) and
the Minimal Unsatisfiable LTL formula search problem (MU-search) are FPSPACE complete because of the very expressive power of QBF/LTL, (2) we extend the PSPACE-hardness of the MF decision problem to the MU decision problem. As a consequence, we ... more >>>

TR12-019 | 2nd March 2012
Eric Miles, Emanuele Viola

#### On the complexity of constructing pseudorandom functions (especially when they don't exist)

We study the complexity of black-box constructions of
pseudorandom functions (PRF) from one-way functions (OWF)
that are secure against non-uniform adversaries. We show
that if OWF do not exist, then given as an oracle any
(inefficient) hard-to-invert function, one can compute a
PRF in polynomial time with only $k(n)$ oracle ... more >>>

TR08-084 | 16th June 2008
Sanjeeb Dash

#### On the complexity of cutting plane proofs using split cuts

We prove a monotone interpolation property for split cuts which, together with results from Pudlak (1997), implies that cutting-plane proofs which use split cuts have exponential length in the worst case.
As split cuts are equivalent to mixed-integer rounding cuts and Gomory mixed-integer cuts, cutting-plane proofs using the above cuts ... more >>>

TR99-038 | 27th August 1999
Peter Jonsson, Paolo Liberatore

#### On the Complexity of Finding Satisfiable Subinstances in Constraint Satisfaction

We study the computational complexity of an optimization
version of the constraint satisfaction problem: given a set $F$ of
constraint functions, an instance consists of a set of variables $V$
related by constraints chosen from $F$ and a natural number $k$. The
problem is to decide whether there exists a ... more >>>

TR00-050 | 13th July 2000
Peter Auer, Philip M. Long, Gerhard J. Woeginger

#### On the Complexity of Function Learning

The majority of results in computational learning theory
are concerned with concept learning, i.e. with the special
case of function learning for classes of functions
with range {0,1}. Much less is known about the theory of
learning functions with a larger range such
as N or R. In ... more >>>

TR11-052 | 4th April 2011
Fabian Wagner

#### On the Complexity of Group Isomorphism

The group isomorphism problem consists in deciding whether two groups $G$ and $H$
given by their multiplication tables are isomorphic.
An algorithm for group isomorphism attributed to Tarjan runs in time $n^{\log n + O(1)}$, c.f. [Mil78].

Miller and Monk showed in [Mil79] that group isomorphism can be many-one ... more >>>

TR01-076 | 24th October 2001
Robert Albin Legenstein

#### On the Complexity of Knock-knee Channel-Routing with 3-Terminal Nets

In this article we consider a basic problem in the layout of
VLSI-circuits, the channel-routing problem in the knock-knee mode.
We show that knock-knee channel routing with 3-terminal nets is
NP-complete and thereby settling a problem that was open for more
than a decade. In 1987, Sarrafzadeh showed that knock-knee ... more >>>

TR97-049 | 22nd October 1997
Michael Schmitt

#### On the Complexity of Learning for Spiking Neurons with Temporal Coding

Spiking neurons are models for the computational units in
biological neural systems where information is considered to be encoded
mainly in the temporal pattern of their activity. In a network of
spiking neurons a new set of parameters becomes relevant which has no
counterpart in traditional ... more >>>

TR02-012 | 3rd February 2002
Ran Raz

#### On the Complexity of Matrix Product

We prove a lower bound of $\Omega(m^2 \log m)$ for the size of
any arithmetic circuit for the product of two matrices,
over the real or complex numbers, as long as the circuit doesn't
use products with field elements of absolute value larger than 1
(where $m \times m$ is ... more >>>

TR15-004 | 4th January 2015
Vikraman Arvind, Pushkar Joglekar, Gaurav Rattan

#### On the Complexity of Noncommutative Polynomial Factorization

In this paper we study the complexity of factorization of polynomials in the free noncommutative ring $\mathbb{F}\langle x_1,x_2,\ldots,x_n\rangle$ of polynomials over the field $\mathbb{F}$ and noncommuting variables $x_1,x_2,\ldots,x_n$. Our main results are the following.

Although $\mathbb{F}\langle x_1,\dots,x_n \rangle$ is not a unique factorization ring, we note that variable-disjoint factorization in ... more >>>

TR05-037 | 8th April 2005
Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen

#### On the Complexity of Numerical Analysis

We study two quite different approaches to understanding the complexity
of fundamental problems in numerical analysis. We show that both hinge
on the question of understanding the complexity of the following problem,
which we call PosSLP:
Given a division-free straight-line program
producing an integer N, decide whether N>0.
more >>>

TR13-041 | 14th March 2013
Igor Sergeev

#### On the complexity of parallel prefix circuits

It is shown that complexity of implementation of prefix sums of $m$ variables (i.e. functions $x_1 \cdot \ldots\cdot x_i$, $1\le i \le m$) by circuits of depth $\lceil \log_2 m \rceil$ in the case $m=2^n$ is exactly $$3.5\cdot2^n - (8.5+3.5(n \bmod 2))2^{\lfloor n/2\rfloor} + n + 5.$$ As a consequence, ... more >>>

TR01-054 | 12th April 2001
Amir Ben-Dor, Itsik Pe'er, Roded Sharan, Ron Shamir

#### On the Complexity of Positional Sequencing by Hybridization

In sequencing by hybridization (SBH),
one has to reconstruct a sequence
from its $l$-long substrings.
SBH was proposed as
an alternative to
gel-based
DNA sequencing approaches, but in its original form the method
is
not competitive.
Positional SBH (PSBH) is a recently proposed
enhancement ... more >>>

TR14-148 | 8th November 2014
Vitaly Feldman, Will Perkins, Santosh Vempala

#### On the Complexity of Random Satisfiability Problems with Planted Solutions

Revisions: 1

We consider the problem of identifying a planted assignment given a random $k$-SAT formula consistent with the assignment. This problem exhibits a large algorithmic gap: while the planted solution can always be identified given a formula with $O(n\log n)$ clauses, there are distributions over clauses for which the best known ... more >>>

TR06-100 | 17th July 2006
Meena Mahajan, Jayalal Sarma

#### On the Complexity of Rank and Rigidity

Given a matrix $M$ over a ring \Ringk, a target rank $r$ and a bound
$k$, we want to decide whether the rank of $M$ can be brought down to
below $r$ by changing at most $k$ entries of $M$. This is a decision
version of the well-studied notion of ... more >>>

TR04-001 | 11th December 2003
Lance Fortnow, Russell Impagliazzo, Chris Umans

#### On the complexity of succinct zero-sum games

We study the complexity of solving succinct zero-sum games,
i.e., the
games whose payoff matrix $M$ is given implicitly by a Boolean circuit
$C$ such that $M(i,j)=C(i,j)$. We complement the known $\EXP$-hardness
of computing the \emph{exact} value of a succinct zero-sum game by
several results on \emph{approximating} the value. (1) ... more >>>

TR12-067 | 6th May 2012
Xiaohui Bei, Ning Chen, Shengyu Zhang

#### On the Complexity of Trial and Error

Revisions: 1

Motivated by certain applications from physics, biochemistry, economics, and computer science in which the objects under investigation are unknown or not directly accessible because of various limitations, we propose a trial-and-error model to examine search problems with unknown inputs. Given a search problem with a hidden input, we are asked ... more >>>

TR14-034 | 3rd March 2014
Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, Miklos Santha, Aarthi Sundaram

#### On the complexity of trial and error for constraint satisfaction problems

In a recent work of Bei, Chen and Zhang (STOC 2013), a trial and error model of computing was introduced, and applied to some constraint satisfaction problems. In this model the input is hidden by an oracle which, for a candidate assignment, reveals some information about a violated constraint if ... more >>>

TR06-022 | 17th February 2006
Danny Harnik, Moni Naor

#### On the Compressibility of NP Instances and Cryptographic Applications

Revisions: 1

We initiate the study of the compressibility of NP problems. We
consider NP problems that have long instances but relatively
short witnesses. The question is, can one efficiently compress an
instance and store a shorter representation that maintains the
information of whether the original input is in the language or
more >>>

TR08-059 | 20th May 2008
Farid Ablayev, Alexander Vasiliev

#### On the Computation of Boolean Functions by Quantum Branching Programs via Fingerprinting

Revisions: 1

We develop quantum fingerprinting technique for constructing quantum
branching programs (QBPs), which are considered as circuits with an
ability to use classical bits as control variables.

We demonstrate our approach constructing optimal quantum ordered
binary decision diagram (QOBDD) for $MOD_m$ and $DMULT_n$ Boolean
functions. The construction of our technique also ... more >>>

TR16-034 | 7th March 2016
Mohamed El Halaby

#### On the Computational Complexity of MaxSAT

Revisions: 1

Given a Boolean formula in Conjunctive Normal Form (CNF) $\phi=S \cup H$, the MaxSAT (Maximum Satisfiability) problem asks for an assignment that satisfies the maximum number of clauses in $\phi$. Due to the good performance of current MaxSAT solvers, many real-life optimization problems such as scheduling can be solved efficiently ... more >>>

TR96-033 | 6th March 1996
Bernd Borchert, Desh Ranjan, Frank Stephan

#### On the Computational Complexity of some Classical Equivalence Relations on Boolean Functions

The paper analyzes in terms of polynomial time many-one reductions
the computational complexity of several natural equivalence
relations on Boolean functions which derive from replacing
variables by expressions. Most of these computational problems
turn out to be between co-NP and Sigma^p_2.

more >>>

TR04-116 | 18th November 2004
PERRET ludovic

#### On the computational complexity of some equivalence problems of polynomial systems of equations over finite fields

We study in this paper the computational complexity of some
equivalence relations on polynomial systems of equations over finite
fields. These problems are analyzed with respect to polynomial-time
many-one reductions (resp. Turing reductions, Levin reductions). In
particular, we show that some of these problems are between ... more >>>

TR99-027 | 17th July 1999
Marek Karpinski, Igor E. Shparlinski

#### On the computational hardness of testing square-freeness of sparse polynomials

We show that deciding square-freeness of a sparse univariate
polynomial over the integer and over the algebraic closure of a
finite field is NP-hard. We also discuss some related open

more >>>

TR94-023 | 12th December 1994
Matthias Krause, Pavel Pudlak

#### On the Computational Power of Depth 2 Circuits with Threshold and Modulo Gates

We investigate the computational power of depth two circuits
consisting of $MOD^r$--gates at the bottom and a threshold gate at
the top (for short, threshold--$MOD^r$ circuits) and circuits with
two levels of $MOD$ gates ($MOD^{p}$-$MOD^q$ circuits.) In particular, we
will show the following results

(i) For all prime numbers ... more >>>

TR98-038 | 9th July 1998
Marek Karpinski

#### On the Computational Power of Randomized Branching Programs

We survey some upper and lower bounds established recently on
the sizes of randomized branching programs computing explicit
boolean functions. In particular, we display boolean
functions on which randomized read-once ordered branching
programs are exponentially more powerful than deterministic
or nondeterministic read-$k$-times branching programs for ... more >>>

TR02-022 | 12th April 2002
Henry Markram

#### On the Computational Power of Recurrent Circuits of Spiking Neurons

Understanding the structure of real-time neural computation in
highly recurrent neural microcircuits that consist of complex
heterogeneous components has remained a serious challenge for
computational modeling. We propose here a new conceptual framework
that strongly differs from all previous approaches based on
computational models inspired ... more >>>

TR00-032 | 31st May 2000

#### On the Computational Power of Winner-Take-All

In this paper the computational power of a new type of gate is studied:
winner-take-all gates. This work is motivated by the fact that the cost
of implementing a winner-take-all gate in analog VLSI is about the same
as that of implementing a threshold gate.

We show that ... more >>>

TR12-045 | 22nd April 2012
Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer

#### On the Concrete-Efficiency Threshold of Probabilistically-Checkable Proofs

Revisions: 3

Probabilistically-Checkable Proofs (PCPs) form the algorithmic core that enables succinct verification of long proofs/computations in many cryptographic constructions, such as succinct arguments and proof-carrying data.

Despite the wonderful asymptotic savings they bring, PCPs are also the infamous computational bottleneck preventing these cryptographic constructions from being used in practice. This reflects ... more >>>

TR13-148 | 26th October 2013
Irit Dinur, Igor Shinkar

#### On the Conditional Hardness of Coloring a 4-colorable Graph with Super-Constant Number of Colors

For $3 \leq q < Q$ we consider the $\text{ApproxColoring}(q,Q)$ problem of deciding for a given graph $G$ whether $\chi(G) \leq q$ or $\chi(G) \geq Q$. It was show in [DMR06] that the problem $\text{ApproxColoring}(q,Q)$ is NP-hard for $q=3,4$ and arbitrary large constant $Q$ under variants of the Unique Games ... more >>>

TR95-052 | 4th October 1995
Douglas R. Stinson

#### On the Connections Between Universal Hashing, Combinatorial Designs and Error-Correcting Codes

In this primarily expository
paper, we discuss the connections between two popular and useful
tools in theoretical computer science, namely,
universal hashing and pairwise
independent random variables; and classical combinatorial stuctures
such as error-correcting codes, balanced incomplete block designs,
difference matrices
... more >>>

TR09-143 | 22nd December 2009
Noam Livne

#### On the Construction of One-Way Functions from Average Case Hardness

In this paper we study the possibility of proving the existence of
one-way functions based on average case hardness. It is well-known
that if there exists a polynomial-time sampler that outputs
instance-solution pairs such that the distribution on the instances
is hard on average, then one-way functions exist. We study ... more >>>

TR97-005 | 17th February 1997
Moni Naor, Omer Reingold

#### On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited

Luby and Rackoff showed a method for constructing a pseudo-random
permutation from a pseudo-random function. The method is based on
composing four (or three for weakened security) so called Feistel
permutations each of which requires the evaluation of a pseudo-random
function. We reduce somewhat the complexity ... more >>>

TR12-137 | 1st November 2012

#### On the correlation of parity and small-depth circuits

Revisions: 1

We prove that the correlation of a depth-$d$
unbounded fanin circuit of size $S$ with parity
of $n$ variables is at most $2^{-\Omega(n/(\log S)^{d-1})}$.

more >>>

TR15-001 | 2nd January 2015
Nir Bitansky, Omer Paneth, Alon Rosen

#### On the Cryptographic Hardness of Finding a Nash Equilibrium

Revisions: 1

We prove that finding a Nash equilibrium of a game is hard, assuming the existence of indistinguishability obfuscation and injective one-way functions with sub-exponential hardness. We do so by showing how these cryptographic primitives give rise to a hard computational problem that lies in the complexity class PPAD, for which ... more >>>

TR98-052 | 5th August 1998
Boris Hemkemeier, Frank Vallentin

#### On the decomposition of lattices

Revisions: 1

A lattice in euclidean space which is an orthogonal sum of
nontrivial sublattices is called decomposable. We present an algorithm
to construct a lattice's decomposition into indecomposable sublattices.
Similar methods are used to prove a covering theorem for generating
systems of lattices and to speed up variations of the LLL ... more >>>

TR06-142 | 26th October 2006
Olaf Beyersdorff

#### On the Deduction Theorem and Complete Disjoint NP-Pairs

In this paper we ask the question whether the extended Frege proof
system EF satisfies a weak version of the deduction theorem. We
prove that if this is the case, then complete disjoint NP-pairs
exist. On the other hand, if EF is an optimal proof system, ... more >>>

TR10-039 | 10th March 2010
Gil Cohen, Amir Shpilka

#### On the degree of symmetric functions on the Boolean cube

In this paper we study the degree of non-constant symmetric functions $f:\{0,1\}^n \to \{0,1,\ldots,c\}$, where $c\in \mathbb{N}$, when represented as polynomials over the real numbers. We show that as long as $c < n$ it holds that deg$(f)=\Omega(n)$. As we can have deg$(f)=1$ when $c=n$, our
result shows a surprising ... more >>>

TR11-002 | 9th January 2011
Gil Cohen, Amir Shpilka, Avishay Tal

#### On the Degree of Univariate Polynomials Over the Integers

We study the following problem raised by von zur Gathen and Roche:

What is the minimal degree of a nonconstant polynomial $f:\{0,\ldots,n\}\to\{0,\ldots,m\}$?

Clearly, when $m=n$ the function $f(x)=x$ has degree $1$. We prove that when $m=n-1$ (i.e. the point $\{n\}$ is not in the range), it must be the case ... more >>>

TR12-157 | 12th November 2012
Andrej Bogdanov, Chin Ho Lee

#### On the depth complexity of homomorphic encryption schemes

Revisions: 2

We show that secure homomorphic evaluation of any non-trivial functionality of sufficiently many inputs with respect to any CPA secure encryption scheme cannot be implemented by constant depth, polynomial size circuits, i.e. in the class AC0. In contrast, we observe that certain previously studied encryption schemes (with quasipolynomial security) can ... more >>>

TR00-081 | 5th September 2000
Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe

#### On the difference between polynomial-time many-one and truth-table reducibilities on distributional problems

In this paper we separate many-one reducibility from truth-table
reducibility for distributional problems in DistNP under the
hypothesis that P neq NP. As a first example we consider the
3-Satisfiability problem (3SAT) with two different distributions
on 3CNF formulas. We show that 3SAT using a version of the
standard distribution ... more >>>

TR00-044 | 26th June 2000
Tzvika Hartman, Ran Raz

#### On the Distribution of the Number of Roots of Polynomials and Explicit Logspace Extractors

Weak designs were defined by Raz, Reingold and Vadhan (1999) and are
used in constructions of extractors. Roughly speaking, a weak design
is a collection of subsets satisfying some near-disjointness
properties. Constructions of weak designs with certain parameters are
given in [RRV99]. These constructions are explicit in the sense that
more >>>

TR17-101 | 8th June 2017
Oded Goldreich

#### On the doubly-efficient interactive proof systems of GKR

We present a somewhat simpler variant of the doubly-efficient interactive proof systems of Goldwasser, Kalai, and Rothblum (JACM, 2015).
Recall that these proof systems apply to log-space uniform sets in NC (or, more generally, to inputs that are acceptable by log-space uniform bounded-depth circuits, where the number of rounds in ... more >>>

TR97-051 | 11th November 1997
Pekka Orponen

#### On the Effect of Analog Noise in Discrete-Time Analog Computations

We introduce a model for analog computation with discrete
time in the presence of analog noise
that is flexible enough to cover the most important concrete
cases, such as noisy analog neural nets and networks of spiking neurons.
This model subsumes the classical ... more >>>

TR12-012 | 9th February 2012
Oded Goldreich

#### On the Effect of the Proximity Parameter on Property Testers

This note refers to the effect of the proximity parameter on the operation of (standard) property testers. Its bottom-line is that, except in pathological cases, the effect of the proximity parameter is restricted to determining the query complexity of the tester. The point is that, in non-pathological cases, the mapping ... more >>>

TR08-064 | 11th July 2008
Or Meir

#### On the Efficiency of Non-Uniform PCPP Verifiers

We define a non-uniform model of PCPs of Proximity, and observe that in this model the non-uniform verifiers can always be made very efficient. Specifically, we show that any non-uniform verifier can be modified to run in time that is roughly polynomial in its randomness and query complexity.

more >>>

TR97-001 | 8th January 1997
Marco Cesati, Luca Trevisan

#### On the Efficiency of Polynomial Time Approximation Schemes

A polynomial time approximation scheme (PTAS) for an optimization
problem $A$ is an algorithm that on input an instance of $A$ and
$\epsilon > 0$ finds a $(1+\epsilon)$-approximate solution in time
that is polynomial for each fixed $\epsilon$. Typical running times
are $n^{O(1/\epsilon)}$ or $2^{1/\epsilon^{O(1)}} ... more >>> TR15-129 | 7th August 2015 Alex Samorodnitsky #### On the entropy of a noisy function Revisions: 1 Let$f$be a nonnegative function on$\{0,1\}^n$. We upper bound the entropy of the image of$f$under the noise operator with noise parameter$\epsilon$by the average entropy of conditional expectations of$f$, given sets of roughly$(1-2\epsilon)^2 \cdot n$variables. As an application, we show that for ... more >>> TR02-016 | 30th January 2002 Alina Beygelzimer, Mitsunori Ogihara #### On the Enumerability of the Determinant and the Rank We investigate the complexity of enumerative approximation of two elementary problems in linear algebra, computing the rank and the determinant of a matrix. In particular, we show that if there exists an enumerator that, given a matrix, outputs a list of constantly many numbers, one of which is guaranteed to more >>> TR05-061 | 15th June 2005 Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma #### On the Error Parameter of Dispersers Optimal dispersers have better dependence on the error than optimal extractors. In this paper we give explicit disperser constructions that beat the best possible extractors in some parameters. Our constructions are not strong, but we show that having such explicit strong constructions implies a solution to the Ramsey graph construction ... more >>> TR98-001 | 17th December 1997 Detlef Sieling #### On the Existence of Polynomial Time Approximation Schemes for OBDD Minimization Revisions: 1 The size of Ordered Binary Decision Diagrams (OBDDs) is determined by the chosen variable ordering. A poor choice may cause an OBDD to be too large to fit into the available memory. The decision variant of the variable ordering problem is known to be NP-complete. We strengthen this result by ... more >>> TR98-021 | 7th April 1998 Shai Ben-David, Anna Gringauze. #### On the Existence of Propositional Proof Systems and Oracle-relativized Propositional Logic. Revisions: 1 We investigate sufficient conditions for the existence of optimal propositional proof systems (PPS). We concentrate on conditions of the form CoNF = NF. We introduce a purely combinatorial property of complexity classes - the notions of {\em slim} vs. {\em fat} classes. These notions partition the ... more >>> TR05-112 | 12th September 2005 Eran Ofek #### On the expansion of the giant component in percolated$(n,d,\lambda)$graphs Revisions: 1 Let$d \geq d_0$be a sufficiently large constant. A$(n,d,c
\sqrt{d})$graph$G$is a$d$regular graph over$n$vertices whose second largest eigenvalue (in absolute value) is at most$c
0$, we prove that with high probability a random subspace$C$of$\F_q^n$of dimension$(1-H_q(p)-\varepsilon)n$has the property that every Hamming ball of radius$pn$has at most$O(1/\varepsilon)$codewords. This ... more >>> TR11-100 | 20th July 2011 Parikshit Gopalan, Cheng Huang, Huseyin Simitci, Sergey Yekhanin #### On the Locality of Codeword Symbols Consider a linear$[n,k,d]_q$code$\mc{C}.$We say that that$i$-th coordinate of$\mc{C}$has locality$r,$if the value at this coordinate can be recovered from accessing some other$r$coordinates of$\mc{C}.$Data storage applications require codes with small redundancy, low locality for information coordinates, large distance, and ... more >>> TR16-003 | 2nd December 2015 Boris Brimkov, Illya Hicks #### On the logspace shortest path problem In this paper, we reduce the logspace shortest path problem to biconnected graphs; in particular, we present a logspace shortest path algorithm for general graphs which uses a logspace shortest path oracle for biconnected graphs. We also present a linear time logspace shortest path algorithm for graphs with bounded vertex ... more >>> TR09-091 | 23rd September 2009 Thanh Minh Hoang #### On the Matching Problem for Special Graph Classes Revisions: 1 In the present paper we show some new complexity bounds for the matching problem for special graph classes. We show that for graphs with a polynomially bounded number of nice cycles, the decision perfect matching problem is in$SPL$, it is hard for$FewL$, and the construction ... more >>> TR96-018 | 23rd February 1996 Oded Goldreich, Johan Hastad #### On the Message Complexity of Interactive Proof Systems Revisions: 2 We investigate the computational complexity of languages which have interactive proof systems of bounded message complexity. In particular, we show that (1) If$L$has an interactive proof in which the total communication is bounded by$c(n)$bits then$L$can be recognized a probabilitic machine in time ... more >>> TR10-178 | 17th November 2010 Amir Shpilka, Avishay Tal #### On the Minimal Fourier Degree of Symmetric Boolean Functions In this paper we give a new upper bound on the minimal degree of a nonzero Fourier coefficient in any non-linear symmetric Boolean function. Specifically, we prove that for every non-linear and symmetric$f:\{0,1\}^{k} \to \{0,1\}$there exists a set$\emptyset\neq S\subset[k]$such that$|S|=O(\Gamma(k)+\sqrt{k})$, and$\hat{f}(S) \neq 0$, where ... more >>> TR14-167 | 11th November 2014 Beate Bollig #### On the Minimization of (Complete) Ordered Binary Decision Diagrams Ordered binary decision diagrams (OBDDs) are a popular data structure for Boolean functions. Some applications work with a restricted variant called complete OBDDs which is strongly related to nonuniform deterministic finite automata. One of its complexity measures is the width which has been investigated in several areas in computer science ... more >>> TR08-056 | 22nd April 2008 Beate Bollig #### On the OBDD complexity of the most significant bit of integer multiplication Integer multiplication as one of the basic arithmetic functions has been in the focus of several complexity theoretical investigations. Ordered binary decision diagrams (OBDDs) are one of the most common dynamic data structures for boolean functions. Among the many areas of application are verification, model checking, computer-aided design, relational algebra, ... more >>> TR12-175 | 13th December 2012 James Cook, Omid Etesami, Rachel Miller, Luca Trevisan #### On the One-Way Function Candidate Proposed by Goldreich Revisions: 1 A function$f$mapping$n$-bit strings to$m$-bit strings can be constructed from a bipartite graph with$n$vertices on the left and$m$vertices on the right having right-degree$d$together with a predicate$P:\{0,1\}^d\rightarrow\{0,1\}$. The vertices on the left correspond to the bits of the input to the ... more >>> TR11-069 | 18th April 2011 Marius Zimand #### On the optimal compression of sets in PSPACE We show that if DTIME[2^{O(n)}] is not included in DSPACE}[2^{o(n)}], then, for every set B in PSPACE, all strings x in B of length n can be represented by a string compressed(x) of length at most log (|B^{=n}|) + O(log n), such that a polynomial-time algorithm, given compressed(x), can distinguish ... more >>> TR09-124 | 24th November 2009 Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth Vishnoi #### On the Optimality of a Class of LP-based Algorithms Revisions: 1 In this paper we will be concerned with a large class of packing and covering problems which includes Vertex Cover and Independent Set. Typically, for NP-hard problems among them, one can write an LP relaxation and then round the solution. For instance, for Vertex Cover, one can obtain a more >>> TR15-127 | 7th August 2015 Stasys Jukna, Georg Schnitger #### On the Optimality of Bellman--Ford--Moore Shortest Path Algorithm Revisions: 1 We prove a general lower bound on the size of branching programs over any semiring of zero characteristic, including the (min,+) semiring. Using it, we show that the classical dynamic programming algorithm of Bellman, Ford and Moore for the shortest s-t path problem is optimal, if only Min and Sum ... more >>> TR17-186 | 29th November 2017 Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi #### On the Parameterized Complexity of Approximating Dominating Set We study the parameterized complexity of approximating the$k$-Dominating Set (domset) problem where an integer$k$and a graph$G$on$n$vertices are given as input, and the goal is to find a dominating set of size at most$F(k) \cdot k$whenever the graph$G$has a dominating ... more >>> TR99-028 | 30th August 1999 Stefan Edelkamp, Ingo Wegener #### On the performance of WEAK-HEAPSORT Dutton presents a further HEAPSORT variant called WEAK-HEAPSORT which also contains a new data structure for priority queues. The sorting algorithm and the underlying data structure ara analyzed showing that WEAK-HEAPSORT is the best HEAPSORT variant and that it has a lot of nice more >>> TR12-101 | 10th August 2012 Oded Goldreich, Shafi Goldwasser, Dana Ron #### On the possibilities and limitations of pseudodeterministic algorithms We study the possibilities and limitations of pseudodeterministic algorithms, a notion put forward by Gat and Goldwasser (2011). These are probabilistic algorithms that solve search problems such that on each input, with high probability, they output the same solution, which may be thought of as a canonical solution. We consider ... more >>> TR00-054 | 5th May 2000 Andrea E. F. Clementi, Paolo Penna, Riccardo Silvestri #### On the power assignment problem in radio networks Given a finite set$S$of points (i.e. the stations of a radio network) on a$d$-dimensional Euclidean space and a positive integer$1\le h \le |S|-1$, the \minrangeh{d} problem consists of assigning transmission ranges to the stations so as to minimize the total power consumption, provided ... more >>> TR11-083 | 22nd May 2011 Eric Allender, Fengming Wang #### On the power of algebraic branching programs of width two We show that there are families of polynomials having small depth-two arithmetic circuits that cannot be expressed by algebraic branching programs of width two. This clarifies the complexity of the problem of computing the product of a sequence of two-by-two matrices, which arises in several settings. more >>> TR95-046 | 4th August 1995 Vince Grolmusz #### On the Power of Circuits with Gates of Low L_1 Norms We examine the power of Boolean functions with low L_1 norms in several settings. In large part of the recent literature, the degree of a polynomial which represents a Boolean function in some way was chosen to be the measure of the complexity of the Boolean function. However, some functions ... more >>> TR12-154 | 31st October 2012 Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, Arie Matsliah #### On the Power of Conditional Samples in Distribution Testing Revisions: 1 In this paper we define and examine the power of the conditional-sampling oracle in the context of distribution-property testing. The conditional-sampling oracle for a discrete distribution$\mu$takes as input a subset$S \subset [n]$of the domain, and outputs a random sample$i \in S$drawn according to$\mu$, ... more >>> TR94-026 | 12th December 1994 Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener #### On the Power of Different Types of Restricted Branching Programs Almost the same types of restricted branching programs (or binary decision diagrams BDDs) are considered in complexity theory and in applications like hardware verification. These models are read-once branching programs (free BDDs) and certain types of oblivious branching programs (ordered and indexed BDDs with k layers). The complexity of ... more >>> TR00-077 | 24th August 2000 Till Tantau #### On the Power of Extra Queries to Selective Languages Revisions: 1 A language is \emph{selective} if there exists a selection algorithm for it. Such an algorithm selects from any two words one, which is an element of the language whenever at least one of them is. Restricting the complexity of selection algorithms yields different \emph{selectivity classes} ... more >>> TR14-045 | 7th April 2014 Mrinal Kumar, Shubhangi Saraf #### On the power of homogeneous depth 4 arithmetic circuits Revisions: 2 We prove exponential lower bounds on the size of homogeneous depth 4 arithmetic circuits computing an explicit polynomial in$VP$. Our results hold for the {\it Iterated Matrix Multiplication} polynomial - in particular we show that any homogeneous depth 4 circuit computing the$(1,1)$entry in the product of$n$... more >>> TR09-024 | 26th February 2009 Raghav Kulkarni #### On the Power of Isolation in Planar Structures The purpose of this paper is to study the deterministic {\em isolation} for certain structures in directed and undirected planar graphs. The motivation behind this work is a recent development on this topic. For example, \cite{btv07} isolate a directed path in planar graphs and \cite{dkr08} isolate a perfect matching in ... more >>> TR97-029 | 20th August 1997 Pavol Duris, Juraj Hromkovic, Jose' D. P. Rolim, Georg Schnitger #### On the Power of Las Vegas for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations The study of the computational power of randomized computations is one of the central tasks of complexity theory. The main goal of this paper is the comparison of the power of Las Vegas computation and deterministic respectively nondeterministic computation. We investigate the power of Las Vegas computation for ... more >>> TR99-007 | 10th March 1999 Juraj Hromkovic, Georg Schnitger #### On the Power of Las Vegas II: Two-Way Finite Automata The investigation of the computational power of randomized computations is one of the central tasks of current complexity and algorithm theory. This paper continues in the comparison of the computational power of LasVegas computations with the computational power of deterministic and nondeterministic ones. While for one-way ... more >>> TR08-091 | 10th September 2008 Vitaly Feldman #### On The Power of Membership Queries in Agnostic Learning Revisions: 1 We study the properties of the agnostic learning framework of Haussler (1992)and Kearns, Schapire and Sellie (1992). In particular, we address the question: is there any situation in which membership queries are useful in agnostic learning? Our results show that the answer is negative for distribution-independent agnostic learning and positive ... more >>> TR13-137 | 29th September 2013 Mohammad Mahmoody, Hemanta Maji, Manoj Prabhakaran #### On the Power of Public-key Encryption in Secure Computation We qualitatively separate semi-honest secure computation of non-trivial secure-function evaluation (SFE) functionalities from existence of key-agreement protocols. Technically, we show the existence of an oracle (namely, PKE-oracle) relative to which key-agreement protocols exist; but it is useless for semi-honest secure realization of symmetric 2-party (deterministic finite) SFE functionalities, i.e. any ... more >>> TR02-074 | 26th December 2002 Andrew Chi-Chih Yao #### On the Power of Quantum Fingerprinting In the simultaneous message model, two parties holding$n$-bit integers$x,y$send messages to a third party, the {\it referee}, enabling him to compute a boolean function$f(x,y)$. Buhrman et al [BCWW01] proved the remarkable result that, when$f$is the equality function, the referee can solve this problem by ... more >>> TR12-129 | 9th October 2012 Iftach Haitner, Eran Omri, Hila Zarosim #### On the Power of Random Oracles Revisions: 3 In the random oracle model, the parties are given oracle access to a random member of a (typically huge) function family, and are assumed to have unbounded computational power (though they can only make a bounded number of oracle queries). This model provides powerful properties that allow proving the security ... more >>> TR95-054 | 24th November 1995 Farid Ablayev, Marek Karpinski #### On the Power of Randomized Branching Programs We define the notion of a randomized branching program in the natural way similar to the definition of a randomized circuit. We exhibit an explicit function$f_{n}$for which we prove that: 1)$f_{n}$can be computed by polynomial size randomized ... more >>> TR98-004 | 13th January 1998 Farid Ablayev, Marek Karpinski #### On the Power of Randomized Ordered Branching Programs We introduce a model of a {\em randomized branching program} in a natural way similar to the definition of a randomized circuit. We exhibit an explicit boolean function$f_{n}:\{0,1\}^{n}\to\{0,1\}$for which we prove that: 1)$f_{n}$can be computed by a polynomial size randomized ... more >>> TR05-135 | 19th November 2005 Iftach Haitner, Danny Harnik, Omer Reingold #### On the Power of the Randomized Iterate We consider two of the most fundamental theorems in Cryptography. The first, due to Haastad et. al. [HILL99], is that pseudorandom generators can be constructed from any one-way function. The second due to Yao [Yao82] states that the existence of weak one-way functions (i.e. functions on which every efficient algorithm ... more >>> TR10-009 | 13th January 2010 A. Pavan, Raghunath Tewari, Vinodchandran Variyam #### On the Power of Unambiguity in Logspace We report progress on the \NL\ vs \UL\ problem. \begin{itemize} \item[-] We show unconditionally that the complexity class$\ReachFewL\subseteq\UL$. This improves on the earlier known upper bound$\ReachFewL \subseteq \FewL$. \item[-] We investigate the complexity of min-uniqueness - a central notion in studying the \NL\ vs \UL\ problem. more >>> TR14-050 | 21st March 2014 Edward Hirsch, Dmitry Sokolov #### On the probabilistic closure of the loose unambiguous hierarchy Revisions: 1 Unambiguous hierarchies [NR93,LR94,NR98] are defined similarly to the polynomial hierarchy; however, all witnesses must be unique. These hierarchies have subtle differences in the mode of using oracles. We consider a "loose" unambiguous hierarchy$prUH_\bullet$with relaxed definition of oracle access to promise problems. Namely, we allow to make queries that ... more >>> TR10-054 | 30th March 2010 Jan Krajicek #### On the proof complexity of the Nisan-Wigderson generator based on a hard$NP \cap coNP$function Let$g$be a map defined as the Nisan-Wigderson generator but based on an$NP \cap coNP$-function$f$. Any string$b$outside the range of$g$determines a propositional tautology$\tau(g)_b$expressing this fact. Razborov \cite{Raz03} has conjectured that if$f$is hard on average for P/poly then these ... more >>> TR02-019 | 20th March 2002 Nader Bshouty, Lynn Burroughs #### On the proper learning of axis parallel concepts We study the proper learnability of axis parallel concept classes in the PAC learning model and in the exact learning model with membership and equivalence queries. These classes include union of boxes, DNF, decision trees and multivariate polynomials. For the {\it constant} dimensional axis parallel concepts$C$we ... more >>> TR11-038 | 10th March 2011 Jiapeng Zhang #### On the query complexity for Showing Dense Model A theorem of Green, Tao, and Ziegler can be stated as follows: if$R$is a pseudorandom distribution, and$D$is a dense distribution of$R,$then$D$can be modeled as a distribution$M$which is dense in uniform distribution such that$D$and$M$are indistinguishable. The reduction ... more >>> TR05-082 | 3rd June 2005 Jorge Castro #### On the Query Complexity of Quantum Learners This paper introduces a framework for quantum exact learning via queries, the so-called quantum protocol. It is shown that usual protocols in the classical learning setting have quantum counterparts. A combinatorial notion, the general halving dimension, is also introduced. Given a quantum protocol and a target concept class, the general ... more >>> TR14-031 | 16th February 2014 Joao Marques-Silva, Mikolas Janota #### On the Query Complexity of Selecting Few Minimal Sets Propositional Satisfiability (SAT) solvers are routinely used for solving many function problems. A natural question that has seldom been addressed is: what is the best worst-case number of calls to a SAT solver for solving some target function problem? This paper develops tighter upper bounds on the query complexity of more >>> TR07-015 | 1st March 2007 Oded Goldreich, Or Sheffet #### On the randomness complexity of property testing We initiate a general study of the randomness complexity of property testing, aimed at reducing the randomness complexity of testers without (significantly) increasing their query complexity. One concrete motovation for this study is provided by the observation that the product of the randomness and query complexity of a tester determine ... more >>> TR07-061 | 12th July 2007 Or Meir #### On the Rectangle Method in proofs of Robustness of Tensor Products Revisions: 4 Given linear two codes R,C, their tensor product$R \otimes C$consists of all matrices whose rows are codewords of R and whose columns are codewords of C. The product$R \otimes C$is said to be robust if for every matrix M that is far from$R \otimes C$more >>> TR10-036 | 8th March 2010 Amir Shpilka, Ilya Volkovich #### On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors We say that a polynomial$f(x_1,\ldots,x_n)$is {\em indecomposable} if it cannot be written as a product of two polynomials that are defined over disjoint sets of variables. The {\em polynomial decomposition} problem is defined to be the task of finding the indecomposable factors of a given polynomial. Note that ... more >>> TR15-186 | 24th November 2015 Benny Applebaum, Pavel Raykov #### On the Relationship between Statistical Zero-Knowledge and Statistical Randomized Encodings \emph{Statistical Zero-knowledge proofs} (Goldwasser, Micali and Rackoff, SICOMP 1989) allow a computationally-unbounded server to convince a computationally-limited client that an input$x$is in a language$\Pi$without revealing any additional information about$x$that the client cannot compute by herself. \emph{Randomized encoding} (RE) of functions (Ishai and Kushilevitz, FOCS ... more >>> TR07-126 | 5th November 2007 Nathan Segerlind #### On the relative efficiency of resolution-like proofs and ordered binary decision diagram proofs We show that tree-like OBDD proofs of unsatisfiability require an exponential increase ($s \mapsto 2^{s^{\Omega(1)}}$) in proof size to simulate unrestricted resolution, and that unrestricted OBDD proofs of unsatisfiability require an almost-exponential increase ($s \mapsto 2^{ 2^{\left( \log s \right)^{\Omega(1)}}}$) in proof size to simulate$\Res{O(\log n)}$. The OBDD proof ... more >>> TR10-045 | 15th March 2010 Jakob Nordström #### On the Relative Strength of Pebbling and Resolution Revisions: 1 The last decade has seen a revival of interest in pebble games in the context of proof complexity. Pebbling has proven to be a useful tool for studying resolution-based proof systems when comparing the strength of different subsystems, showing bounds on proof space, and establishing size-space trade-offs. The typical approach ... more >>> TR04-109 | 15th November 2004 Neeraj Kayal, Nitin Saxena #### On the Ring Isomorphism & Automorphism Problems We study the complexity of the isomorphism and automorphism problems for finite rings with unity. We show that both integer factorization and graph isomorphism reduce to the problem of counting automorphisms of rings. The problem is shown to be in the complexity class$\AM \cap co\AM$and hence ... more >>> TR05-104 | 16th September 2005 Don Coppersmith, Atri Rudra #### On the Robust Testability of Product of Codes Ben-Sasson and Sudan in~\cite{BS04} asked if the following test is robust for the tensor product of a code with another code-- pick a row (or column) at random and check if the received word restricted to the picked row (or column) belongs to the corresponding code. Valiant showed that ... more >>> TR14-062 | 22nd March 2014 Alexander Kozachinsky #### On the role of private coins in unbounded-round Information Complexity We prove a version of "Reversed Newman Theorem" in context of information complexity: every private-coin communication protocol with information complexity$I$and communication complexity$C$can be replaced by public-coin protocol with the same behavior so that it's information complexity does not exceed$O\left(\sqrt{IC}\right)$. This result holds for unbounded-round communication ... more >>> TR15-137 | 22nd August 2015 Mohammad Bavarian, Dmitry Gavinsky, Tsuyoshi Ito #### On the Role of Shared Randomness in Simultaneous Communication Two parties wish to carry out certain distributed computational tasks, and they are given access to a source of correlated random bits. It allows the parties to act in a correlated manner, which can be quite useful. But what happens if the shared randomness is not perfect? In this work, ... more >>> TR99-005 | 21st December 1998 Michael Schmitt #### On the Sample Complexity for Nonoverlapping Neural Networks A neural network is said to be nonoverlapping if there is at most one edge outgoing from each node. We investigate the number of examples that a learning algorithm needs when using nonoverlapping neural networks as hypotheses. We derive bounds for this sample complexity in terms of the Vapnik-Chervonenkis dimension. ... more >>> TR04-033 | 23rd January 2004 Michael Schmitt #### On the sample complexity of learning for networks of spiking neurons with nonlinear synaptic interactions We study networks of spiking neurons that use the timing of pulses to encode information. Nonlinear interactions model the spatial groupings of synapses on the dendrites and describe the computations performed at local branches. We analyze the question of how many examples these networks must ... more >>> TR06-104 | 25th August 2006 Wenceslas Fernandez de la Vega, Marek Karpinski #### On the Sample Complexity of MAX-CUT We give a simple proof for the sample complexity bound$O~(1/\epsilon^4)$of absolute approximation of MAX-CUT. The proof depends on a new analysis method for linear programs (LPs) underlying MAX-CUT which could be also of independent interest. more >>> TR00-045 | 23rd June 2000 Maria Isabel Gonzalez Vasco, Igor E. Shparlinski #### On the Security of Diffie--Hellman Bits Boneh and Venkatesan have recently proposed a polynomial time algorithm for recovering a hidden'' element$\alpha$of a finite field$\F_p$of$p$elements from rather short strings of the most significant bits of the remainder mo\-du\-lo$p$of$\alpha t$for several values of$t$selected uniformly at ... more >>> TR01-007 | 7th December 2000 Vered Rosen #### On the Security of Modular Exponentiation Comments: 1 Assuming the inractability of factoring, we show that the output of the exponentiation modulo a composite function$f_{N,g}(x)=g^x\bmod N$(where$N=P\cdot Q$) is pseudorandom, even when its input is restricted to be half the size. This result is equivalent to the simultaneous hardness of the ... more >>> TR02-049 | 4th August 2002 Oded Goldreich, Vered Rosen #### On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators Assuming the inractability of factoring, we show that the output of the exponentiation modulo a composite function$f_{N,g}(x)=g^x\bmod N$(where$N=P\cdot Q$) is pseudorandom, even when its input is restricted to be half the size. This result is equivalent to the simultaneous hardness of the upper half of the bits ... more >>> TR97-027 | 29th April 1997 Johannes Merkle, Ralph Werchner #### On the Security of Server aided RSA protocols Revisions: 1 In this paper we investigate the security of the server aided RSA protocols RSA-S1 and RSA-S1M proposed by Matsumoto, Kato and Imai resp. Matsumoto, Imai, Laih and Yen. We prove lower bounds for the complexity of attacks on these protocols and show that the bounds are sharp by describing attacks ... more >>> TR16-062 | 18th April 2016 Avishay Tal #### On The Sensitivity Conjecture The sensitivity of a Boolean function$f:\{0,1\}^n \to \{0,1\}$is the maximal number of neighbors a point in the Boolean hypercube has with different$f$-value. Roughly speaking, the block sensitivity allows to flip a set of bits (called a block) rather than just one bit, in order to change the ... more >>> TR16-132 | 23rd August 2016 Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, Ameya Velingker #### On the Sensitivity Conjecture for Read-k Formulas Various combinatorial/algebraic parameters are used to quantify the complexity of a Boolean function. Among them, sensitivity is one of the simplest and block sensitivity is one of the most useful. Nisan (1989) and Nisan and Szegedy (1991) showed that block sensitivity and several other parameters, such as certificate complexity, decision ... more >>> TR05-020 | 22nd November 2004 Sourav Chakraborty #### On the Sensitivity of Cyclically-Invariant Boolean Functions In this paper we construct a cyclically invariant Boolean function whose sensitivity is$\Theta(n^{1/3})$. This result answers two previously published questions. Tur\'an (1984) asked if any Boolean function, invariant under some transitive group of permutations, has sensitivity$\Omega(\sqrt{n})$. Kenyon and Kutin (2004) asked whether for a nice'' function the product ... more >>> TR13-043 | 25th March 2013 Oded Goldreich, Avi Wigderson #### On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions Revisions: 1 We propose that multi-linear functions of relatively low degree over GF(2) may be good candidates for obtaining exponential lower bounds on the size of constant-depth Boolean circuits (computing explicit functions). Specifically, we propose to move gradually from linear functions to multilinear ones, and conjecture that, for any$t\geq2$, more >>> TR15-181 | 13th November 2015 Neeraj Kayal, Chandan Saha, Sébastien Tavenas #### On the size of homogeneous and of depth four formulas with low individual degree Let$r \geq 1$be an integer. Let us call a polynomial$f(x_1, x_2,\ldots, x_N) \in \mathbb{F}[\mathbf{x}]$as a multi-$r$-ic polynomial if the degree of$f$with respect to any variable is at most$r$(this generalizes the notion of multilinear polynomials). We investigate arithmetic circuits in which the output ... more >>> TR14-170 | 10th December 2014 Yael Tauman Kalai, Ran Raz #### On the Space Complexity of Linear Programming with Preprocessing Revisions: 1 Linear Programs are abundant in practice, and tremendous effort has been put into designing efficient algorithms for such problems, resulting with very efficient (polynomial time) algorithms. A fundamental question is: what is the space complexity of Linear Programming? It is widely believed that (even approximating) Linear Programming requires a large ... more >>> TR12-150 | 1st November 2012 Michael Elberfeld, Christoph Stockhusen, Till Tantau #### On the Space Complexity of Parameterized Problems Revisions: 1 Parameterized complexity theory measures the complexity of computational problems predominantly in terms of their parameterized time complexity. The purpose of the present paper is to demonstrate that the study of parameterized space complexity can give new insights into the complexity of well-studied parameterized problems like the feedback vertex set problem. ... more >>> TR01-008 | 6th November 2000 Eldar Fischer #### On the strength of comparisons in property testing An$\epsilon$-test for a property$P$of functions from${\cal D}=\{1,\ldots,d\}$to the positive integers is a randomized algorithm, which makes queries on the value of an input function at specified locations, and distinguishes with high probability between the case of the function satisfying$P$, and the case that it ... more >>> TR13-049 | 1st April 2013 Amir Shpilka, Ben Lee Volk, Avishay Tal #### On the Structure of Boolean Functions with Small Spectral Norm Revisions: 1 In this paper we prove results regarding Boolean functions with small spectral norm (the spectral norm of$f$is$\|\hat{f}\|_1=\sum_{\alpha}|\hat{f}(\alpha)|$). Specifically, we prove the following results for functions$f:\{0,1\}^n\to \{0,1\}$with$\|\hat{f}\|_1=A$. 1. There is a subspace$V$of co-dimension at most$A^2$such that$f|_V$is constant. 2. ... more >>> TR09-080 | 19th September 2009 Elad Haramaty, Amir Shpilka #### On the Structure of Cubic and Quartic Polynomials Revisions: 1 In this paper we study the structure of polynomials of degree three and four that have high bias or high Gowers norm, over arbitrary prime fields. In particular we obtain the following results. 1. We give a canonical representation for degree three or four polynomials that have a significant bias ... more >>> TR15-101 | 15th June 2015 Patrick Scharpfenecker #### On the structure of Solution-Graphs for Boolean Formulas Revisions: 2 In this work we extend the study of solution graphs and prove that for boolean formulas in a class called CPSS, all connected components are partial cubes of small dimension, a statement which was proved only for some cases in [Schwerdtfeger 2013]. In contrast, we show that general Schaefer formulas ... more >>> TR06-146 | 30th September 2006 Christoph Buchheim, Peter J Cameron, Taoyang Wu #### On the Subgroup Distance Problem We investigate the computational complexity of finding an element of a permutation group~$H\subseteq S_n$with a minimal distance to a given~$\pi\in S_n$, for different metrics on~$S_n$. We assume that~$H$is given by a set of generators, such that the problem cannot be solved in polynomial time ... more >>> TR13-039 | 18th March 2013 Arturs Backurs, Mohammad Bavarian #### On the sum of$L1$influences Revisions: 2 For a multilinear polynomial$p(x_1,...x_n)$, over the reals, the$L1$-influence is defined to be$\sum_{i=1}^n E_x\left[\frac{|p(x)-p(x^i)|}{2} \right]$, where$x^i$is$x$with$i$-th bit swapped. If$p$maps$\{-1,1\}^n$to$[-1,1]$, we prove that the$L1$-influence of$p$is upper bounded by a function of its degree (and independent of ... more >>> TR10-189 | 8th December 2010 Neeraj Kayal, Chandan Saha #### On the Sum of Square Roots of Polynomials and related problems The sum of square roots problem over integers is the task of deciding the sign of a nonzero sum,$S = \Sigma_{i=1}^{n}{\delta_i}$. \sqrt{$a_i$}, where$\delta_i \in${ +1, -1} and$a_i$'s are positive integers that are upper bounded by$N$(say). A fundamental open question in numerical analysis and ... more >>> TR06-018 | 8th February 2006 Jin-Yi Cai, Vinay Choudhary #### On the Theory of Matchgate Computations Valiant has proposed a new theory of algorithmic computation based on perfect matchings and the Pfaffian. We study the properties of {\it matchgates}---the basic building blocks in this new theory. We give a set of algebraic identities which completely characterize these objects in terms of the ... more >>> TR99-021 | 8th April 1999 Igor E. Shparlinski #### ON THE UNIFORMITY OF DISTRIBUTION OF A CERTAIN PSEUDO-RANDOM FUNCTION We show that a pseudo-random number generator, introduced recently by M. Naor and O. Reingold, possess one more attractive and useful property. Namely, it is proved that for almost all values of parameters it produces a uniformly distributed sequence. The proof is based on some recent bounds of exponential more >>> TR08-024 | 26th February 2008 Paul Beame, Trinh Huynh #### On the Value of Multiple Read/Write Streams for Approximating Frequency Moments Revisions: 2 Recently, an extension of the standard data stream model has been introduced in which an algorithm can create and manipulate multiple read/write streams in addition to its input data stream. Like the data stream model, the most important parameter for this model is the amount of internal memory used by ... more >>> TR16-010 | 28th January 2016 Alexander Razborov #### On the Width of Semi-Algebraic Proofs and Algorithms In this paper we initiate the study of width in semi-algebraic proof systems and various cut-based procedures in integer programming. We focus on two important systems: Gomory-Chv\'atal cutting planes and Lov\'asz-Schrijver lift-and-project procedures. We develop general methods for proving width lower bounds and apply them to random$k$-CNFs and several ... more >>> TR13-019 | 31st January 2013 Stephen A. Fenner, Rohit Gurjar, Arpita Korwar, Thomas Thierauf #### On Two-Level Poset Games We consider the complexity of determining the winner of a finite, two-level poset game. This is a natural question, as it has been shown recently that determining the winner of a finite, three-level poset game is PSPACE-complete. We give a simple formula allowing one to compute the status ... more >>> TR01-039 | 18th May 2001 Stasys Jukna, Stanislav Zak #### On Uncertainty versus Size in Branching Programs Revisions: 1 We propose an information-theoretic approach to proving lower bounds on the size of branching programs. The argument is based on Kraft-McMillan type inequalities for the average amount of uncertainty about (or entropy of) a given input during the various stages of computation. The uncertainty is measured by the average more >>> TR14-036 | 8th March 2014 Mikolas Janota, Leroy Chew, Olaf Beyersdorff #### On Unification of QBF Resolution-Based Calculi Revisions: 1 Several calculi for quantified Boolean formulas (QBFs) exist, but relations between them are not yet fully understood. This paper defines a novel calculus, which is resolution-based and enables unification of the principal existing resolution-based QBF calculi, namely Q-resolution, long-distance Q-resolution and the expansion-based calculus ... more >>> TR17-087 | 9th May 2017 Pushkar Joglekar, Raghavendra Rao B V, Sidhartha Sivakumar #### On Weak-Space Complexity over Complex Numbers Defining a feasible notion of space over the Blum-Shub-Smale (BSS) model of algebraic computation is a long standing open problem. In an attempt to define a right notion of space complexity for the BSS model, Naurois [CiE, 2007] introduced the notion of weak-space. We investigate the weak-space bounded computations and ... more >>> TR05-015 | 27th January 2005 Andrej Bogdanov, Luca Trevisan #### On Worst-Case to Average-Case Reductions for NP Problems We show that if an NP-complete problem has a non-adaptive self-corrector with respect to a samplable distribution then coNP is contained in NP/poly and the polynomial hierarchy collapses to the third level. Feigenbaum and Fortnow (SICOMP 22:994-1005, 1993) show the same conclusion under the stronger assumption that an more >>> TR95-050 | 15th October 1995 Oded Goldreich, Noam Nisan, Avi Wigderson #### On Yao's XOR-Lemma Revisions: 2 , Comments: 1 TR03-052 | 13th May 2003 Stanislav Busygin, Dmitrii V. Pasechnik #### On ~chi(G)-alpha(G)>0 gap recognition and alpha(G)-upper bounds We show that for a graph G it is NP-hard to decide whether its independence number alpha(G) equals its clique partition number ~chi(G) even when some minimum clique partition of G is given. This implies that any alpha(G)-upper bound provably better than ~chi(G) is NP-hard to compute. To establish this ... more >>> TR00-063 | 13th July 2000 Peter Auer #### On-line Learning of Rectangles in Noisy Environments We investigate the implications of noise in the equivalence query model. Besides some results for general target and hypotheses classes, we prove bounds on the learning complexity of d-dimensional discretized rectangles in the case where only rectangles are allowed as hypotheses. Our noise model assumes ... more >>> TR00-071 | 14th July 2000 Peter Auer, Nicolo Cesa-Bianchi #### On-line Learning with Malicious Noise and the Closure Algorithm We investigate a variant of the on-line learning model for classes of {0,1}-valued functions (concepts) in which the labels of a certain amount of the input instances are corrupted by adversarial noise. We propose an extension of a general learning strategy, known as "Closure Algorithm", to this noise ... more >>> TR00-001 | 14th January 2000 Piotr Berman, Moses Charikar, Marek Karpinski #### On-Line Load Balancing for Related Machines We consider the problem of scheduling permanent jobs on related machines in an on-line fashion. We design a new algorithm that achieves the competitive ratio of$3+\sqrt{8}\approx 5.828$for the deterministic version, and$3.31/\ln 2.155 \approx 4.311$for its randomized variant, improving the previous competitive ratios ... more >>> TR99-014 | 30th May 1999 Alexander Razborov, Nikolay Vereshchagin #### One Property of Cross-Intersecting Families Assume that A, B are finite families of n-element sets. We prove that there is an element that simultaneously belongs to at least |A|/2n sets in A and to at least |B|/2n sets in B. We use this result to prove that for any inconsistent DNF's F,G with OR ... more >>> TR14-091 | 22nd July 2014 Ryan O'Donnell, A. C. Cem Say #### One time-travelling bit is as good as logarithmically many Revisions: 1 We consider computation in the presence of closed timelike curves (CTCs), as proposed by Deutsch. We focus on the case in which the CTCs carry classical bits (as opposed to qubits). Previously, Aaronson and Watrous showed that computation with polynomially many CTC bits is equivalent in power to PSPACE. On ... more >>> TR12-091 | 16th July 2012 Abuzer Yakaryilmaz #### One-counter verifiers for decidable languages Condon and Lipton (FOCS 1989) showed that the class of languages having a space-bounded interactive proof system (IPS) is a proper subset of decidable languages, where the verifier is a probabilistic Turing machine. In this paper, we show that if we use architecturally restricted verifiers instead of restricting the working ... more >>> TR06-130 | 27th September 2006 Tanmoy Chakraborty, Samir Datta #### One-input-face MPCVP is Hard for L, but in LogDCFL A monotone planar circuit (MPC) is a Boolean circuit that can be embedded in a plane, and that has only AND and OR gates. Yang showed that the one-input-face monotone planar circuit value problem (MPCVP) is in NC^2, and Limaye et. al. improved the bound to ... more >>> TR13-013 | 18th January 2013 Daniel Apon, Jonathan Katz, Alex Malozemoff #### One-Round Multi-Party Communication Complexity of Distinguishing Sums Revisions: 1 We consider an instance of the following problem: Parties$P_1,..., P_k$each receive an input$x_i$, and a coordinator (distinct from each of these parties) wishes to compute$f(x_1,..., x_k)$for some predicate$f$. We are interested in one-round protocols where each party sends a single message to the coordinator; ... more >>> TR16-173 | 5th November 2016 Egor Klenin, Alexander Kozachinsky #### One-sided error communication complexity of Gap Hamming Distance Assume that Alice has a binary string$x$and Bob a binary string$y$, both of length$n$. Their goal is to output 0, if$x$and$y$are at least$L$-close in Hamming distance, and output 1, if$x$and$y$are at least$U$-far in Hamming distance, where ... more >>> TR17-152 | 9th October 2017 Swagato Sanyal #### One-way Communication and Non-adaptive Decision Tree Comments: 1 Let$f$be a Boolean function on$n$-bits, and$\mathsf{IP}$the inner-product function on$2b$bits. Let$f^{\mathsf{IP}}:=f \circ \mathsf{IP}^n$be the two party function obtained by composing$f$with$\mathsf{IP}$. In this work we bound the one-way communication complexity of$f^{\IP}$in terms of the non-adaptive query complexity of ... more >>> TR03-083 | 21st November 2003 Jan Arpe, Andreas Jakoby, Maciej Liskiewicz #### One-Way Communication Complexity of Symmetric Boolean Functions We study deterministic one-way communication complexity of functions with Hankel communication matrices. Some structural properties of such matrices are established and applied to the one-way two-party communication complexity of symmetric Boolean functions. It is shown that the number of required communication bits does not depend on ... more >>> TR09-019 | 10th March 2009 Agrawal Manindra, Osamu Watanabe #### One-Way Functions and the Isomorphism Conjecture We study the Isomorphism Conjecture proposed by Berman and Hartmanis. It states that all sets complete for NP under polynomial-time many-one reductions are P-isomorphic to each other. From previous research it has been widely believed that all NP-complete sets are reducible each other by one-to-one and length-increasing polynomial-time reductions, but ... more >>> TR07-079 | 11th August 2007 Emanuele Viola, Avi Wigderson #### One-way multi-party communication lower bound for pointer jumping with applications In this paper we study the one-way multi-party communication model, in which every party speaks exactly once in its turn. For every fixed$k$, we prove a tight lower bound of$\Omega{n^{1/(k-1)}}$on the probabilistic communication complexity of pointer jumping in a$k$-layered tree, where the pointers of the$i$-th ... more >>> TR09-097 | 2nd September 2009 Rakesh Mohanty, N. S. Narayanaswamy #### Online Algorithms for Self-Organizing Sequential Search - A Survey The main objective of this survey is to present the important theoretical and experimental results contributed till date in the area of online algorithms for the self organizing sequential search problem, also popularly known as the List Update Problem(LUP) in a chronological way. The survey includes competitiveness results of deterministic ... more >>> TR10-016 | 22nd December 2009 Alexander Fanghänel, Sascha Geulen, Martin Hoefer, Berthold Vöcking #### Online Capacity Maximization in Wireless Networks In this paper we study a dynamic version of capacity maximization in the physical model of wireless communication. In our model, requests for connections between pairs of points in Euclidean space of constant dimension$d$arrive iteratively over time. When a new request arrives, an online algorithm needs to decide ... more >>> TR05-161 | 13th December 2005 John Hitchcock #### Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets We establish a relationship between the online mistake-bound model of learning and resource-bounded dimension. This connection is combined with the Winnow algorithm to obtain new results about the density of hard sets under adaptive reductions. This improves previous work of Fu (1995) and Lutz and Zhao (2000), and solves one ... more >>> TR96-061 | 27th November 1996 Ryuhei Uehara, Kensei Tsuchida, Ingo Wegener #### Optimal attribute-efficient learning of disjunction, parity, and threshold functions Decision trees are a very general computation model. Here the problem is to identify a Boolean function$f$out of a given set of Boolean functions$F$by asking for the value of$f$at adaptively chosen inputs. For classes$F$consisting of functions which may be obtained from one more >>> TR12-030 | 4th April 2012 Deeparnab Chakrabarty, C. Seshadhri #### Optimal bounds for monotonicity and Lipschitz testing over the hypercube Revisions: 2 The problem of monotonicity testing of the boolean hypercube is a classic well-studied, yet unsolved question in property testing. We are given query access to$f:\{0,1\}^n \mapsto R$(for some ordered range$R$). The boolean hypercube${\cal B}^n$has a natural partial order, denoted by$\prec$(defined by the product ... more >>> TR10-025 | 24th February 2010 Alexander A. Sherstov #### Optimal bounds for sign-representing the intersection of two halfspaces by polynomials The threshold degree of a function$f\colon\{0,1\}^n\to\{-1,+1\}$is the least degree of a real polynomial$p$with$f(x)\equiv\mathrm{sgn}\; p(x).$We prove that the intersection of two halfspaces on$\{0,1\}^n$has threshold degree$\Omega(n),$which matches the trivial upper bound and completely answers a question due to Klivans (2002). The best ... more >>> TR95-041 | 28th June 1995 Alexander E. Andreev, Andrea E. F. Clementi, Jose Rolim #### Optimal Bounds for the Approximation of Boolean Functions and Some Applications We prove an optimal bound on the Shannon function$L(n,m,\epsilon)$which describes the trade-off between the circuit-size complexity and the degree of approximation; that is $$L(n,m,\epsilon)\ =\ \Theta\left(\frac{m\epsilon^2}{\log(2 + m\epsilon^2)}\right)+O(n).$$ Our bound applies to any partial boolean function and any ... more >>> TR12-104 | 8th August 2012 Matthew Franklin, Ran Gelles, Rafail Ostrovsky, Leonard Schulman #### Optimal Coding for Streaming Authentication and Interactive Communication Revisions: 1 Error correction and message authentication are well studied in the literature, and various efficient solutions have been suggested and analyzed. This is however not the case for data streams in which the message is very long, possibly infinite, and not known in advance to the sender. Trivial solutions for error-correcting ... more >>> TR10-106 | 17th June 2010 Yuichi Yoshida #### Optimal Constant-Time Approximation Algorithms and (Unconditional) Inapproximability Results for Every Bounded-Degree CSP Revisions: 1 Raghavendra (STOC 2008) gave an elegant and surprising result: if Khot's Unique Games Conjecture (STOC 2002) is true, then for every constraint satisfaction problem (CSP), the best approximation ratio is attained by a certain simple semidefinite programming and a rounding scheme for it. In this paper, we show that a ... more >>> TR12-176 | 14th December 2012 Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu #### Optimal Cuts and Partitions in Tree Metrics in Polynomial Time We present a polynomial time dynamic programming algorithm for optimal partitions in the shortest path metric induced by a tree. This resolves, among other things, the exact complexity status of the optimal partition problems in one dimensional geometric metric settings. Our method of solution could be also of independent interest ... more >>> TR06-032 | 25th February 2006 Vitaly Feldman #### Optimal Hardness Results for Maximizing Agreements with Monomials We consider the problem of finding a monomial (or a term) that maximizes the agreement rate with a given set of examples over the Boolean hypercube. The problem originates in learning and is referred to as {\em agnostic learning} of monomials. Finding a monomial with the highest agreement rate was ... more >>> TR11-091 | 20th May 2011 Edward Hirsch, Dmitry Itsykson, Valeria Nikolaenko, Alexander Smal #### Optimal heuristic algorithms for the image of an injective function The existence of optimal algorithms is not known for any decision problem in NP$\setminus$P. We consider the problem of testing the membership in the image of an injective function. We construct optimal heuristic algorithms for this problem in both randomized and deterministic settings (a heuristic algorithm can err on a ... more >>> TR12-158 | 14th November 2012 Aditya Bhaskara, Devendra Desai, Srikanth Srinivasan #### Optimal Hitting Sets for Combinatorial Shapes We consider the problem of constructing explicit Hitting sets for Combinatorial Shapes, a class of statistical tests first studied by Gopalan, Meka, Reingold, and Zuckerman (STOC 2011). These generalize many well-studied classes of tests, including symmetric functions and combinatorial rectangles. Generalizing results of Linial, Luby, Saks, and Zuckerman (Combinatorica 1997) ... more >>> TR05-101 | 20th September 2005 Guy Kindler, Ryan O'Donnell, Subhash Khot, Elchanan Mossel #### Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs? In this paper we show a reduction from the Unique Games problem to the problem of approximating MAX-CUT to within a factor of$\GW + \eps$, for all$\eps > 0$; here$\GW \approx .878567$denotes the approximation ratio achieved by the Goemans-Williamson algorithm~\cite{GW95}. This implies that if the Unique ... more >>> TR17-079 | 1st May 2017 Alexander A. Sherstov, Pei Wu #### Optimal Interactive Coding for Insertions, Deletions, and Substitutions Interactive coding, pioneered by Schulman (FOCS 1992, STOC 1993), is concerned with making communication protocols resilient to adversarial noise. The canonical model allows the adversary to alter a small constant fraction of symbols, chosen at the adversary's discretion, as they pass through the communication channel. Braverman, Gelles, Mao, and Ostrovsky ... more >>> TR09-130 | 1st December 2009 Ryan O'Donnell, YI WU, Yuan Zhou #### Optimal lower bounds for locality sensitive hashing (except when$q$is tiny) We study lower bounds for Locality Sensitive Hashing (LSH) in the strongest setting: point sets in$\{0,1\}^d$under the Hamming distance. Recall that$\mathcal{H}$is said to be an$(r, cr, p, q)$-sensitive hash family if all pairs$x,y \in \{0,1\}^d$with dist$(x,y) \leq r$have probability at least$p$... more >>> TR96-022 | 15th March 1996 Martin Sauerhoff, Ingo Wegener, Ralph Werchner #### Optimal Ordered Binary Decision Diagrams for Tree-like Circuits Many Boolean functions have short representations by OBDDs (ordered binary decision diagrams) if appropriate variable orderings are used. For tree-like circuits, which may contain EXOR-gates, it is proved that some depth first traversal leads to an optimal variable ordering. Moreover, an optimal variable ordering and the resulting OBDD can ... more >>> TR08-107 | 12th November 2008 Zenon Sadowski #### Optimal Proof Systems and Complete Languages We investigate the connection between optimal propositional proof systems and complete languages for promise classes. We prove that an optimal propositional proof system exists if and only if there exists a propositional proof system in which every promise class with the test set in co-NP ... more >>> TR97-026 | 18th June 1997 Jochen Me\3ner, Jacobo Toran #### Optimal proof systems for Propositional Logic and complete sets A polynomial time computable function$h:\Sigma^*\to\Sigma^*$whose range is the set of tautologies in Propositional Logic (TAUT), is called a proof system. Cook and Reckhow defined this concept and in order to compare the relative strenth of different proof systems, they considered the notion ... more >>> TR13-046 | 27th March 2013 Venkatesan Guruswami, Chaoping Xing #### Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets We construct a new list-decodable family of asymptotically good algebraic-geometric (AG) codes over fixed alphabets. The function fields underlying these codes are constructed using class field theory, specifically Drinfeld modules of rank$1$, and designed to have an automorphism of large order that is used to fold" the AG code. ... more >>> TR16-166 | 1st November 2016 Mark Braverman, Ran Gelles, Michael A. Yitayew #### Optimal Resilience for Short-Circuit Noise in Formulas Revisions: 1 We show an efficient method for converting a logic circuit of gates with fan-out 1 into an equivalent circuit that works even if some fraction of its gates are short-circuited, i.e., their output is short-circuited to one of their inputs. Our conversion can be applied to any circuit with fan-in ... more >>> TR96-044 | 6th August 1996 Yosi Ben-Asher, Ilan Newman #### Optimal Search in Trees Revisions: 1 It is well known that the optimal solution for searching in a finite total order set is the binary search. In the binary search we divide the set into two halves'', by querying the middle element, and continue the search on the suitable half. What is the equivalent of binary ... more >>> TR09-061 | 2nd July 2009 Konstantinos Georgiou, Avner Magen, Madhur Tulsiani #### Optimal Sherali-Adams Gaps from Pairwise Independence This work considers the problem of approximating fixed predicate constraint satisfaction problems (MAX k-CSP(P)). We show that if the set of assignments accepted by$P$contains the support of a balanced pairwise independent distribution over the domain of the inputs, then such a problem on$n$variables cannot be approximated ... more >>> TR11-059 | 15th April 2011 Elad Haramaty, Amir Shpilka, Madhu Sudan #### Optimal testing of multivariate polynomials over small prime fields We consider the problem of testing if a given function$f : \F_q^n \rightarrow \F_q$is close to a$n$-variate degree$d$polynomial over the finite field$\F_q$of$q$elements. The natural, low-query, test for this property would be to pick the smallest dimension$t = t_{q,d}\approx d/q$such ... more >>> TR09-086 | 2nd October 2009 Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman #### Optimal testing of Reed-Muller codes Revisions: 1 We consider the problem of testing if a given function$f : \F_2^n \rightarrow \F_2$is close to any degree$d$polynomial in$n$variables, also known as the Reed-Muller testing problem. Alon et al.~\cite{AKKLR} proposed and analyzed a natural$2^{d+1}$-query test for this property and showed that it accepts more >>> TR04-049 | 15th June 2004 Piotr Berman, Marek Karpinski, Yakov Nekrich #### Optimal Trade-Off for Merkle Tree Traversal We prove upper and lower bounds for computing Merkle tree traversals, and display optimal trade-offs between time and space complexity of that problem. more >>> TR17-049 | 14th March 2017 Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri #### Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps We study the problem of testing unateness of functions$f:\{0,1\}^d \to \mathbb{R}.$We give a$O(\frac{d}{\epsilon} \cdot \log\frac{d}{\epsilon})$-query nonadaptive tester and a$O(\frac{d}{\epsilon})$-query adaptive tester and show that both testers are optimal for a fixed distance parameter$\epsilon$. Previously known unateness testers worked only for Boolean functions, and their query ... more >>> TR01-069 | 24th October 2001 Robert Albin Legenstein #### Optimizing the Layout of a Balanced Tree Revisions: 1 It is shown that the total wire length of layouts of a balanced binary tree on a 2-dimensional grid can be reduced by 33% if one does not choose the obvious symmetric'' layout strategy. Furthermore it is shown that the more efficient layout strategy that is presented in this article ... more >>> TR95-015 | 6th February 1995 Bshouty, Cleve, Gavalda, Kannan, Tamon. #### Oracles and queries that are sufficient for exact learning We show what happen to learning if the learner can use NP-oracle. A consequence of our results we show that If NP\subset P/poly then the polynomial Hierarchy collapses to ZPP^NP END_OF_DESCRIPTION Contact: bshouty@cpsc.ucalgary.ca (Nader Bshouty) more >>> TR05-040 | 13th April 2005 Scott Aaronson #### Oracles Are Subtle But Not Malicious Theoretical computer scientists have been debating the role of oracles since the 1970's. This paper illustrates both that oracles can give us nontrivial insights about the barrier problems in circuit complexity, and that they need not prevent us from trying to solve those problems. First, we ... more >>> TR98-039 | 14th July 1998 Christoph Meinel, Thorsten Theobald #### Ordered Binary Decision Diagrams and Their Significance in Computer-Aided Design of VLSI Circuits - a Survey Many problems in computer-aided design of highly integrated circuits (CAD for VLSI) can be transformed to the task of manipulating objects over finite domains. The efficiency of these operations depends substantially on the chosen data structures. In the last years, ordered binary decision diagrams (OBDDs) have ... more >>> TR09-087 | 1st October 2009 Olga Tveretina, Carsten Sinz, Hans Zantema #### Ordered Binary Decision Diagrams, Pigeonhole Formulas and Beyond Groote and Zantema proved that a particular OBDD computation of the pigeonhole formula has an exponential size and that limited OBDD derivations cannot simulate resolution polynomially. Here we show that any arbitrary OBDD Apply refutation of the pigeonhole formula has an exponential size: we prove that the size of one ... more >>> TR05-131 | 7th November 2005 Don Coppersmith, Lisa Fleischer, Atri Rudra #### Ordering by weighted number of wins gives a good ranking for weighted tournaments We consider the following simple algorithm for feedback arc set problem in weighted tournaments --- order the vertices by their weighted indegrees. We show that this algorithm has an approximation guarantee of$5$if the weights satisfy \textit{probability constraints} (for any pair of vertices$u$and$v$,$w_{uv}+w_{vu}=1$). Special cases ... more >>> TR16-053 | 6th April 2016 Jiawei Gao, Russell Impagliazzo #### Orthogonal Vectors is hard for first-order properties on sparse graphs Revisions: 3 Fine-grained reductions, introduced by Vassilevska-Williams and Williams, preserve any improvement in the known algorithms. These have been used very successfully in relating the exact complexities of a wide range of problems, from NP-complete problems like SAT to important quadratic time solvable problems within P such as Edit Distance. However, until ... more >>> TR11-132 | 2nd September 2011 Ludwig Staiger #### Oscillation-free Chaitin$h$-random sequences Revisions: 1 The present paper generalises results by Tadaki [12] and Calude et al. [1] on oscillation-free partially random infinite strings. Moreover, it shows that oscillation-free partial Chaitin randomness can be separated from scillation-free partial strong Martin-L\"of randomness by$\Pi_{1}^{0}$-definable sets of infinite strings. more >>> TR13-189 | 21st December 2013 Periklis Papakonstantinou, Dominik Scheder, Hao Song #### Overlays and Limited Memory Communication Mode(l)s We give new characterizations and lower bounds relating classes in the communication complexity polynomial hierarchy and circuit complexity to limited memory communication models. We introduce the notion of rectangle overlay complexity of a function$f: \{0,1\}^n\times \{0,1\}^n\to\{0,1\}$. This is a natural combinatorial complexity measure in terms of combinatorial rectangles in ... more >>> TR17-102 | 9th June 2017 Oded Goldreich #### Overview of the doubly-efficient interactive proof systems of RRR We provide an overview of the doubly-efficient interactive proof systems of Reingold, Rothblum, and Rothblum (STOC, 2016). Recall that by their result, any set that is decidable in polynomial-time by an algorithm of space complexity$s(n)\leq n^{0.499}\$, has a constant-round interactive proof system
in which the prover runs polynomial time ... more >>>

ISSN 1433-8092 | Imprint