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

**Other**

__
TR11-143
| 2nd November 2011
__

Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena#### Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits

__
TR10-105
| 29th June 2010
__

Scott Aaronson, Dieter van Melkebeek#### A note on circuit lower bounds from derandomization

__
TR24-143
| 25th September 2024
__

Noga Amir, Oded Goldreich, Guy Rothblum#### Doubly Sub-linear Interactive Proofs of Proximity

__
TR24-013
| 26th January 2024
__

Oded Goldreich#### On locally-characterized expander graphs (a survey)

Revisions: 1

__
TR23-146
| 27th September 2023
__

Oded Goldreich, Laliv Tauber#### On Testing Isomorphism to a Fixed Graph in the Bounded-Degree Graph Model

Revisions: 1

__
TR23-064
| 3rd May 2023
__

Oded Goldreich#### On the Lower Bound on the Length of Relaxed Locally Decodable Codes

__
TR19-152
| 6th November 2019
__

Uma Girish, Ran Raz, Avishay Tal#### Quantum versus Randomized Communication Complexity, with Efficient Players

__
TR19-010
| 21st January 2019
__

Dorit Aharonov, Alex Bredariol Grilo#### Stoquastic PCP vs. Randomness

__
TR15-114
| 18th July 2015
__

Avishay Tal#### #SAT Algorithms from Shrinkage

__
TR13-159
| 20th November 2013
__

Per Austrin, Venkatesan Guruswami, Johan HÃ¥stad#### $(2+\epsilon)$-SAT is NP-hard

Revisions: 2

__
TR15-062
| 15th April 2015
__

Sangxia Huang#### $2^{(\log N)^{1/4-o(1)}}$ Hardness for Hypergraph Coloring

Revisions: 2

__
TR11-119
| 4th September 2011
__

Subhash Khot, Preyas Popat, Nisheeth Vishnoi#### $2^{\log^{1-\epsilon} n}$ Hardness for Closest Vector Problem with Preprocessing

__
TR21-023
| 20th February 2021
__

Jiatu Li, Tianqi Yang#### $3.1n - o(n)$ Circuit Lower Bounds for Explicit Functions

__
TR13-088
| 16th June 2013
__

Zachary Remscrim, Michael Sipser#### $AC^0$ Pseudorandomness of Natural Operations

__
TR19-021
| 19th February 2019
__

Rahul Ilango#### $AC^0[p]$ Lower Bounds and NP-Hardness for Variants of MCSP

__
TR24-048
| 4th March 2024
__

Kuan Cheng, Yichuan Wang#### $BPL\subseteq L-AC^1$

__
TR19-116
| 9th September 2019
__

Venkatesan Guruswami, Sai Sandeep#### $d$-to-$1$ Hardness of Coloring $4$-colorable Graphs with $O(1)$ colors

Revisions: 1

__
TR09-018
| 8th March 2009
__

Yoav Tzur#### $GF(2^n)$-Linear Tests versus $GF(2)$-Linear Tests

Comments: 1

__
TR20-127
| 21st August 2020
__

Nikhil Bansal, Makrand Sinha#### $k$-Forrelation Optimally Separates Quantum and Classical Query Complexity

Revisions: 2

__
TR12-105
| 17th August 2012
__

Madhur Tulsiani, Pratik Worah#### $LS_+$ Lower Bounds from Pairwise Independence

__
TR23-111
| 29th July 2023
__

Vaibhav Krishan#### $\mathit{MidBit}^+$, Torus Polynomials and Non-classical Polynomials: Equivalences for $\mathit{ACC}$ Lower Bounds

__
TR15-030
| 6th March 2015
__

Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie#### ${\mathrm{AC}^{0} \circ \mathrm{MOD}_2}$ lower bounds for the Boolean Inner Product

Revisions: 1

__
TR17-178
| 24th November 2017
__

Justin Holmgren, Lisa Yang#### (A Counterexample to) Parallel Repetition for Non-Signaling Multi-Player Games

