Under the auspices of the Computational Complexity Foundation (CCF)

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

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

TR10-105 | 29th June 2010
Scott Aaronson, Dieter van Melkebeek

#### A note on circuit lower bounds from derandomization

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

TR15-114 | 18th July 2015
Avishay Tal

#### #SAT Algorithms from Shrinkage

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

TR13-159 | 20th November 2013
Per Austrin, Venkatesan Guruswami, Johan Håstad

#### $(2+\epsilon)$-SAT is NP-hard

Revisions: 2

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

TR15-062 | 15th April 2015
Sangxia Huang

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

Revisions: 2

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

TR11-119 | 4th September 2011
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 >>> TR13-088 | 16th June 2013 Zachary Remscrim, Michael Sipser ####$AC^0$Pseudorandomness of Natural Operations 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 >>> TR09-018 | 8th March 2009 Yoav Tzur ####$GF(2^n)$-Linear Tests versus$GF(2)$-Linear Tests Comments: 1 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 >>> TR12-105 | 17th August 2012 Madhur Tulsiani, Pratik Worah ####$LS_+$Lower Bounds from Pairwise Independence 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 >>> 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$\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 >>> TR17-178 | 24th November 2017 Justin Holmgren, Lisa Yang #### (A Counterexample to) Parallel Repetition for Non-Signaling Multi-Player Games 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 >>> TR05-041 | 12th April 2005 Shengyu Zhang #### (Almost) tight bounds for randomized and quantum Local Search on hypercubes and grids Revisions: 2 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 >>> TR14-024 | 19th February 2014 Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider #### 0-1 Integer Linear Programming with a Linear Number of Constraints 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 >>> 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 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 >>> TR01-047 | 3rd July 2001 Piotr Berman, Sridhar Hannenhalli, Marek Karpinski #### 1.375-Approximation Algorithm for Sorting by Reversals 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 >>> 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 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 >>> TR15-163 | 11th October 2015 James Aisenberg, Maria Luisa Bonet, Sam Buss #### 2-D Tucker is PPA complete 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 >>> TR05-062 | 17th June 2005 A. Pavan, Vinodchandran Variyam #### 2-Local Random Reductions to 3-Valued Functions 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 >>> TR14-094 | 24th July 2014 Zeev Dvir, Sivakanth Gopi #### 2-Server PIR with sub-polynomial communication 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 >>> TR08-033 | 21st March 2008 Elena Grigorescu, Tali Kaufman, Madhu Sudan #### 2-Transitivity is Insufficient for Local Testability 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 >>> TR14-116 | 6th September 2014 Rahul Mehta #### 2048 is (PSPACE) Hard, but Sometimes Easy 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 >>> TR95-033 | 29th June 1995 Richard Beigel, David Eppstein #### 3-Coloring in time O(1.3446^n): a no-MIS algorithm 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 >>> TR05-134 | 17th November 2005 Xi Chen, Xiaotie Deng #### 3-NASH is PPAD-Complete 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 >>> TR08-069 | 5th August 2008 Klim Efremenko #### 3-Query Locally Decodable Codes of Subexponential Length 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 >>>

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

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

TR03-006 | 23rd January 2003

#### 3CNF Properties are Hard to Test

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

TR13-009 | 9th January 2013
Zahra Jafargholi, Emanuele Viola

#### 3SUM, 3XOR, Triangles

Revisions: 1

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

TR05-069 | 11th July 2005
Piotr Berman, Marek Karpinski

#### 8/7-Approximation Algorithm for (1,2)-TSP

Revisions: 2

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

TR02-070 | 13th December 2002
Wenceslas Fernandez de la Vega, Marek Karpinski

#### 9/8-Approximation Algorithm for Random MAX-3SAT

Revisions: 1

We prove that MAX-3SAT can be approximated in polynomial time
within a factor 9/8 on random instances.

more >>>

TR10-090 | 14th May 2010
Nikolay Vereshchagin

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

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

TR13-052 | 3rd April 2013
Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam, Nitin Saurabh

#### {Upper Bounds on Fourier Entropy

Revisions: 1

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

ISSN 1433-8092 | Imprint