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

__
TR19-095
| 18th July 2019
__

Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari#### Unambiguous Catalytic Computation

__
TR07-112
| 25th September 2007
__

Alexander A. Sherstov#### Unbounded-Error Communication Complexity of Symmetric Functions

__
TR06-126
| 2nd October 2006
__

Piotr Indyk#### Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1

__
TR09-064
| 3rd August 2009
__

Harry Buhrman, Lance Fortnow, Rahul Santhanam#### Unconditional Lower Bounds against Advice

__
TR07-075
| 9th August 2007
__

Shachar Lovett#### Unconditional pseudorandom generators for low degree polynomials

__
TR17-037
| 25th February 2017
__

Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla#### Understanding Cutting Planes for QBFs

__
TR17-098
| 28th May 2017
__

Raman Arora, Amitabh Basu , Poorya Mianjy, Anirbit Mukherjee#### Understanding Deep Neural Networks with Rectified Linear Units

Revisions: 2

__
TR16-011
| 27th January 2016
__

Olaf Beyersdorff, Ján Pich#### Understanding Gentzen and Frege systems for QBF

__
TR07-043
| 7th May 2007
__

Uriel Feige, Guy Kindler, Ryan O'Donnell#### Understanding Parallel Repetition Requires Understanding Foams

__
TR15-120
| 12th July 2015
__

Xiaotie Deng, Zhe Feng, Zhengyang Liu, Qi Qi#### Understanding PPA-Completeness

Revisions: 1

__
TR10-125
| 11th August 2010
__

Eli Ben-Sasson, Jakob Nordström#### Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions

__
TR09-034
| 25th March 2009
__

Eli Ben-Sasson, Jakob Nordström#### Understanding Space in Resolution: Optimal Lower Bounds and Exponential Trade-offs

Comments: 1

__
TR04-094
| 10th November 2004
__

Omer Reingold#### Undirected ST-Connectivity in Log-Space

__
TR01-033
| 27th April 2001
__

Eric Allender, David Mix Barrington, William Hesse#### Uniform Circuits for Division: Consequences and Problems

__
TR00-065
| 7th September 2000
__

Eric Allender, David Mix Barrington#### Uniform Circuits for Division: Consequences and Problems

Comments: 2

__
TR12-059
| 14th May 2012
__

Rahul Santhanam, Ryan Williams#### Uniform Circuits, Lower Bounds, and QBF Algorithms

__
TR10-069
| 17th April 2010
__

Eric Allender, Vikraman Arvind, Fengming Wang#### Uniform Derandomization from Pathetic Lower Bounds

Revisions: 1
,
Comments: 1

__
TR08-079
| 31st August 2008
__

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson#### Uniform Direct-Product Theorems: Simplified, Optimized, and Derandomized

__
TR98-032
| 10th June 1998
__

Mihir Bellare, Oded Goldreich, Erez Petrank#### Uniform Generation of NP-witnesses using an NP-oracle.

__
TR06-154
| 13th December 2006
__

Joshua Buresh-Oppenheim, Valentine Kabanets, Rahul Santhanam#### Uniform Hardness Amplification in NP via Monotone Codes

__
TR98-023
| 16th April 1998
__

Eric Allender, Shiyu Zhou#### Uniform Inclusions in Nondeterministic Logspace

__
TR18-184
| 5th November 2018
__

Iddo Tzameret, Stephen Cook#### Uniform, Integral and Feasible Proofs for the Determinant Identities

__
TR06-062
| 24th April 2006
__

Subhas Kumar Ghosh#### Unique k-SAT is as Hard as k-SAT

Revisions: 1
,
Comments: 3

__
TR07-025
| 5th March 2007
__

Benoit Larose, Pascal Tesson, Pascal Tesson#### Universal Algebra and Hardness Results for Constraint Satisfaction Problems

__
TR01-093
| 2nd December 2001
__

Boaz Barak, Oded Goldreich#### Universal Arguments and their Applications

__
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

__
TR16-042
| 19th March 2016
__

Oded Goldreich, Tom Gur#### Universal Locally Testable Codes

Revisions: 2

__
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

__
TR08-078
| 15th April 2008
__

Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steve Homer#### Universal Quantum Circuits

__
TR07-084
| 4th September 2007
__

Brendan Juba, Madhu Sudan#### Universal Semantic Communication I

__
TR08-095
| 31st October 2008
__

Brendan Juba, Madhu Sudan#### Universal Semantic Communication II: A Theory of Goal-Oriented Communication

Revisions: 1

__
TR11-169
| 14th December 2011
__

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

Revisions: 2

