Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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

U
TR07-112 | 25th September 2007
Alexander A. Sherstov

Unbounded-Error Communication Complexity of Symmetric Functions

The sign-rank of a real matrix M is the least rank
of a matrix R in which every entry has the same sign as the
corresponding entry of M. We determine the sign-rank of every
matrix of the form M=[ D(|x AND y|) ]_{x,y}, where
D:{0,1,...,n}->{-1,+1} is given and ... more >>>


TR06-126 | 2nd October 2006
Piotr Indyk

Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1

We give an explicit construction of a constant-distortion embedding of an n-dimensional L_2 space into an n^{1+o(1)}-dimensional L_1 space.

more >>>

TR09-064 | 3rd August 2009
Harry Buhrman, Lance Fortnow, Rahul Santhanam

Unconditional Lower Bounds against Advice

We show several unconditional lower bounds for exponential time classes
against polynomial time classes with advice, including:
\begin{enumerate}
\item For any constant $c$, $\NEXP \not \subseteq \P^{\NP[n^c]}/n^c$
\item For any constant $c$, $\MAEXP \not \subseteq \MA/n^c$
\item $\BPEXP \not \subseteq \BPP/n^{o(1)}$
\end{enumerate}

It was previously unknown even whether $\NEXP \subseteq ... more >>>


TR07-075 | 9th August 2007
Shachar Lovett

Unconditional pseudorandom generators for low degree polynomials

We give an explicit construction of pseudorandom
generators against low degree polynomials over finite fields. We
show that the sum of $2^d$ small-biased generators with error
$\epsilon^{2^{O(d)}}$ is a pseudorandom generator against degree $d$
polynomials with error $\epsilon$. This gives a generator with seed
length $2^{O(d)} \log{(n/\epsilon)}$. Our construction follows ... more >>>


TR17-037 | 25th February 2017
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla

Understanding Cutting Planes for QBFs

We define a cutting planes system CP+$\forall$red for quantified Boolean formulas (QBF) and analyse the proof-theoretic strength of this new calculus. While in the propositional case, Cutting Planes is of intermediate strength between resolution and Frege, our findings here show that the situation in QBF is slightly more complex: while ... more >>>


TR17-098 | 28th May 2017
Raman Arora, Amitabh Basu , Poorya Mianjy, Anirbit Mukherjee

Understanding Deep Neural Networks with Rectified Linear Units

Revisions: 1

In this paper we investigate the family of functions representable by deep neural networks (DNN) with rectified linear units (ReLU). We give the first-ever polynomial time (in the size of data) algorithm to train to global optimality a ReLU DNN with one hidden layer, assuming the input dimension and number ... more >>>


TR16-011 | 27th January 2016
Olaf Beyersdorff, Ján Pich

Understanding Gentzen and Frege systems for QBF