__
TR05-041
| 12th April 2005
__

Shengyu Zhang#### (Almost) tight bounds for randomized and quantum Local Search on hypercubes and grids

Revisions: 2

__
TR23-205
| 21st December 2023
__

Marshall Ball, Dana Dachman-Soled#### (Inefficient Prover) ZAPs from Hard-to-Invert Functions

__
TR22-010
| 18th January 2022
__

Marshall Ball, Dana Dachman-Soled, Julian Loss#### (Nondeterministic) Hardness vs. Non-Malleability

__
TR20-012
| 14th February 2020
__

Dmitry Sokolov#### (Semi)Algebraic Proofs over $\{\pm 1\}$ Variables

__
TR14-024
| 19th February 2014
__

Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider#### 0-1 Integer Linear Programming with a Linear Number of Constraints

__
TR08-094
| 10th October 2008
__

Piotr Berman, Marek Karpinski, Alexander Zelikovsky#### 1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two

__
TR01-047
| 3rd July 2001
__

Piotr Berman, Sridhar Hannenhalli, Marek Karpinski#### 1.375-Approximation Algorithm for Sorting by Reversals

__
TR95-003
| 1st January 1995
__

Marek Karpinski, Alexander Zelikovsky#### 1.757 and 1.267-Approximation Algorithms for the Network and and Rectilinear Steiner Tree Problems

__
TR15-163
| 11th October 2015
__

James Aisenberg, Maria Luisa Bonet, Sam Buss#### 2-D Tucker is PPA complete

__
TR05-062
| 17th June 2005
__

A. Pavan, N. V. Vinodchandran#### 2-Local Random Reductions to 3-Valued Functions

__
TR14-094
| 24th July 2014
__

Zeev Dvir, Sivakanth Gopi#### 2-Server PIR with sub-polynomial communication

__
TR08-033
| 21st March 2008
__

Elena Grigorescu, Tali Kaufman, Madhu Sudan#### 2-Transitivity is Insufficient for Local Testability

__
TR14-116
| 6th September 2014
__

Rahul Mehta#### 2048 is (PSPACE) Hard, but Sometimes Easy

__
TR95-033
| 29th June 1995
__

Richard Beigel, David Eppstein#### 3-Coloring in time O(1.3446^n): a no-MIS algorithm

__
TR05-134
| 17th November 2005
__

Xi Chen, Xiaotie Deng#### 3-NASH is PPAD-Complete

__
TR08-069
| 5th August 2008
__

Klim Efremenko#### 3-Query Locally Decodable Codes of Subexponential Length

__
TR03-054
| 2nd July 2003
__

Daniel Rolf#### 3-SAT in RTIME(O(1.32793^n)) - Improving Randomized Local Search by Initializing Strings of 3-Clauses

__
TR03-006
| 23rd January 2003
__

Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova#### 3CNF Properties are Hard to Test

__
TR13-009
| 9th January 2013
__

Zahra Jafargholi, Emanuele Viola#### 3SUM, 3XOR, Triangles

Revisions: 1

__
TR20-097
| 30th June 2020
__

Md Lutfar Rahman, Thomas Watson#### 6-Uniform Maker-Breaker Game Is PSPACE-Complete

__
TR05-069
| 11th July 2005
__

Piotr Berman, Marek Karpinski#### 8/7-Approximation Algorithm for (1,2)-TSP

Revisions: 2

__
TR02-070
| 13th December 2002
__

Wenceslas Fernandez de la Vega, Marek Karpinski#### 9/8-Approximation Algorithm for Random MAX-3SAT

Revisions: 1

__
TR10-090
| 14th May 2010
__

Nikolay Vereshchagin#### {Algorithmic Minimal Sufficient Statistics: a New Definition

__
TR13-052
| 3rd April 2013
__

Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam, Nitin Saurabh#### {Upper Bounds on Fourier Entropy

Revisions: 2

Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