__
TR16-071
| 1st May 2016
__

Jan Krajicek, Igor Carboni Oliveira#### Unprovability of circuit upper bounds in Cook's theory PV

__
TR03-048
| 24th June 2003
__

Stefan Droste, Thomas Jansen, Ingo Wegener#### Upper and Lower Bounds for Randomized Search Heuristics in Black-Box Optimization

__
TR97-002
| 28th January 1997
__

Richard Beigel, Alexis Maciel#### Upper and Lower Bounds for Some Depth-3 Circuit Classes

__
TR19-006
| 17th January 2019
__

Anna Gal, Ridwan Syed#### Upper Bounds on Communication in terms of Approximate Rank

Revisions: 1

__
TR03-064
| 23rd June 2003
__

Vikraman Arvind, Piyush Kurur#### Upper Bounds on the Complexity of some Galois Theory Problems

__
TR09-106
| 28th October 2009
__

Abhinav Kumar, Satyanarayana V. Lokam, Vijay M. Patankar, Jayalal Sarma#### Using Elimination Theory to construct Rigid Matrices

__
TR00-078
| 18th July 2000
__

Jean-Pierre Seifert#### Using fewer Qubits in Shor's Factorization Algorithm via Simultaneous Diophantine Approximation}

__
TR15-077
| 4th May 2015
__

Arnab Bhattacharyya, Abhishek Bhowmick#### Using higher-order Fourier analysis over general fields

__
TR04-087
| 13th October 2004
__

Alexander Healy, Salil Vadhan, Emanuele Viola#### Using Nondeterminism to Amplify Hardness

__
TR06-085
| 15th May 2006
__

Andreas Jakoby, Maciej Liskiewicz, Aleksander Madry#### Using Quantum Oblivious Transfer to Cheat Sensitive Quantum Bit Commitment

Revisions: 1

__
TR01-102
| 18th December 2001
__

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

__
TR18-109
| 29th May 2018
__

Kasper Green Larsen, Jesper Buus Nielsen#### Yes, There is an Oblivious RAM Lower Bound!

Amey Bhangale, Subhash Khot

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

Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari

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

Alexander A. Sherstov

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

Piotr Indyk

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 >>>Harry Buhrman, Lance Fortnow, Rahul Santhanam

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

Shachar Lovett

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

Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla

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

Raman Arora, Amitabh Basu , Poorya Mianjy, Anirbit Mukherjee

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

Olaf Beyersdorff, Ján Pich

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

Uriel Feige, Guy Kindler, Ryan O'Donnell

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

Xiaotie Deng, Zhe Feng, Zhengyang Liu, Qi Qi

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

Eli Ben-Sasson, Jakob Nordström

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

Eli Ben-Sasson, Jakob Nordström

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

Omer Reingold

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

Eric Allender, David Mix Barrington, William Hesse

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

Eric Allender, David Mix Barrington

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

Rahul Santhanam, Ryan Williams

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

Eric Allender, Vikraman Arvind, Fengming Wang

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

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson

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

Mihir Bellare, Oded Goldreich, Erez Petrank

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

Joshua Buresh-Oppenheim, Valentine Kabanets, Rahul Santhanam

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

Eric Allender, Shiyu Zhou

We show that the complexity class LogFew is contained

in NL $\cap$ SPL. Previously, this was known only to

hold in the nonuniform setting.

Iddo Tzameret, Stephen Cook

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

Subhas Kumar Ghosh

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

Benoit Larose, Pascal Tesson, Pascal Tesson

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

Boaz Barak, Oded Goldreich

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

Ronald Cramer, Victor Shoup

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

Oded Goldreich, Tom Gur

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

Oded Goldreich, Tom Gur

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

Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steve Homer

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

Brendan Juba, Madhu Sudan

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

Brendan Juba, Madhu Sudan

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

Leonid Gurvits

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

Jan Krajicek, Igor Carboni Oliveira

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 >>>Stefan Droste, Thomas Jansen, Ingo Wegener

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

Richard Beigel, Alexis Maciel

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

Anna Gal, Ridwan Syed

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

Vikraman Arvind, Piyush Kurur

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

Abhinav Kumar, Satyanarayana V. Lokam, Vijay M. Patankar, Jayalal Sarma

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

Jean-Pierre Seifert

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

Arnab Bhattacharyya, Abhishek Bhowmick

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 >>>Alexander Healy, Salil Vadhan, Emanuele Viola

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

Andreas Jakoby, Maciej Liskiewicz, Aleksander Madry

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

Oded Goldreich

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

Kasper Green Larsen, Jesper Buus Nielsen

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