Recently Beyersdorff, Bonacina, and Chew (ITCS'16) introduced a natural class of Frege systems for quantified Boolean formulas (QBF) and showed strong lower bounds for restricted versions of these systems. Here we provide a comprehensive analysis of the new extended Frege system from Beyersdorff et al., denoted EF+$\forall$red, which is a ... more >>>


TR07-043 | 7th May 2007
Uriel Feige, Guy Kindler, Ryan O'Donnell

Understanding Parallel Repetition Requires Understanding Foams

Motivated by the study of Parallel Repetition and also by the Unique
Games Conjecture, we investigate the value of the ``Odd Cycle Games''
under parallel repetition. Using tools from discrete harmonic
analysis, we show that after $d$ rounds on the cycle of length $m$,
the value of the game is ... more >>>


TR15-120 | 12th July 2015
Xiaotie Deng, Zhe Feng, Zhengyang Liu, Qi Qi

Understanding PPA-Completeness

Revisions: 1

The search complexity classes {\bf PPA} and {\bf PPAD} were proposed by Papadimitriou twenty years ago for characterizing the computational difficulties of many interesting natural search problems. While many members in the complete class of {\bf PPAD}, {\bf PPAD}-completeness, are established in the past twenty years, the understanding of the ... more >>>


TR10-125 | 11th August 2010
Eli Ben-Sasson, Jakob Nordström

Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions

For current state-of-the-art satisfiability algorithms based on the DPLL procedure and clause learning, the two main bottlenecks are the amounts of time and memory used. In the field of proof complexity, these resources correspond to the length and space of resolution proofs for formulas in conjunctive normal form (CNF). There ... more >>>


TR09-034 | 25th March 2009
Eli Ben-Sasson, Jakob Nordström

Understanding Space in Resolution: Optimal Lower Bounds and Exponential Trade-offs

Comments: 1

For current state-of-the-art satisfiability algorithms based on the
DPLL procedure and clause learning, the two main bottlenecks are the
amounts of time and memory used. Understanding time and memory
consumption, and how they are related to one another, is therefore a
question of considerable practical importance. In the field of ... more >>>


TR04-094 | 10th November 2004
Omer Reingold

Undirected ST-Connectivity in Log-Space

We present a deterministic, log-space algorithm that solves
st-connectivity in undirected graphs. The previous bound on the
space complexity of undirected st-connectivity was
log^{4/3}() obtained by Armoni, Ta-Shma, Wigderson and
Zhou. As undirected st-connectivity is
complete for the class of problems solvable by symmetric,
non-deterministic, log-space computations (the class SL), ... more >>>


TR01-033 | 27th April 2001
Eric Allender, David Mix Barrington, William Hesse

Uniform Circuits for Division: Consequences and Problems

Integer division has been known to lie in P-uniform TC^0 since
the mid-1980's, and recently this was improved to DLOG-uniform
TC^0. At the time that the results in this paper were proved and
submitted for conference presentation, it was unknown whether division
lay in DLOGTIME-uniform TC^0 (also known as ... more >>>


TR00-065 | 7th September 2000
Eric Allender, David Mix Barrington

Uniform Circuits for Division: Consequences and Problems

Comments: 2

The essential idea in the fast parallel computation of division and
related problems is that of Chinese remainder representation
(CRR) -- storing a number in the form of its residues modulo many
small primes. Integer division provides one of the few natural
examples of problems for which ... more >>>


TR12-059 | 14th May 2012
Rahul Santhanam, Ryan Williams

Uniform Circuits, Lower Bounds, and QBF Algorithms

We explore the relationships between circuit complexity, the complexity of generating circuits, and circuit-analysis algorithms. Our results can be roughly divided into three parts:

1. Lower Bounds Against Medium-Uniform Circuits. Informally, a circuit class is ``medium uniform'' if it can be generated by an algorithmic process that is somewhat complex ... more >>>


TR10-069 | 17th April 2010
Eric Allender, Vikraman Arvind, Fengming Wang

Uniform Derandomization from Pathetic Lower Bounds

Revisions: 1 , Comments: 1

A recurring theme in the literature on derandomization is that probabilistic
algorithms can be simulated quickly by deterministic algorithms, if one can obtain *impressive* (i.e., superpolynomial, or even nearly-exponential) circuit size lower bounds for certain problems. In contrast to what is
needed for derandomization, existing lower bounds seem rather pathetic ... more >>>


TR08-079 | 31st August 2008
Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson

Uniform Direct-Product Theorems: Simplified, Optimized, and Derandomized

The classical Direct-Product Theorem for circuits says
that if a Boolean function $f:\{0,1\}^n\to\{0,1\}$ is somewhat hard
to compute on average by small circuits, then the corresponding
$k$-wise direct product function
$f^k(x_1,\dots,x_k)=(f(x_1),\dots,f(x_k))$ (where each
$x_i\in\{0,1\}^n$) is significantly harder to compute on average by
slightly smaller ... more >>>


TR98-032 | 10th June 1998
Mihir Bellare, Oded Goldreich, Erez Petrank

Uniform Generation of NP-witnesses using an NP-oracle.

A Uniform Generation procedure for $NP$ is an
algorithm which given any input in a fixed NP-language, outputs a uniformly
distributed NP-witness for membership of the input in the language.
We present a Uniform Generation procedure for $NP$ that runs in probabilistic
polynomial-time with an NP-oracle. This improves upon ... more >>>


TR06-154 | 13th December 2006
Joshua Buresh-Oppenheim, Valentine Kabanets, Rahul Santhanam

Uniform Hardness Amplification in NP via Monotone Codes

We consider the problem of amplifying uniform average-case hardness
of languages in $\NP$, where hardness is with respect to $\BPP$
algorithms. We introduce the notion of \emph{monotone}
error-correcting codes, and show that hardness amplification for
$\NP$ is essentially equivalent to constructing efficiently
\emph{locally} encodable and \emph{locally} list-decodable monotone
codes. The ... more >>>


TR98-023 | 16th April 1998
Eric Allender, Shiyu Zhou

Uniform Inclusions in Nondeterministic Logspace

We show that the complexity class LogFew is contained
in NL $\cap$ SPL. Previously, this was known only to
hold in the nonuniform setting.

more >>>

TR06-062 | 24th April 2006
Subhas Kumar Ghosh

Unique k-SAT is as Hard as k-SAT

Revisions: 1 , Comments: 3

In this work we show that Unique k-SAT is as Hard as k-SAT for every $k \in {\mathds N}$. This settles a conjecture by Calabro, Impagliazzo, Kabanets and Paturi \cite{CIKP03}. To provide an affirmative answer to this conjecture, we develop a randomness optimal construction of Isolation Lemma(see Valiant and Vazirani ... more >>>


TR07-025 | 5th March 2007
Benoit Larose, Pascal Tesson, Pascal Tesson

Universal Algebra and Hardness Results for Constraint Satisfaction Problems

We present algebraic conditions on constraint languages \Gamma
that ensure the hardness of the constraint satisfaction problem
CSP(\Gamma) for complexity classes L, NL, P, NP and Mod_pL.
These criteria also give non-expressibility results for various
restrictions of Datalog. Furthermore, we show that if
CSP(\Gamma) is not first-order definable then it ... more >>>


TR01-093 | 2nd December 2001
Boaz Barak, Oded Goldreich

Universal Arguments and their Applications


We put forward a new type of
computationally-sound proof systems, called universal-arguments,
which are related but different from both CS-proofs (as defined
by Micali) and arguments (as defined by Brassard, Chaum and
Crepeau). In particular, we adopt the instance-based
prover-efficiency paradigm of CS-proofs, but follow the
computational-soundness condition of ... more >>>


TR01-072 | 18th October 2001
Ronald Cramer, Victor Shoup

Universal Hash Proofs and and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption

Revisions: 2

We present several new and fairly practical public-key encryption
schemes and prove them secure against
adaptive chosen ciphertext attack. One scheme is based on Paillier's
Decision Composite Residuosity (DCR) assumption,
while another is based in the classical Quadratic Residuosity (QR)
assumption. The analysis is in the standard ... more >>>


TR16-042 | 19th March 2016
Oded Goldreich, Tom Gur

Universal Locally Testable Codes

Revisions: 2

We initiate a study of ``universal locally testable codes" (universal-LTCs). These codes admit local tests for membership in numerous possible subcodes, allowing for testing properties of the encoded message. More precisely, a universal-LTC $C:\{0,1\}^k \to \{0,1\}^n$ for a family of functions $\mathcal{F} = \{ f_i : \{0,1\}^k \to \{0,1\} \}_{i ... more >>>


TR16-192 | 25th November 2016
Oded Goldreich, Tom Gur

Universal Locally Verifiable Codes and 3-Round Interactive Proofs of Proximity for CSP

Revisions: 1 , Comments: 1

Universal locally testable codes (Universal-LTCs), recently introduced in our companion paper [GG16], are codes that admit local tests for membership in numerous possible subcodes, allowing for testing properties of the encoded message. In this work, we initiate the study of the NP analogue of these codes, wherein the testing procedures ... more >>>


TR08-078 | 15th April 2008
Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steve Homer

Universal Quantum Circuits

Abstract:We define and construct efficient depth-universal and almost-size-universal quantum circuits. Such circuits can be viewed as general-purpose simulators for central classes of quantum circuits and can be used to capture the computational power of the circuit class being simulated. For depth we construct universal circuits whose depth is the same ... more >>>


TR07-084 | 4th September 2007
Brendan Juba, Madhu Sudan

Universal Semantic Communication I

Is it possible for two intelligent beings to communicate meaningfully, without any common language or background? This question has interest on its own, but is especially relevant in the context of modern computational infrastructures where an increase in the diversity of computers is making the task of inter-computer interaction increasingly ... more >>>


TR08-095 | 31st October 2008
Brendan Juba, Madhu Sudan

Universal Semantic Communication II: A Theory of Goal-Oriented Communication

Revisions: 1

We continue the investigation of the task of meaningful communication among intelligent entities (players, agents) without any prior common language. Our generic thesis is that such communication is feasible provided the goals of the communicating players are verifiable and compatible. In a previous work we gave supporting evidence for this ... more >>>


TR11-169 | 14th December 2011
Leonid Gurvits

Unleashing the power of Schrijver's permanental inequality with the help of the Bethe Approximation

Revisions: 2

Let $A \in \Omega_n$ be doubly-stochastic $n \times n$ matrix. Alexander Schrijver proved in 1998 the following remarkable inequality
\begin{equation} \label{le}
per(\widetilde{A}) \geq \prod_{1 \leq i,j \leq n} (1- A(i,j)); \widetilde{A}(i,j) =: A(i,j)(1-A(i,j)), 1 \leq i,j \leq n
\end{equation}
We prove in this paper the following generalization (or just clever ... more >>>


TR16-071 | 1st May 2016
Jan Krajicek, Igor Carboni Oliveira

Unprovability of circuit upper bounds in Cook's theory PV

We establish unconditionally that for every integer $k \geq 1$ there is a language $L \in P$ such that it is consistent with Cook's theory PV that $L \notin SIZE(n^k)$. Our argument is non-constructive and does not provide an explicit description of this language.

more >>>

TR03-048 | 24th June 2003
Stefan Droste, Thomas Jansen, Ingo Wegener

Upper and Lower Bounds for Randomized Search Heuristics in Black-Box Optimization

Randomized search heuristics like local search, simulated annealing or all kinds of evolutionary algorithms have many applications. However, for most problems the best worst-case expected run times are achieved by more problem-specific algorithms. This raises the question about the limits of general randomized search heuristics.

Here a framework called black-box ... more >>>


TR97-002 | 28th January 1997
Richard Beigel, Alexis Maciel

Upper and Lower Bounds for Some Depth-3 Circuit Classes

We investigate the complexity of depth-3 threshold circuits
with majority gates at the output, possibly negated AND
gates at level two, and MODm gates at level one. We show
that the fan-in of the AND gates can be reduced to O(log n)
in the case where ... more >>>


TR03-064 | 23rd June 2003
Vikraman Arvind, Piyush Kurur

Upper Bounds on the Complexity of some Galois Theory Problems

Given a polynomial f(X) with rational coefficients as input
we study the problem of (a) finding the order of the Galois group of
f(X), and (b) determining the Galois group of f(X) by finding a small
generator set. Assuming the generalized Riemann hypothesis, we prove
the following complexity bounds:

1. ... more >>>


TR09-106 | 28th October 2009
Abhinav Kumar, Satyanarayana V. Lokam, Vijay M. Patankar, Jayalal Sarma

Using Elimination Theory to construct Rigid Matrices

The rigidity of a matrix A for target rank r is the minimum number of entries
of A that must be changed to ensure that the rank of the altered matrix is at
most r. Since its introduction by Valiant (1977), rigidity and similar
rank-robustness functions of matrices have found ... more >>>


TR00-078 | 18th July 2000
Jean-Pierre Seifert

Using fewer Qubits in Shor's Factorization Algorithm via Simultaneous Diophantine Approximation}

While quantum computers might speed up in principle
certain computations dramatically, in pratice, though
quantum computing technology is still in its infancy.
Even we cannot clearly envison at present what the
hardware of that machine will be like.
Nevertheless, we can be quite confident that it will be
more >>>


TR15-077 | 4th May 2015
Arnab Bhattacharyya, Abhishek Bhowmick

Using higher-order Fourier analysis over general fields

Higher-order Fourier analysis, developed over prime fields, has been recently used in different areas of computer science, including list decoding, algorithmic decomposition and testing. We extend the tools of higher-order Fourier analysis to analyze functions over general fields. Using these new tools, we revisit the results in the above areas.

... more >>>

TR04-087 | 13th October 2004
Alexander Healy, Salil Vadhan, Emanuele Viola

Using Nondeterminism to Amplify Hardness

We revisit the problem of hardness amplification in $\NP$, as
recently studied by O'Donnell (STOC `02). We prove that if $\NP$
has a balanced function $f$ such that any circuit of size $s(n)$
fails to compute $f$ on a $1/\poly(n)$ fraction of inputs, then
$\NP$ has a function $f'$ such ... more >>>


TR06-085 | 15th May 2006
Andreas Jakoby, Maciej Liskiewicz, Aleksander Madry

Using Quantum Oblivious Transfer to Cheat Sensitive Quantum Bit Commitment

Revisions: 1

It is well known that unconditionally secure bit commitment is impossible
even in the quantum world. In this paper a weak variant of quantum bit
commitment, introduced independently by Aharonov et al. and Hardy and Kent
is investigated. In this variant, the parties require some nonzero probability
more >>>


TR01-102 | 18th December 2001
Oded Goldreich

Using the FGLSS-reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs.

Using known results regarding PCP,
we present simple proofs of the inapproximability
of vertex cover for hypergraphs.
Specifically, we show that

(1) Approximating the size of the minimum vertex cover
in $O(1)$-regular hypergraphs to within a factor of~1.99999 is NP-hard.
(2) Approximating the size ... more >>>




ISSN 1433-8092 | Imprint