We present a single, common tool to strictly subsume all known cases of polynomial time blackbox polynomial identity testing (PIT) that have been hitherto solved using diverse tools and techniques. In particular, we show that polynomial time hitting-set generators for identity testing of the two seemingly different and well studied ... more >>>

Scott Aaronson, Dieter van Melkebeek

We present an alternate proof of the result by Kabanets and Impagliazzo that derandomizing polynomial identity testing implies circuit lower bounds. Our proof is simpler, scales better, and yields a somewhat stronger result than the original argument.

more >>>Noga Amir, Oded Goldreich, Guy Rothblum

We initiate a study of doubly-efficient interactive proofs of proximity, while focusing on properties that can be tested within query-complexity that is significantly sub-linear, and seeking interactive proofs of proximity in which

1. The query-complexity of verification is significantly smaller than the query-complexity of testing.

2. The query-complexity of the ... more >>>

Oded Goldreich

We consider the notion of a local-characterization of an infinite family of unlabeled bounded-degree graphs.

Such a local-characterization is defined in terms of a finite set of (marked) graphs yielding a generalized notion of subgraph-freeness, which extends the standard notions of induced and non-induced subgraph freeness.

We survey the work ... more >>>

Oded Goldreich, Laliv Tauber

We consider the problem of testing isomorphism to a fixed graph in the bounded-degree graph model. Our main result is that, for almost all $d$-regular $n$-vertex graphs $H$,

testing isomorphism to $H$ can be done using $\tildeO({\sqrt n})$ queries.

