Under the auspices of the Computational Complexity Foundation (CCF)

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
TR19-004 | 11th January 2019
Amey Bhangale, Subhash Khot

#### UG-hardness to NP-hardness by Losing Half

Revisions: 1

The $2$-to-$2$ Games Theorem of [KMS-1, DKKMS-1, DKKMS-2, KMS-2] implies that it is NP-hard to distinguish between Unique Games instances with assignment satisfying at least $(\frac{1}{2}-\varepsilon)$ fraction of the constraints $vs.$ no assignment satisfying more than $\varepsilon$ fraction of the constraints, for every constant $\varepsilon>0$. We show that the reduction ... more >>>

TR19-095 | 18th July 2019
Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari

#### Unambiguous Catalytic Computation

The catalytic Turing machine is a model of computation defined by Buhrman, Cleve,
Kouck, Loff, and Speelman (STOC 2014). Compared to the classical space-bounded Turing
machine, this model has an extra space which is filled with arbitrary content in addition
to the clean space. In such a model we study ... more >>>

TR21-016 | 16th February 2021
Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari

#### Unambiguous DNFs from Hex

Revisions: 1

We exhibit an unambiguous $k$-DNF formula that requires CNF width $\tilde{\Omega}(k^{1.5})$. Our construction is inspired by the board game Hex and it is vastly simpler than previous ones, which achieved at best an exponent of $1.22$. Our result is known to imply several other improved separations in query and communication ... more >>>

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: 2 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 >>> TR20-053 | 16th April 2020 Olaf Beyersdorff, Benjamin Böhm #### Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution QBF solvers implementing the QCDCL paradigm are powerful algorithms that successfully tackle many computationally complex applications. However, our theoretical understanding of the strength and limitations of these QCDCL solvers is very limited. In this paper we suggest to formally model QCDCL solvers as proof systems. We define different policies that ... 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 >>> TR20-050 | 18th April 2020 Shuichi Hirahara #### Unexpected Hardness Results for Kolmogorov Complexity Under Uniform Reductions Hardness of computing the Kolmogorov complexity of a given string is closely tied to a security proof of hitting set generators, and thus understanding hardness of Kolmogorov complexity is one of the central questions in complexity theory. In this paper, we develop new proof techniques for showing hardness of computing ... 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 >>> TR18-184 | 5th November 2018 Iddo Tzameret, Stephen Cook #### Uniform, Integral and Feasible Proofs for the Determinant Identities Revisions: 1 Aiming to provide weak as possible axiomatic assumptions in which one can develop basic linear algebra, we give a uniform and integral version of the short propositional proofs for the determinant identities demonstrated over$GF(2)$in Hrubes-Tzameret [SICOMP'15]. Specifically, we show that the multiplicativity of the determinant function and the ... 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: 2 , 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
\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

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

TR21-031 | 3rd March 2021
Vaibhav Krishan

#### Upper Bound for Torus Polynomials

We prove that all functions that have low degree torus polynomials approximating them with small error also have $MidBit^+$ circuits computing them. This serves as a partial converse to the result that all $ACC$ functions have low degree torus polynomials approximating them with small error, by Bhrushundi, Hosseini, Lovett and ... more >>>

TR19-006 | 17th January 2019
Anna Gal, Ridwan Syed

#### Upper Bounds on Communication in terms of Approximate Rank

Revisions: 1

We show that any Boolean function with approximate rank $r$ can be computed by bounded error quantum protocols without prior entanglement of complexity $O( \sqrt{r} \log r)$. In addition, we show that any Boolean function with approximate rank $r$ and discrepancy $\delta$ can be computed by deterministic protocols of complexity ... 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 >>>

TR21-052 | 12th April 2021
Benny Applebaum, Oded Nir

#### Upslices, Downslices, and Secret-Sharing with Complexity of $1.5^n$

A secret-sharing scheme allows to distribute a secret $s$ among $n$ parties such that only some predefined authorized'' sets of parties can reconstruct the secret, and all other unauthorized'' sets learn nothing about $s$.
The collection of authorized/unauthorized sets can be captured by a monotone function $f:\{0,1\}^n\rightarrow \{0,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 >>>

TR19-167 | 21st November 2019
Anant Dhayal, Russell Impagliazzo

#### UTIME Easy-witness Lemma & Some Consequences

Revisions: 2

We prove an easy-witness lemma ($\ewl$) for unambiguous non-deterministic verfiers. We show that if $\utime(t)\subset\mathcal{C}$, then for every $L\in\utime(t)$, for every $\utime(t)$ verifier $V$ for $L$, and for every $x\in L$, there is a certificate $y$ satisfing $V(x,y)=1$, that can be encoded as a truth-table of a $\mathcal{C}$ circuit. Our ... more >>>

TR18-109 | 29th May 2018
Kasper Green Larsen, Jesper Buus Nielsen

#### Yes, There is an Oblivious RAM Lower Bound!

An Oblivious RAM (ORAM) introduced by Goldreich and Ostrovsky
[JACM'96] is a (possibly randomized) RAM, for which the memory access
pattern reveals no information about the operations
performed. The main performance metric of an ORAM is the bandwidth
overhead, i.e., the multiplicative factor extra memory blocks that must be
accessed ... more >>>

ISSN 1433-8092 | Imprint