This result is shown to be optimal (up to ...
more >>>

Oded Goldreich

We revisit the known proof of the lower bound on the length of relaxed locally decodable codes, providing an arguably simpler exposition that yields a slightly better lower bound for the non-adaptive case and a weaker bound in the general case.

Recall that a locally decodable code is an error ... more >>>

Uma Girish, Ran Raz, Avishay Tal

We study a new type of separation between quantum and classical communication complexity which is obtained using quantum protocols where all parties are efficient, in the sense that they can be implemented by small quantum circuits with oracle access to their inputs. More precisely, we give an explicit partial Boolean ... more >>>

Dorit Aharonov, Alex Bredariol Grilo

The derandomization of MA, the probabilistic version of NP, is a long standing open question. In this work, we connect this problem to a variant of another major problem: the quantum PCP conjecture. Our connection goes through the surprising quantum characterization of MA by Bravyi and Terhal. They proved the ... more >>>

Avishay Tal

We present a deterministic algorithm that counts the number of satisfying assignments for any de Morgan formula $F$ of size at most $n^{3-16\epsilon}$ in time $2^{n-n^{\epsilon}}\cdot \mathrm{poly}(n)$, for any small constant $\epsilon>0$. We do this by derandomizing the randomized algorithm mentioned by Komargodski et al. (FOCS, 2013) and Chen et ... more >>>

Per Austrin, Venkatesan Guruswami, Johan HÃ¥stad

We prove the following hardness result for a natural promise variant of the classical CNF-satisfiability problem: Given a CNF-formula where each clause has width $w$ and the guarantee that there exists an assignment satisfying at least $g = \lceil \frac{w}{2}\rceil -1$ literals in each clause, it is NP-hard to find ... more >>>

Sangxia Huang

We show that it is quasi-NP-hard to color 2-colorable 8-uniform hypergraphs with $2^{(\log N)^{1/4-o(1)}}$ colors, where $N$ is the number of vertices. There has been much focus on hardness of hypergraph coloring recently. Guruswami, H{\aa}stad, Harsha, Srinivasan and Varma showed that it is quasi-NP-hard to color 2-colorable 8-uniform hypergraphs with ... more >>>

Subhash Khot, Preyas Popat, Nisheeth Vishnoi

We prove that for an arbitrarily small constant $\eps>0,$ assuming NP$\not \subseteq$DTIME$(2^{{\log^{O(1/\epsilon)} n}})$, the preprocessing versions of the closest vector problem and the nearest codeword problem are hard to approximate within a factor better than $2^{\log ^{1-\epsilon}n}.$ This improves upon the previous hardness factor of $(\log n)^\delta$ for some $\delta ... more >>>

Jiatu Li, Tianqi Yang

Proving circuit lower bounds has been an important but extremely hard problem for decades. Although one may show that almost every function $f:\mathbb{F}_2^n\to\mathbb{F}_2$ requires circuit of size $\Omega(2^n/n)$ by a simple counting argument, it remains unknown whether there is an explicit function (for example, a function in $NP$) not computable ... more >>>

Zachary Remscrim, Michael Sipser

A function $f:\Sigma^{*} \rightarrow \Sigma^{*}$ on strings is $AC^0$-pseudorandom if the pair $(x,\hat f(x))$ is $AC^0$-indistinguishable from a uniformly random pair $(y,z)$ when $x$ is chosen uniformly at random. Here $\hat f(x)$ is the string that is obtained from $f(x)$ by discarding some selected bits from $f(x)$.

It is shown ... more >>>

Rahul Ilango

The Minimum Circuit Size Problem (MCSP) asks whether a (given) Boolean function has a circuit of at most a (given) size. Despite over a half-century of study, we know relatively little about the computational complexity of MCSP. We do know that questions about the complexity of MCSP have significant ramifications ... more >>>

Kuan Cheng, Yichuan Wang

Whether $BPL=L$ (which is conjectured to be equal), or even whether $BPL\subseteq NL$, is a big open problem in theoretical computer science. It is well known that $L-NC^1\subseteq L\subseteq NL\subseteq L-AC^1$. In this work we will show that $BPL\subseteq L-AC^1$, which was not known before. Our proof is based on ... more >>>

Venkatesan Guruswami, Sai Sandeep

The $d$-to-$1$ conjecture of Khot asserts that it is hard to satisfy an $\epsilon$ fraction of constraints of a satisfiable $d$-to-$1$ Label Cover instance, for arbitrarily small $\epsilon > 0$. We prove that the $d$-to-$1$ conjecture for any fixed $d$ implies the hardness of coloring a $4$-colorable graph with $C$ ... more >>>

Yoav Tzur

A small-biased distribution of bit sequences is defined as one withstanding $GF(2)$-linear tests for randomness, which are linear combinations of the bits themselves. We consider linear combinations over larger fields, specifically, $GF(2^n)$ for $n$ that divides the length of the bit sequence. Indeed, this means that we partition the bits ... more >>>

Nikhil Bansal, Makrand Sinha

Aaronson and Ambainis (SICOMP '18) showed that any partial function on $N$ bits that can be computed with an advantage $\delta$ over a random guess by making $q$ quantum queries, can also be computed classically with an advantage $\delta/2$ by a randomized decision tree making ${O}_q(N^{1-\frac{1}{2q}}\delta^{-2})$ queries. Moreover, they conjectured ... more >>>

Madhur Tulsiani, Pratik Worah

We consider the complexity of LS$_+$ refutations of unsatisfiable instances of Constraint Satisfaction Problems (CSPs) when the underlying predicate supports a pairwise independent distribution on its satisfying assignments. This is the most general condition on the predicates under which the corresponding MAX-CSP problem is known to be approximation resistant.

We ... more >>>

Vaibhav Krishan

We give a conversion from non-classical polynomials to $\mathit{MidBit}^+$ circuits and vice-versa. This conversion, along with previously known results, shows that torus polynomials, non-classical polynomials and $\mathit{MidBit}^+$ circuits can all be converted to each other. Therefore lower bounds against any of these models lead to lower bounds against all three ... more >>>

Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie

$\mathrm{AC}^{0} \circ \mathrm{MOD}_2$ circuits are $\mathrm{AC}^{0}$ circuits augmented with a layer of parity gates just above the input layer. We study the $\mathrm{AC}^{0} \circ \mathrm{MOD}_2$ circuit lower bound for computing the Boolean Inner Product functions. Recent works by Servedio and Viola (ECCC TR12-144) and Akavia et al. (ITCS 2014) have ... more >>>

Justin Holmgren, Lisa Yang

We give a three-player game whose non-signaling value is constant (2/3) under any number of parallel repetitions. This is the first known setting where parallel repetition completely fails to reduce the maximum winning probability of computationally unbounded players.

We also show that the best known results on non-signaling ...
more >>>

Shengyu Zhang

The Local Search problem, which finds a

local minimum of a black-box function on a given graph, is of both

practical and theoretical importance to many areas in computer

science and natural sciences. In this paper, we show that for the

Boolean hypercube $\B^n$, the randomized query complexity of Local

more >>>

Marshall Ball, Dana Dachman-Soled

A ZAP is a witness-indistinguishable two-message public-coin interactive proof with the following simple structure: the verifier sends a uniformly random string, the prover responds, and the verifier decides in polynomial time whether to accept or reject.

We show that one-way functions imply the existence of ...
more >>>

Marshall Ball, Dana Dachman-Soled, Julian Loss

We present the first truly explicit constructions of \emph{non-malleable codes} against tampering by bounded polynomial size circuits. These objects imply unproven circuit lower bounds and our construction is secure provided E requires exponential size nondeterministic circuits, an assumption from the derandomization literature.

Prior works on NMC ...
more >>>

Dmitry Sokolov

One of the major open problems in proof complexity is to prove lower bounds on $AC_0[p]$-Frege proof

systems. As a step toward this goal Impagliazzo, Mouli and Pitassi in a recent paper suggested to prove

lower bounds on the size for Polynomial Calculus over the $\{\pm 1\}$ basis. In this ...
more >>>

Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider

We give an exact algorithm for the 0-1 Integer Linear Programming problem with a linear number of constraints that improves over exhaustive search by an exponential factor. Specifically, our algorithm runs in time $2^{(1-\text{poly}(1/c))n}$ where $n$ is the

number of variables and $cn$ is the number of constraints. The key ...
more >>>

Piotr Berman, Marek Karpinski, Alexander Zelikovsky

We give a 1.25 approximation algorithm for the Steiner Tree Problem with distances one and two, improving on the best known bound for that problem.

more >>>Piotr Berman, Sridhar Hannenhalli, Marek Karpinski

Analysis of genomes evolving by inversions leads to a general

combinatorial problem of {\em Sorting by Reversals}, MIN-SBR, the problem of

sorting a permutation by a minimum number of reversals.

This combinatorial problem has a long history, and a number of other

motivations. It was studied in a great ...
more >>>

Marek Karpinski, Alexander Zelikovsky

The Steiner tree problem requires to find a shortest tree connection

a given set of terminal points in a metric space. We suggest a better

and fast heuristic for the Steiner problem in graphs and in

rectilinear plane. This heuristic finds a Steiner tree at ...
more >>>

James Aisenberg, Maria Luisa Bonet, Sam Buss

The 2-D Tucker search problem is shown to be PPA-hard under many-one reductions; therefore it is complete for PPA. The same holds for $k$-D Tucker for all $k\ge 2$. This corrects a claim in the literature that the Tucker search problem is in PPAD.

more >>>A. Pavan, N. V. Vinodchandran

Yao (in a lecture at DIMACS Workshop on structural complexity and

cryptography) showed that if a language L is 2-locally-random

reducible to a Boolean functio, then L is in PSPACE/poly.

Fortnow and Szegedy quantitatively improved Yao's result to show that

such languages are in fact in NP/poly (Information Processing Letters, ...
more >>>

Zeev Dvir, Sivakanth Gopi

A 2-server Private Information Retrieval (PIR) scheme allows a user to retrieve the $i$th bit of an $n$-bit database replicated among two servers (which do not communicate) while not revealing any information about $i$ to either server. In this work we construct a 1-round 2-server PIR with total communication cost ... more >>>

Elena Grigorescu, Tali Kaufman, Madhu Sudan

A basic goal in Property Testing is to identify a

minimal set of features that make a property testable.

For the case when the property to be tested is membership

in a binary linear error-correcting code, Alon et al.~\cite{AKKLR}

had conjectured that the presence of a {\em single} low weight

more >>>

Rahul Mehta

We prove that a variant of 2048, a popular online puzzle game, is PSPACE-Complete. Our hardness result

holds for a version of the problem where the player has oracle access to the computer player's moves.

Specifically, we show that for an $n \times n$ game board $G$, computing a

more >>>

Richard Beigel, David Eppstein

We consider worst case time bounds for NP-complete problems

including 3-SAT, 3-coloring, 3-edge-coloring, and 3-list-coloring.

Our algorithms are based on a common generalization of these problems,

called symbol-system satisfiability or, briefly, SSS [R. Floyd &

R. Beigel, The Language of Machines]. 3-SAT is equivalent to

(2,3)-SSS while the other problems ...
more >>>

Xi Chen, Xiaotie Deng

In this paper, we improve a recent result of Daskalakis, Goldberg and Papadimitriou on PPAD-completeness of 4-Nash, showing that 3-Nash is PPAD-complete.

more >>>Klim Efremenko

Locally Decodable Codes (LDC) allow one to decode any particular

symbol of the input message by making a constant number of queries

to a codeword, even if a constant fraction of the codeword is

damaged. In recent work ~\cite{Yekhanin08} Yekhanin constructs a

$3$-query LDC with sub-exponential length of size

$\exp(\exp(O(\frac{\log ...
more >>>

Daniel Rolf

This paper establishes a randomized algorithm that finds a satisfying assignment for a satisfiable formula $F$ in 3-CNF in $O(1.32793^n)$ expected running time. The algorithms is based on the analysis of so-called strings, which are sequences of 3-clauses where non-succeeding clauses do not share a variable and succeeding clauses share ... more >>>

Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova

For a boolean formula \phi on n variables, the associated property

P_\phi is the collection of n-bit strings that satisfy \phi. We prove

that there are 3CNF properties that require a linear number of queries,

even for adaptive tests. This contrasts with 2CNF properties

that are testable with O(\sqrt{n}) ...
more >>>

Zahra Jafargholi, Emanuele Viola

We show that if one can solve 3SUM on a set of size $n$

in time $n^{1+\epsilon}$ then one can list $t$ triangles in a

graph with $m$ edges in time $\tilde

O(m^{1+\epsilon}t^{1/3+\epsilon'})$ for any $\epsilon' > 0$. This is a

reversal of Patrascu's reduction from 3SUM to

listing triangles ...
more >>>

Md Lutfar Rahman, Thomas Watson

In a STOC 1976 paper, Schaefer proved that it is PSPACE-complete to determine the winner of the so-called Maker-Breaker game on a given set system, even when every set has size at most 11. Since then, there has been no improvement on this result. We prove that the game remains ... more >>>

Piotr Berman, Marek Karpinski

We design a polynomial time 8/7-approximation algorithm for the Traveling Salesman Problem in which all distances are either one or two. This improves over the best known approximation factor of 7/6 for that problem. As a direct application we get a 7/6-approximation algorithm for the Maximum Path Cover Problem, similarily ... more >>>

Wenceslas Fernandez de la Vega, Marek Karpinski

We prove that MAX-3SAT can be approximated in polynomial time

within a factor 9/8 on random instances.

Nikolay Vereshchagin

We express some criticism about the definition of an algorithmic sufficient statistic and, in particular, of an algorithmic minimal sufficient statistic. We propose another definition, which has better properties.

more >>>Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam, Nitin Saurabh

iven a function $f : \{0,1\}^n \to \reals$, its {\em Fourier Entropy} is defined to be $-\sum_S \fcsq{f}{S} \log \fcsq{f}{S}$, where $\fhat$ denotes the Fourier transform of $f$. This quantity arises in a number of applications, especially in the study of Boolean functions. An outstanding open question is a conjecture ... more >>>