Under the auspices of the Computational Complexity Foundation (CCF)

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

C
TR98-070 | 7th December 1998
Rüdiger Reischuk

#### Can Large Fanin Circuits Perform Reliable Computations in the Presence of Noise?

For ordinary circuits with a fixed upper bound on the maximal fanin
of gates it has been shown that logarithmic redundancy is necessary and
sufficient to overcome random hardware faults.
Here, we consider the same question for unbounded fanin circuits that
in the noiseless case can compute ... more >>>

TR16-059 | 14th April 2016
Alon Rosen, Gil Segev, Ido Shahaf

#### Can PPAD Hardness be Based on Standard Cryptographic Assumptions?

Revisions: 2

We consider the question of whether average-case PPAD hardness can be based on standard cryptographic assumptions, such as the existence of one-way functions or public-key encryption. This question is particularly well-motivated in light of new devastating attacks on obfuscation candidates and their underlying building blocks, which are currently the only ... more >>>

TR99-013 | 28th May 1999
Oded Goldreich, Amit Sahai, Salil Vadhan

#### Can Statistical Zero Knowledge be made Non-Interactive? or On the Relationship of SZK and NISZK

We extend the study of non-interactive statistical zero-knowledge
proofs. Our main focus is to compare the class NISZK of problems
possessing such non-interactive proofs to the class SZK of problems
possessing interactive statistical zero-knowledge proofs. Along these
lines, we first show that if statistical zero knowledge is non-trivial
then so ... more >>>

TR14-142 | 1st November 2014
Subhash Khot, Dana Moshkovitz

#### Candidate Lasserre Integrality Gap For Unique Games

We propose a candidate Lasserre integrality gap construction for the Unique Games problem.
Our construction is based on a suggestion in [KM STOC'11] wherein the authors study the complexity of approximately solving a system of linear equations over reals and suggest it as an avenue towards a (positive) resolution ... more >>>

TR00-090 | 3rd December 2000
Oded Goldreich

#### Candidate One-Way Functions Based on Expander Graphs

We suggest a candidate one-way function using combinatorial
constructs such as expander graphs. These graphs are used to
determine a sequence of small overlapping subsets of input bits,
to which a hard-wired random predicate is applied.
Thus, the function is extremely easy to evaluate:
all that is needed ... more >>>

TR20-141 | 11th September 2020
Inbar Ben Yaacov, Gil Cohen, Anand Kumar Narayanan

#### Candidate Tree Codes via Pascal Determinant Cubes

Tree codes are combinatorial structures introduced by Schulman (STOC 1993) as key ingredients in interactive coding schemes. Asymptotically-good tree codes are long known to exist, yet their explicit construction remains a notoriously hard open problem. Even proposing a plausible construction, without the burden of proof, is difficult and the defining ... more >>>

TR14-033 | 10th March 2014
Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, Alon Rosen

#### Candidate Weak Pseudorandom Functions in $\mathrm{AC}0 \circ \mathrm{MOD}2$

Revisions: 1

Pseudorandom functions (PRFs) play a fundamental role in symmetric-key cryptography. However, they are inherently complex and cannot be implemented in the class $\mathrm{AC}^0( \mathrm{MOD}_2)$. Weak pseudorandom functions (weak PRFs) do not suffer from this complexity limitation, yet they suffice for many cryptographic applications. We study the minimal complexity requirements for ... more >>>

TR04-106 | 19th November 2004
Christian Glaßer, Alan L. Selman, Liyu Zhang

#### Canonical Disjoint NP-Pairs of Propositional Proof Systems

We prove that every disjoint NP-pair is polynomial-time, many-one equivalent to
the canonical disjoint NP-pair of some propositional proof system. Therefore, the degree structure of the class of disjoint NP-pairs and of all canonical pairs is
identical. Secondly, we show that this degree structure is not superficial: Assuming there exist ... more >>>

TR20-110 | 22nd July 2020
Leonid Gurvits, Jonathan Leake

#### Capacity Lower Bounds via Productization

Revisions: 2

The purpose of this note is to state and prove a lower bound on the capacity of a real stable polynomial $p(x)$ which is based only on its value and gradient at $x=1$. This result implies a sharp improvement to a similar inequality proved by Linial-Samorodnitsky-Wigderson in 2000. Such inequalities ... more >>>

TR13-118 | 2nd September 2013
Mahdi Cheraghchi, Venkatesan Guruswami

#### Capacity of Non-Malleable Codes

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), encode messages $s$ in a manner so that tampering the codeword causes the decoder to either output $s$ or a message that is independent of $s$. While this is an impossible goal to achieve against unrestricted tampering functions, rather surprisingly ... more >>>

TR19-147 | 31st October 2019
Gil Cohen, Shahar Samocha

#### Capacity-Approaching Deterministic Interactive Coding Schemes Against Adversarial Errors

We devise a deterministic interactive coding scheme with rate $1-O(\sqrt{\varepsilon\log(1/\varepsilon)})$ against $\varepsilon$-fraction of adversarial errors. The rate we obtain is tight by a result of Kol and Raz (STOC 2013). Prior to this work, deterministic coding schemes for any constant fraction $\varepsilon>0$ of adversarial errors could obtain rate no larger ... more >>>

TR20-056 | 17th April 2020
James Cook, Ian Mertz

The study of branching programs for the Tree Evaluation Problem, introduced by S. Cook et al. (TOCT 2012), remains one of the most promising approaches to separating L from P. Given a label in $[k]$ at each leaf of a complete binary tree and an explicit function in $[k]^2 \to ... more >>> TR09-054 | 7th June 2009 Emanuele Viola, Emanuele Viola #### Cell-Probe Lower Bounds for Prefix Sums We prove that to store n bits x so that each prefix-sum query Sum(i) := sum_{k < i} x_k can be answered by non-adaptively probing q cells of log n bits, one needs memory > n + n/log^{O(q)} n. Our bound matches a recent upper bound of n + n/log^{Omega(q)} ... more >>> TR17-066 | 20th April 2017 Josh Alman, Joshua Wang, Huacheng Yu #### Cell-Probe Lower Bounds from Online Communication Complexity Revisions: 1 In this work, we introduce an online model for communication complexity. Analogous to how online algorithms receive their input piece-by-piece, our model presents one of the players Bob his input piece-by-piece, and has the players Alice and Bob cooperate to compute a result it presents Bob with the next piece. ... more >>> TR22-143 | 7th November 2022 Sourav Chakraborty, Anna Gal, Sophie Laplante, Rajat Mittal, Anupa Sunny #### Certificate games Revisions: 1 We introduce and study Certificate Game complexity, a measure of complexity based on the probability of winning a game where two players are given inputs with different function values and are asked to output some index$i$such that$x_i\neq y_i$, in a zero-communication setting. We give upper and lower ... more >>> TR23-020 | 3rd March 2023 Scott Aaronson, Shih-Han Hung #### Certified Randomness from Quantum Supremacy We propose an application for near-term quantum devices: namely, generating cryptographically certified random bits, to use (for example) in proof-of-stake cryptocurrencies. Our protocol repurposes the existing "quantum supremacy" experiments, based on random circuit sampling, that Google and USTC have successfully carried out starting in 2019. We show that, whenever the ... more >>> TR12-153 | 9th November 2012 Joshua Brody, Amit Chakrabarti, Ranganath Kondapally #### Certifying Equality With Limited Interaction Revisions: 1 The \textsc{equality} problem is usually one's first encounter with communication complexity and is one of the most fundamental problems in the field. Although its deterministic and randomized communication complexity were settled decades ago, we find several new things to say about the problem by focusing on two subtle aspects. The ... more >>> TR12-102 | 16th August 2012 Swastik Kopparty, Srikanth Srinivasan #### Certifying Polynomials for$\mathrm{AC}^0[\oplus]$circuits, with applications In this paper, we introduce and develop the method of certifying polynomials for proving$\mathrm{AC}^0[\oplus]$circuit lower bounds. We use this method to show that Approximate Majority cannot be computed by$\mathrm{AC}^0[\oplus]$circuits of size$n^{1+o(1)}$. This implies a separation between the power of$\mathrm{AC}^0[\oplus]$circuits of near-linear size and ... more >>> TR03-030 | 27th February 2003 Amin Coja-Oghlan, Andreas Goerdt, André Lanka, Frank Schädlich #### Certifying Unsatisfiability of Random 2k-SAT Formulas using Approximation Techniques Abstract. It is known that random k-SAT formulas with at least (2^k*ln2)*n random clauses are unsatisfiable with high probability. This result is simply obtained by bounding the expected number of satisfy- ing assignments of a random k-SAT instance by an expression tending to 0 when n, the number of variables ... more >>> TR13-119 | 2nd September 2013 Emanuele Viola #### Challenges in computational lower bounds We draw two incomplete, biased maps of challenges in computational complexity lower bounds. Our aim is to put these challenges in perspective, and to present some connections which do not seem widely known. more >>> TR06-040 | 6th March 2006 Tomas Feder, Gagan Aggarwal, Rajeev Motwani, An Zhu #### Channel assignment in wireless networks and classification of minimum graph homomorphism We study the problem of assigning different communication channels to acces points in a wireless Local Area Network. Each access point will be assigned a specific radio frequency channel. Since channels with similar frequencies interfere, it is desirable to assign far apart channels (frequencies) to nearby access points. Our goal ... more >>> TR19-081 | 31st May 2019 Iftach Haitner, Noam Mazor, Ronen Shaltiel, Jad Silbak #### Channels of Small Log-Ratio Leakage and Characterization of Two-Party Differentially Private Computation Revisions: 1 Consider a PPT two-party protocol ?=(A,B) in which the parties get no private inputs and obtain outputs O^A,O^B?{0,1}, and let V^A and V^B denote the parties’ individual views. Protocol ? has ?-agreement if Pr[O^A=O^B]=1/2+?. The leakage of ? is the amount of information a party obtains about the event {O^A=O^B}; ... more >>> TR16-076 | 27th April 2016 Krishnamoorthy Dinesh, Sajin Koroth, Jayalal Sarma #### Characterization and Lower Bounds for Branching Program Size using Projective Dimension Revisions: 2 We study projective dimension, a graph parameter (denoted by$pd(G)$for a graph$G$), introduced by (Pudlak, Rodl 1992), who showed that proving lower bounds for$pd(G_f)$for bipartite graphs$G_f$associated with a Boolean function$f$imply size lower bounds for branching programs computing$f$. Despite several attempts (Pudlak, ... more >>> TR09-082 | 20th September 2009 T.C. Vijayaraghavan #### Characterization of ModL using Prime Modulus. Revisions: 1 The complexity class ModL was defined by Arvind and Vijayaraghavan in [AV04] (more precisely in Definition 1.4.1, Vij08],[Definition 3.1, AV]). In this paper, under the assumption that NL =UL, we show that for every language$L\in ModL$there exists a function$f\in \sharpL$and a function$g\in FL$such that ... more >>> TR20-143 | 16th September 2020 Shuichi Hirahara #### Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity We exactly characterize the average-case complexity of the polynomial-time hierarchy (PH) by the worst-case (meta-)complexity of GapMINKT(PH), i.e., an approximation version of the problem of determining if a given string can be compressed to a short PH-oracle efficient program. Specifically, we establish the following equivalence: DistPH is contained in ... more >>> TR22-084 | 2nd June 2022 Yanyi Liu, Rafael Pass #### Characterizing Derandomization Through Hardness of Levin-Kolmogorov Complexity A central open problem in complexity theory concerns the question of whether all efficient randomized algorithms can be simulated by efficient deterministic algorithms. We consider this problem in the context of promise problems (i.e,. the$\prBPP$v.s.$\prP$problem) and show that for all sufficiently large constants$c$, the following ... more >>> TR18-121 | 20th June 2018 Justin Holmgren, Lisa Yang #### Characterizing Parallel Repetition of Non-Signaling Games: Counterexamples and a Dichotomy Theorem Non-signaling games are an important object of study in the theory of computation, for their role both in quantum information and in (classical) cryptography. In this work, we study the behavior of these games under parallel repetition. We show that, unlike the situation both for classical games and for two-player ... more >>> TR15-134 | 19th August 2015 Fu Li, Iddo Tzameret, Zhengyu Wang #### Characterizing Propositional Proofs as Non-Commutative Formulas Does every Boolean tautology have a short propositional-calculus proof? Here, a propositional-calculus (i.e., Frege) proof is any proof starting from a set of axioms and deriving new Boolean formulas using a fixed set of sound derivation rules. Establishing any super-polynomial size lower bound on Frege proofs (in terms of the ... more >>> TR11-141 | 2nd November 2011 Salil Vadhan, Colin Jia Zheng #### Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions Revisions: 3 We provide a characterization of pseudoentropy in terms of hardness of sampling: Let$(X,B)$be jointly distributed random variables such that$B$takes values in a polynomial-sized set. We show that$B$is computationally indistinguishable from a random variable of higher Shannon entropy given$X$if and only if there ... more >>> TR98-057 | 10th September 1998 Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner #### Characterizing Small Depth and Small Space Classes by Operators of Higher Types Motivated by the question of how to define an analog of interactive proofs in the setting of logarithmic time- and space-bounded computation, we study complexity classes defined in terms of operators quantifying over oracles. We obtain new characterizations of$\NCe$,$\L$,$\NL$,$\NP$, ... more >>> TR09-081 | 27th August 2009 Olaf Beyersdorff, Zenon Sadowski #### Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes In this paper we investigate the following two questions: Q1: Do there exist optimal proof systems for a given language L? Q2: Do there exist complete problems for a given promise class C? For concrete languages L (such as TAUT or SAT and concrete promise classes C (such as NP ... more >>> TR22-166 | 23rd November 2022 Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Huacheng Yu #### Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly We study boolean constraint satisfaction problems (CSPs)$\mathrm{Max}\text{-}\mathrm{CSP}^f_n$for all predicates$f: \{ 0, 1 \} ^k \to \{ 0, 1 \}$. In these problems, given an integer$v$and a list of constraints over$n$boolean variables, each obtained by applying$f$to a sequence of literals, we wish ... more >>> TR09-009 | 18th December 2008 T.C. Vijayaraghavan #### Checking Equality of Matroid Linear Representations and the Cycle Matching Problem Revisions: 2 Given linear representations M_1 and M_2 of matroids over a field F, we consider the problem (denoted by ECLR), of checking if M_1 and M_2 represent the same matroid. We show that when F=Z_2, ECLR{Z_2} is complete for$\parityL$. Let M_1,M_2\in Q ^{m\times n} be two matroid linear representations given ... more >>> TR98-062 | 28th October 1998 Oded Goldreich, Dana Ron, Madhu Sudan #### Chinese Remaindering with Errors Revisions: 4 , Comments: 1 The Chinese Remainder Theorem states that a positive integer m is uniquely specified by its remainder modulo k relatively prime integers p_1,...,p_k, provided m < \prod_{i=1}^k p_i. Thus the residues of m modulo relatively prime integers p_1 < p_2 < ... < p_n form a redundant representation of m if ... more >>> TR18-004 | 3rd January 2018 Aayush Ojha, Raghunath Tewari #### Circuit Complexity of Bounded Planar Cutwidth Graph Matching Recently, perfect matching in bounded planar cutwidth bipartite graphs$BGGM$was shown to be in ACC$^0$by Hansen et al.. They also conjectured that the problem is in AC$^0$. In this paper, we disprove their conjecture by showing that the problem is not in AC$^0[p^{\alpha}]$for every prime$p$. ... more >>> TR98-056 | 31st August 1998 Anna Bernasconi, Igor E. Shparlinski #### Circuit Complexity of Testing Square-Free Numbers In this paper we extend the area of applications of the Abstract Harmonic Analysis to the field of Boolean function complexity. In particular, we extend the class of functions to which a spectral technique developed in a series of works of the first author can be applied. This extension ... more >>> TR14-052 | 14th April 2014 Joshua Grochow, Toniann Pitassi #### Circuit complexity, proof complexity, and polynomial identity testing We introduce a new and very natural algebraic proof system, which has tight connections to (algebraic) circuit complexity. In particular, we show that any super-polynomial lower bound on any Boolean tautology in our proof system implies that the permanent does not have polynomial-size algebraic circuits ($VNP \neq VP$). As a ... more >>> TR18-192 | 12th November 2018 Alexander Golovnev, Alexander Kulikov #### Circuit Depth Reductions Revisions: 3 The best known circuit lower bounds against unrestricted circuits remained around$3n$for several decades. Moreover, the only known technique for proving lower bounds in this model, gate elimination, is inherently limited to proving lower bounds of less than$5n$. In this work, we suggest a first non-gate-elimination approach for ... more >>> TR04-004 | 13th January 2004 Ramamohan Paturi, Pavel Pudlak #### Circuit lower bounds and linear codes In 1977 Valiant proposed a graph theoretical method for proving lower bounds on algebraic circuits with gates computing linear functions. He used this method to reduce the problem of proving lower bounds on circuits with linear gates to to proving lower bounds on the rigidity of a matrix, a ... more >>> TR13-037 | 15th March 2013 Alexander Knop #### Circuit Lower Bounds for Heuristic MA Revisions: 2 Santhanam (2007) proved that MA/1 does not have circuits of size$n^k$. We translate his result to the heuristic setting by proving that there is a constant$a$such that for any$k$, there is a language in HeurMA that cannot be solved by circuits of size$n^k$on more ... more >>> TR19-022 | 23rd February 2019 Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis #### Circuit Lower Bounds for MCSP from Local Pseudorandom Generators Revisions: 1 The Minimum Circuit Size Problem (MCSP) asks if a given truth table of a Boolean function$f$can be computed by a Boolean circuit of size at most$\theta$, for a given parameter$\theta$. We improve several circuit lower bounds for MCSP, using pseudorandom generators (PRGs) that are local; a ... more >>> TR07-005 | 17th January 2007 Rahul Santhanam #### Circuit Lower Bounds for Merlin-Arthur Classes We show that for each k > 0, MA/1 (MA with 1 bit of advice) does not have circuits of size n^k. This implies the first superlinear circuit lower bounds for the promise versions of the classes MA, AM and ZPP_{||}^{NP}. We extend our main result in several ways. For ... more >>> TR17-188 | 22nd December 2017 Cody Murray, Ryan Williams #### Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP We prove that if every problem in$NP$has$n^k$-size circuits for a fixed constant$k$, then for every$NP$-verifier and every yes-instance$x$of length$n$for that verifier, the verifier's search space has an$n^{O(k^3)}$-size witness circuit: a witness for$x$that can be encoded with a circuit ... more >>> TR13-077 | 14th May 2013 Ján Pich #### Circuit Lower Bounds in Bounded Arithmetics We prove that$T_{NC^1}$, the true universal first-order theory in the language containing names for all uniform$NC^1$algorithms, cannot prove that for sufficiently large$n$, SAT is not computable by circuits of size$n^{2kc}$where$k\geq 1, c\geq 4$unless each function$f\in SIZE(n^k)$can be approximated by formulas ... more >>> TR09-122 | 23rd November 2009 Vikraman Arvind, Srikanth Srinivasan #### Circuit Lower Bounds, Help Functions, and the Remote Point Problem We investigate the power of Algebraic Branching Programs (ABPs) augmented with help polynomials, and constant-depth Boolean circuits augmented with help functions. We relate the problem of proving explicit lower bounds in both these models to the Remote Point Problem (introduced by Alon, Panigrahy, and Yekhanin (RANDOM '09)). More precisely, proving ... more >>> TR99-045 | 16th November 1999 Valentine Kabanets, Jin-Yi Cai #### Circuit Minimization Problem We study the complexity of the circuit minimization problem: given the truth table of a Boolean function f and a parameter s, decide whether f can be realized by a Boolean circuit of size at most s. We argue why this problem is unlikely to be in P (or ... more >>> TR16-022 | 22nd February 2016 Alexander Golovnev, Alexander Kulikov, Alexander Smal, Suguru Tamaki #### Circuit size lower bounds and #SAT upper bounds through a general framework Revisions: 2 Most of the known lower bounds for binary Boolean circuits with unrestricted depth are proved by the gate elimination method. The most efficient known algorithms for the #SAT problem on binary Boolean circuits use similar case analyses to the ones in gate elimination. Chen and Kabanets recently showed that the ... more >>> TR02-066 | 24th October 2002 Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V Vinay #### Circuits on Cylinders We consider the computational power of constant width polynomial size cylindrical circuits and nondeterministic branching programs. We show that every function computed by a Pi2 o MOD o AC0 circuit can also be computed by a constant width polynomial size cylindrical nondeterministic branching program (or cylindrical circuit) and that ... more >>> TR22-050 | 12th April 2022 Klim Efremenko, Bernhard Haeupler, Yael Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh Saxena #### Circuits Resilient to Short-Circuit Errors Given a Boolean circuit$C$, we wish to convert it to a circuit$C'$that computes the same function as$C$even if some of its gates suffer from adversarial short circuit errors, i.e., their output is replaced by the value of one of their inputs [KLM97]. Can we ... more >>> TR14-020 | 18th February 2014 Pavel Hrubes, Anup Rao #### Circuits with Medium Fan-In Revisions: 1 We consider boolean circuits in which every gate may compute an arbitrary boolean function of$k$other gates, for a parameter$k$. We give an explicit function$f:\bits^n \rightarrow \bits$that requires at least$\Omega(\log^2 n)$non-input gates when$k = 2n/3$. When the circuit is restricted to being depth ... more >>> TR12-145 | 31st October 2012 Cenny Wenner #### Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width at Least Four Håstad established that any predicate$P \subseteq \{0,1\}^m$containing parity of width at least three is approximation resistant for almost satisfiable instances. However, in comparison to for example the approximation hardness of Max-3SAT, the result only holds for almost satisfiable instances. This limitation was addressed by O'Donnell, Wu, and Huang ... more >>> TR22-036 | 10th March 2022 Agnes Schleitzer, Olaf Beyersdorff #### Classes of Hard Formulas for QBF Resolution Revisions: 1 To date, we know only a few handcrafted quantified Boolean formulas (QBFs) that are hard for central QBF resolution systems such as Q and QU, and only one specific QBF family to separate Q and QU. Here we provide a general method to construct hard formulas for Q and ... more >>> TR12-023 | 19th March 2012 Sophie Laplante, Virginie Lerays, Jérémie Roland #### Classical and quantum partition bound and detector inefficiency In communication complexity, two players each have an input and they wish to compute some function of the joint inputs. This has been the object of much study and a wide variety of lower bound methods have been introduced to address the problem of showing lower bounds on communication. Recently, ... more >>> TR14-136 | 17th October 2014 Viliam Geffert, Abuzer Yakaryilmaz #### Classical Automata on Promise Problems Promise problems were mainly studied in quantum automata theory. Here we focus on state complexity of classical automata for promise problems. First, it was known that there is a family of unary promise problems solvable by quantum automata by using a single qubit, but the number of states required by ... more >>> TR07-058 | 9th June 2007 Dmytro Gavinsky #### Classical Interaction Cannot Replace a Quantum Message Revisions: 1 We demonstrate a two-player communication problem that can be solved in the one-way quantum model by a 0-error protocol of cost O(log n) but requires exponentially more communication in the classical interactive (two-way) model. more >>> TR02-062 | 19th November 2002 Andrew Chi-Chih Yao #### Classical Physics and the Church-Turing Thesis Would physical laws permit the construction of computing machines that are capable of solving some problems much faster than the standard computational model? Recent evidence suggests that this might be the case in the quantum world. But the question is of great interest even in the realm of classical physics. ... more >>> TR05-016 | 13th January 2005 Tomas Feder, Daniel Ford #### Classification of Bipartite Boolean Constraint Satisfaction through Delta-Matroid Intersection Matroid intersection has a known polynomial time algorithm using an oracle. We generalize this result to delta-matroids that do not have equality as a restriction, and give a polynomial time algorithm for delta-matroid intersection on delta-matroids without equality using an oracle. We note that when equality is present, delta-matroid intersection more >>> TR21-107 | 20th July 2021 igor razgon #### Classification of OBDD size for monotone 2-CNFs We introduce a new graph parameter called linear upper maximum induced matching width \textsc{lu-mim width}, denoted for a graph$G$by$lu(G)$. We prove that the smallest size of the \textsc{obdd} for$\varphi$, the monotone 2-\textsc{cnf} corresponding to$G$, is sandwiched between$2^{lu(G)}$and$n^{O(lu(G))}$. The upper bound ... more >>> TR01-082 | 24th September 2001 Tsuyoshi Morioka #### Classification of Search Problems and Their Definability in Bounded Arithmetic We present a new framework for the study of search problems and their definability in bounded arithmetic. We identify two notions of complexity of search problems: verification complexity and computational complexity. Notions of exact solvability and exact reducibility are developed, and exact$\Sigma^b_i$-definability of search problems in bounded arithmetic ... more >>> TR21-011 | 13th February 2021 Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy #### Classification of the streaming approximability of Boolean CSPs Revisions: 4 , Comments: 1 A Boolean constraint satisfaction problem (CSP), Max-CSP$(f)$, is a maximization problem specified by a constraint$f:\{-1,1\}^k\to\{0,1\}$. An instance of the problem consists of$m$constraint applications on$n$Boolean variables, where each constraint application applies the constraint to$k$literals chosen from the$n$variables and their negations. The goal ... more >>> TR05-102 | 13th September 2005 Evgeny Dantsin, Edward Hirsch, Alexander Wolpert #### Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms We give a deterministic algorithm for testing satisfiability of formulas in conjunctive normal form with no restriction on clause length. Its upper bound on the worst-case running time matches the best known upper bound for randomized satisfiability-testing algorithms [Dantsin and Wolpert, SAT 2005]. In comparison with the randomized algorithm in ... more >>> TR12-039 | 17th April 2012 Stasys Jukna #### Clique Problem, Cutting Plane Proofs, and Communication Complexity Motivated by its relation to the length of cutting plane proofs for the Maximum Biclique problem, here we consider the following communication game on a given graph G, known to both players. Let K be the maximal number of vertices in a complete bipartite subgraph of G (which is not ... more >>> TR08-092 | 26th August 2008 Scott Aaronson, John Watrous #### Closed Timelike Curves Make Quantum and Classical Computing Equivalent While closed timelike curves (CTCs) are not known to exist, studying their consequences has led to nontrivial insights in general relativity, quantum information, and other areas. In this paper we show that if CTCs existed, then quantum computers would be no more powerful than classical computers: both would have the ... more >>> TR19-037 | 5th March 2019 Chi-Ning Chou, Mrinal Kumar, Noam Solomon #### Closure of VP under taking factors: a short and simple proof Revisions: 1 In this note, we give a short, simple and almost completely self contained proof of a classical result of Kaltofen [Kal86, Kal87, Kal89] which shows that if an n variate degree$d$polynomial f can be computed by an arithmetic circuit of size s, then each of its factors can ... more >>> TR95-035 | 30th June 1995 Richard Beigel #### Closure Properties of GapP and #P We classify the univariate functions that are relativizable closure properties of GapP, solving a problem posed by Hertrampf, Vollmer, and Wagner (Structures '95). We also give a simple proof of their classification of univariate functions that are relativizable closure properties of #P. more >>> TR06-160 | 17th December 2006 Tomas Feder, Phokion G. Kolaitis #### Closures and dichotomies for quantified constraints Quantified constraint satisfaction is the generalization of constraint satisfaction that allows for both universal and existential quantifiers over constrained variables, instead of just existential quantifiers. We study quantified constraint satisfaction problems${\rm CSP}(Q,S)$, where$Q$denotes a pattern of quantifier alternation ending in exists or the set of all possible more >>> TR99-035 | 6th July 1999 Leonard Schulman #### Clustering for Edge-Cost Minimization We address the problem of partitioning a set of$n$points into clusters, so as to minimize the sum, over all intracluster pairs of points, of the cost associated with each pair. We obtain a randomized approximation algorithm for this problem, for the cost functions$\ell_2^2,\ell_1$and$\ell_2$, as ... more >>> TR13-031 | 22nd February 2013 Irit Dinur, Elazar Goldenberg #### Clustering in the Boolean Hypercube in a List Decoding Regime Revisions: 2 We consider the following clustering with outliers problem: Given a set of points$X \subset \{-1,1\}^n$, such that there is some point$z \in \{-1,1\}^n$for which at least$\delta$of the points are$\epsilon$-correlated with$z$, find$z$. We call such a point$z$a$(\delta,\epsilon)$-center of X. In ... more >>> TR21-112 | 30th July 2021 Vikraman Arvind, Venkatesan Guruswami #### CNF Satisfiability in a Subspace and Related Problems We introduce the problem of finding a satisfying assignment to a CNF formula that must further belong to a prescribed input subspace. Equivalent formulations of the problem include finding a point outside a union of subspaces (the Union-of-Subspace Avoidance (USA) problem), and finding a common zero of a system of ... more >>> TR08-060 | 10th April 2008 James R. Lee, Prasad Raghavendra #### Coarse Differentiation and Multi-flows in Planar Graphs We show that the multi-commodity max-flow/min-cut gap for series-parallel graphs can be as bad as 2, matching a recent upper bound by Chakrabarti.et.al for this class, and resolving one side of a conjecture of Gupta, Newman, Rabinovich, and Sinclair. This also improves the largest known gap for planar graphs ... more >>> TR10-077 | 26th April 2010 Venkatesan Guruswami, Adam Smith #### Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate In this paper, we consider coding schemes for computationally bounded channels, which can introduce an arbitrary set of errors as long as (a) the fraction of errors is bounded with high probability by a parameter p and (b) the process which adds the errors can be described by a sufficiently ... more >>> TR20-156 | 22nd October 2020 Sankeerth Rao Karingula, Shachar Lovett #### Codes over integers, and the singularity of random matrices with large entries Revisions: 1 The prototypical construction of error correcting codes is based on linear codes over finite fields. In this work, we make first steps in the study of codes defined over integers. We focus on Maximum Distance Separable (MDS) codes, and show that MDS codes with linear rate and distance can be ... more >>> TR15-106 | 22nd June 2015 Itay Berman, Iftach Haitner, Aris Tentes #### Coin Flipping of Any Constant Bias Implies One-Way Functions Revisions: 1 We show that the existence of a coin-flipping protocol safe against any non-trivial constant bias (e.g.,$.499$) implies the existence of one-way functions. This improves upon a recent result of Haitner and Omri [FOCS '11], who proved this implication for protocols with bias$\frac{\sqrt2 -1}2 - o(1) \approx .207$. Unlike ... more >>> TR19-087 | 10th June 2019 Rohit Agrawal #### Coin Theorems and the Fourier Expansion Revisions: 1 In this note we compare two measures of the complexity of a class$\mathcal F$of Boolean functions studied in (unconditional) pseudorandomness:$\mathcal F$'s ability to distinguish between biased and uniform coins (the coin problem), and the norms of the different levels of the Fourier expansion of functions in$\mathcal ... more >>>

TR17-160 | 29th October 2017
Eli Ben-Sasson, Eden Saig

#### Collaborative Discovery: A study of Guru-follower dynamics

Revisions: 1

Gurus are individuals who claim to possess mental powers of insight and prediction that far surpass those of the average person; they compete over followers, offering them insight in return for continued devotion. Followers wish to harness a (true) Guru’s predictive power but (i) have limited attention span and (ii) ... more >>>

TR13-131 | 17th September 2013
Nikhil Balaji, Samir Datta

#### Collapsing Exact Arithmetic Hierarchies

Revisions: 1

We provide a uniform framework for proving the collapse of the hierarchy, $NC^1(\mathcal{C})$
for an exact arithmetic class $\mathcal{C}$ of polynomial degree. These hierarchies collapses all the way down to the third level of the ${AC}^0$-hierarchy, ${AC^0_3}(\mathcal{C})$. Our main collapsing exhibits are the classes $\mathcal{C} \in \{{C}_={NC^1}, {C}_={L}, {C}_={SAC^1}, {C}_={P}\}.$
more >>>

TR16-178 | 11th November 2016
Ilias Diakonikolas, Themis Gouleakis, John Peebles, Eric Price

#### Collision-based Testers are Optimal for Uniformity and Closeness

We study the fundamental problems of (i) uniformity testing of a discrete distribution,
and (ii) closeness testing between two discrete distributions with bounded $\ell_2$-norm.
These problems have been extensively studied in distribution testing
and sample-optimal estimators are known for them~\cite{Paninski:08, CDVV14, VV14, DKN:15}.

In this work, we show ... more >>>

TR96-042 | 26th July 1996
Oded Goldreich, Shai Halevi

#### Collision-Free Hashing from Lattice Problems

Recently Ajtai described a construction of one-way functions whose
security is equivalent to the difficulty of some well known approximation
problems in lattices. We show that essentially the same
construction can also be used to obtain collision-free hashing.

more >>>

TR22-017 | 15th February 2022
Ron D. Rothblum, Prashant Nalini Vasudevan

#### Collision-Resistance from Multi-Collision-Resistance

Revisions: 2

Collision-resistant hash functions (CRH) are a fundamental and ubiquitous cryptographic primitive. Several recent works have studied a relaxation of CRH called t-way multi-collision-resistant hash functions (t-MCRH). These are families of functions for which it is computationally hard to find a t-way collision, even though such collisions are abundant (and even ... more >>>

TR94-009 | 12th December 1994
Noga Alon, Raphael Yuster, Uri Zwick

#### Color-coding

We describe a novel randomized method, the method of
{\em color-coding\/} for finding simple paths and cycles of a specified
length $k$, and other small subgraphs, within a given graph $G=(V,E)$.
The randomized algorithms obtained using this method can be
derandomized using families of {\em perfect hash functions\/}. ... more >>>

TR09-093 | 8th October 2009
Vikraman Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda

#### Colored Hypergraph Isomorphism is Fixed Parameter Tractable

Revisions: 1

We describe a fixed parameter tractable (fpt) algorithm for Colored Hypergraph Isomorphism} which has running time $b!2^{O(b)}N^{O(1)}$, where the parameter $b$ is the maximum size of the color classes of the given hypergraphs and $N$ is the input size. We also describe fpt algorithms for certain permutation group problems that ... more >>>

TR04-070 | 22nd June 2004
Leonid Gurvits

#### Combinatorial and algorithmic aspects of hyperbolic polynomials

Let $p(x_1,...,x_n) =\sum_{ (r_1,...,r_n) \in I_{n,n} } a_{(r_1,...,r_n) } \prod_{1 \leq i \leq n} x_{i}^{r_{i}}$
be homogeneous polynomial of degree $n$ in $n$ real variables with integer nonnegative coefficients.
The support of such polynomial $p(x_1,...,x_n)$
is defined as $supp(p) = \{(r_1,...,r_n) \in I_{n,n} : a_{(r_1,...,r_n)} \neq 0 ... more >>> TR07-115 | 19th November 2007 Or Meir #### Combinatorial Construction of Locally Testable Codes Revisions: 1 An error correcting code is said to be locally testable if there is a test that checks whether a given string is a codeword, or rather far from the code, by reading only a constant number of symbols of the string. Locally Testable Codes (LTCs) were first systematically studied by ... more >>> TR10-184 | 19th November 2010 Manjish Pal #### Combinatorial Geometry of Graph Partitioning - I The {\sc$c$-Balanced Separator} problem is a graph-partitioning problem in which given a graph$G$, one aims to find a cut of minimum size such that both the sides of the cut have at least$cn$vertices. In this paper, we present new directions of progress in the {\sc$c$-Balanced ... more >>> TR00-026 | 11th April 2000 Andrei Romashchenko, Alexander Shen, Nikolay Vereshchagin #### Combinatorial Interpretation of Kolmogorov Complexity The very first Kolmogorov's paper on algorithmic information theory was entitled Three approaches to the definition of the quantity of information'. These three approaches were called combinatorial, probabilistic and algorithmic. Trying to establish formal connections between combinatorial and algorithmic approaches, we prove that any ... more >>> TR12-017 | 1st March 2012 Venkatesan Guruswami, Srivatsan Narayanan #### Combinatorial limitations of a strong form of list decoding Revisions: 1 We prove the following results concerning the combinatorics of list decoding, motivated by the exponential gap between the known upper bound (of$O(1/\gamma)$) and lower bound (of$\Omega_p(\log (1/\gamma))$) for the list-size needed to decode up to radius$p$with rate$\gamma$away from capacity, i.e.,$1-h(p)-\gamma$(here$p\in (0,1/2)$... more >>> TR15-007 | 8th January 2015 Jonah Brown-Cohen, Prasad Raghavendra #### Combinatorial Optimization Algorithms via Polymorphisms An elegant characterization of the complexity of constraint satisfaction problems has emerged in the form of the the algebraic dichotomy conjecture of [BKJ00]. Roughly speaking, the characterization asserts that a CSP$\Lambda$is tractable if and only if there exist certain non-trivial operations known as polymorphisms to combine solutions to ... more >>> TR11-104 | 3rd August 2011 Or Meir #### Combinatorial PCPs with efficient verifiers Revisions: 3 The PCP theorem asserts the existence of proofs that can be verified by a verifier that reads only a very small part of the proof. The theorem was originally proved by Arora and Safra (J. ACM 45(1)) and Arora et al. (J. ACM 45(3)) using sophisticated algebraic tools. More than ... more >>> TR13-134 | 25th September 2013 Or Meir #### Combinatorial PCPs with Short Proofs The PCP theorem (Arora et. al., J. ACM 45(1,3)) asserts the existence of proofs that can be verified by reading a very small part of the proof. Since the discovery of the theorem, there has been a considerable work on improving the theorem in terms of the length of the ... more >>> TR97-056 | 1st December 1997 Oded Goldreich #### Combinatorial Property Testing (a survey). Comments: 1 We consider the question of determining whether a given object has a predetermined property or is far'' from any object having the property. Specifically, objects are modeled by functions, and distance between functions is measured as the fraction of the domain on which the functions differ. We ... more >>> TR98-041 | 27th July 1998 Stasys Jukna #### Combinatorics of Monotone Computations We consider a general model of monotone circuits, which we call d-local. In these circuits we allow as gates: (i) arbitrary monotone Boolean functions whose minterms or maxterms (or both) have length at most <i>d</i>, and (ii) arbitrary real-valued non-decreasing functions on ... more >>> TR18-059 | 6th April 2018 Joshua Brakensiek, Venkatesan Guruswami #### Combining LPs and Ring Equations via Structured Polymorphisms Revisions: 1 Promise CSPs are a relaxation of constraint satisfaction problems where the goal is to find an assignment satisfying a relaxed version of the constraints. Several well known problems can be cast as promise CSPs including approximate graph and hypergraph coloring, discrepancy minimization, and interesting variants of satisfiability. Similar to CSPs, ... more >>> TR09-003 | 6th January 2009 Alex Hertel, Alasdair Urquhart #### Comments on ECCC Report TR06-133: The Resolution Width Problem is EXPTIME-Complete We discovered a serious error in one of our previous submissions to ECCC and wish to make sure that this mistake is publicly known. The main argument of the report TR06-133 is in error. The paper claims to prove the result of the title by reduction from the (Exists,k)-pebble game, ... more >>> TR22-140 | 10th October 2022 Sam Gunn, Nathan Ju, Fermi Ma, Mark Zhandry #### Commitments to Quantum States Revisions: 1 What does it mean to commit to a quantum state? In this work, we propose a simple answer: a commitment to quantum messages is binding if, after the commit phase, the committed state is hidden from the sender's view. We accompany this new definition with several instantiations. We build the ... more >>> TR13-056 | 30th March 2013 Gábor Braun, Sebastian Pokutta #### Common information and unique disjointness Revisions: 5 We provide a new framework for establishing strong lower bounds on the nonnega- tive rank of matrices by means of common information, a notion previously introduced in Wyner [1975]. Common information is a natural lower bound for the nonnegative rank of a matrix and by combining it with Hellinger distance ... more >>> TR15-156 | 21st September 2015 Tim Roughgarden #### Communication Complexity (for Algorithm Designers) This document collects the lecture notes from my course Communication Complexity (for Algorithm Designers),'' taught at Stanford in the winter quarter of 2015. The two primary goals of the course are: 1. Learn several canonical problems that have proved the most useful for proving lower bounds (Disjointness, Index, Gap-Hamming, etc.). ... more >>> TR01-062 | 9th September 2001 Moni Naor, Kobbi Nissim #### Communication Complexity and Secure Function Evaluation A secure function evaluation protocol allows two parties to jointly compute a function$f(x,y)$of their inputs in a manner not leaking more information than necessary. A major result in this field is: any function$f$that can be computed using polynomial resources can be computed securely using polynomial resources'' ... more >>> TR22-096 | 8th July 2022 Mika Göös, Siddhartha Jain #### Communication Complexity of Collision The Collision problem is to decide whether a given list of numbers$(x_1,\ldots,x_n)\in[n]^n$is$1$-to-$1$or$2$-to-$1$when promised one of them is the case. We show an$n^{\Omega(1)}$randomised communication lower bound for the natural two-party version of Collision where Alice holds the first half of the bits of ... more >>> TR17-061 | 3rd April 2017 Anat Ganor, Karthik C. S. #### Communication Complexity of Correlated Equilibrium in Two-Player Games We show a communication complexity lower bound for finding a correlated equilibrium of a two-player game. More precisely, we define a two-player$N \times N$game called the 2-cycle game and show that the randomized communication complexity of finding a 1/poly($N$)-approximate correlated equilibrium of the 2-cycle game is$\Omega(N)$. For ... more >>> TR15-087 | 30th May 2015 Badih Ghazi, Pritish Kamath, Madhu Sudan #### Communication Complexity of Permutation-Invariant Functions Motivated by the quest for a broader understanding of communication complexity of simple functions, we introduce the class of ''permutation-invariant'' functions. A partial function$f:\{0,1\}^n \times \{0,1\}^n\to \{0,1,?\}$is permutation-invariant if for every bijection$\pi:\{1,\ldots,n\} \to \{1,\ldots,n\}$and every$\mathbf{x}, \mathbf{y} \in \{0,1\}^n$, it is the case that$f(\mathbf{x}, \mathbf{y}) ... more >>>

TR14-055 | 17th April 2014
Mika Göös, Thomas Watson

#### Communication Complexity of Set-Disjointness for All Probabilities

Revisions: 1

We study set-disjointness in a generalized model of randomized two-party communication where the probability of acceptance must be at least alpha(n) on yes-inputs and at most beta(n) on no-inputs, for some functions alpha(n)>beta(n). Our main result is a complete characterization of the private-coin communication complexity of set-disjointness for all functions ... more >>>

TR16-170 | 3rd November 2016
Thomas Watson

#### Communication Complexity of Statistical Distance

Revisions: 1

We prove nearly matching upper and lower bounds on the randomized communication complexity of the following problem: Alice and Bob are each given a probability distribution over $n$ elements, and they wish to estimate within $\pm\epsilon$ the statistical (total variation) distance between their distributions. For some range of parameters, there ... more >>>

TR07-072 | 2nd July 2007
Alexander A. Sherstov

#### Communication Complexity under Product and Nonproduct Distributions

We solve an open problem of Kushilevitz and Nisan
(1997) in communication complexity. Let $R_{eps}(f)$
and $D^{mu}_{eps}(f)$ denote the randomized and
$mu$-distributional communication complexities of
f, respectively ($eps$ a small constant). Yao's
well-known Minimax Principle states that
R_{eps}(f) = max_{mu} { D^{mu}_{eps}(f) }.
Kushilevitz and Nisan (1997) ask whether ... more >>>

TR20-054 | 22nd April 2020
Marshall Ball, Oded Goldreich, Tal Malkin

#### Communication Complexity with Defective Randomness

Revisions: 3

Starting with the two standard model of randomized communication complexity, we study the communication complexity of functions when the protocol has access to a defective source of randomness.
Specifically, we consider both the public-randomness and private-randomness cases, while replacing the commonly postulated perfect randomness with distributions over $\ell$ bit ... more >>>

TR16-148 | 23rd September 2016
Thomas Watson

#### Communication Complexity with Small Advantage

Revisions: 1

We study problems in randomized communication complexity when the protocol is only required to attain some small advantage over purely random guessing, i.e., it produces the correct output with probability at least $\epsilon$ greater than one over the codomain size of the function. Previously, Braverman and Moitra (STOC 2013) showed ... more >>>

TR13-084 | 8th June 2013
Shachar Lovett

#### Communication is bounded by root of rank

Revisions: 1

We prove that any total boolean function of rank $r$ can be computed by a deterministic communication protocol of complexity $O(\sqrt{r} \cdot \log(r))$. Equivalently, any graph whose adjacency matrix has rank $r$ has chromatic number at most $2^{O(\sqrt{r} \cdot \log(r))}$. This gives a nearly quadratic improvement in the dependence on ... more >>>

TR13-005 | 2nd January 2013
Alexander A. Sherstov

#### Communication Lower Bounds Using Directional Derivatives

We prove that the set disjointness problem has randomized communication complexity
$\Omega(\sqrt{n}/2^{k}k)$ in the number-on-the-forehead model with $k$ parties, a quadratic improvement
on the previous bound $\Omega(\sqrt{n}/2^{k})^{1/2}$. Our result remains valid for quantum
protocols, where it is essentially tight. Proving it was an open problem since 1997, ... more >>>

TR08-057 | 14th May 2008
Alexander A. Sherstov

#### Communication Lower Bounds Using Dual Polynomials

Representations of Boolean functions by real polynomials
play an important role in complexity theory. Typically,
one is interested in the least degree of a polynomial
p(x_1,...,x_n) that approximates or sign-represents
surveys a new and growing body of work in communication
complexity that centers ... more >>>

TR15-064 | 19th April 2015
Ilan Komargodski, Pravesh Kothari, Madhu Sudan

#### Communication with Contextual Uncertainty

Revisions: 1

We introduce a simple model illustrating the role of context in communication and the challenge posed by uncertainty of knowledge of context. We consider a variant of distributional communication complexity where Alice gets some information $x$ and Bob gets $y$, where $(x,y)$ is drawn from a known distribution, and Bob ... more >>>

TR14-153 | 14th November 2014
Clement Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan

#### Communication with Imperfectly Shared Randomness

Revisions: 2

The communication complexity of many fundamental problems reduces greatly
when the communicating parties share randomness that is independent of the
inputs to the communication task. Natural communication processes (say between
humans) however often involve large amounts of shared correlations among the
communicating players, but rarely allow for perfect sharing of ... more >>>

TR18-150 | 27th August 2018

#### Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation

We study the role of interaction in the Common Randomness Generation (CRG) and Secret Key Generation (SKG) problems. In the CRG problem, two players, Alice and Bob, respectively get samples $X_1,X_2,\dots$ and $Y_1,Y_2,\dots$ with the pairs $(X_1,Y_1)$, $(X_2, Y_2)$, $\dots$ being drawn independently from some known probability distribution $\mu$. They ... more >>>

TR15-035 | 22nd February 2015
Sunil K S, Balagopal Komarath, Jayalal Sarma

#### Comparator Circuits over Finite Bounded Posets

Revisions: 1

Comparator circuit model was originally introduced by Mayr and Subramanian (1992) to capture problems which are not known to be P-complete but still not known to admit efficient parallel algorithms. The class CC is the complexity class of problems many-one logspace reducible to the Comparator Circuit Value Problem We know ... more >>>

TR20-171 | 12th November 2020
Russell Impagliazzo, Sam McGuire

#### Comparing computational entropies below majority (or: When is the dense model theorem false?)

Computational pseudorandomness studies the extent to which a random variable $\bf{Z}$ looks like the uniform distribution according to a class of tests $\cal{F}$. Computational entropy generalizes computational pseudorandomness by studying the extent which a random variable looks like a \emph{high entropy} distribution. There are different formal definitions of computational entropy ... more >>>

TR98-063 | 4th November 1998

#### Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK

We consider the following (promise) problem, denoted ED (for Entropy
Difference): The input is a pairs of circuits, and YES instances (resp.,
NO instances) are such pairs in which the first (resp., second) circuit
generates a distribution with noticeably higher entropy.

On one hand we show that any language ... more >>>

TR06-039 | 28th February 2006
John Hitchcock, A. Pavan

#### Comparing Reductions to NP-Complete Sets

Under the assumption that NP does not have p-measure 0, we
investigate reductions to NP-complete sets and prove the following:

reductions: there is a problem that is Turing-complete for NP but
not truth-table-complete.

- Strong nondeterministic reductions are more powerful ... more >>>

TR14-143 | 3rd November 2014
Ronald de Haan, Stefan Szeider

#### Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy

We present a list of parameterized problems together with a complexity classification of whether they allow a fixed-parameter tractable reduction to SAT or not. These parameterized problems are based on problems whose complexity lies at the second level of the Polynomial Hierarchy or higher. The list will be updated as ... more >>>

TR11-122 | 14th September 2011
Gillat Kol, Ran Raz

#### Competing Provers Protocols for Circuit Evaluation

Let $C$ be a (fan-in $2$) Boolean circuit of size $s$ and depth $d$, and let $x$ be an input for $C$. Assume that a verifier that knows $C$ but doesn't know $x$ can access the low degree extension of $x$ at one random point. Two competing provers try to ... more >>>

TR17-136 | 10th September 2017
Salman Beigi, Andrej Bogdanov, Omid Etesami, Siyao Guo

#### Complete Classi fication of Generalized Santha-Vazirani Sources

Let $\mathcal{F}$ be a finite alphabet and $\mathcal{D}$ be a finite set of distributions over $\mathcal{F}$. A Generalized Santha-Vazirani (GSV) source of type $(\mathcal{F}, \mathcal{D})$, introduced by Beigi, Etesami and Gohari (ICALP 2015, SICOMP 2017), is a random sequence $(F_1, \dots, F_n)$ in $\mathcal{F}^n$, where $F_i$ is a sample from ... more >>>

TR16-171 | 3rd November 2016
Daniel Minahan, Ilya Volkovich

#### Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas

In this paper we study the identity testing problem of \emph{arithmetic read-once formulas} (ROF) and some related models. A read-once formula is formula (a circuit whose underlying graph is a tree) in which the
operations are $\set{+,\times}$ and such that every input variable labels at most one leaf. We obtain ... more >>>

TR06-036 | 7th February 2006
Tobias Riege, Jörg Rothe

#### Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems

Revisions: 1

This paper surveys some of the work that was inspired by Wagner's general technique to prove completeness in the levels of the boolean hierarchy over NP and some related results. In particular, we show that it is DP-complete to decide whether or not a given graph can be colored with ... more >>>

TR03-060 | 7th September 2003
Danny Harnik, Moni Naor, Omer Reingold, Alon Rosen

#### Completeness in Two-Party Secure Computation - A Computational View

A Secure Function Evaluation (SFE) of a two-variable function f(.,.) is a protocol that allows two parties with inputs x and y to evaluate
f(x,y) in a manner where neither party learns more than is necessary". A rich body of work deals with the study of completeness for secure ... more >>>

TR97-057 | 3rd November 1997
Petr Savicky

#### Complexity and Probability of some Boolean Formulas

For any Boolean function $f$ let $L(f)$ be its formula size
complexity in the basis $\{\land,\oplus,1\}$. For every $n$ and
every $k\le n/2$, we describe a probabilistic distribution
on formulas in the basis $\{\land,\oplus,1\}$ in some given set of
$n$ variables and of the ... more >>>

TR16-039 | 15th March 2016
Adam Bouland, Laura Mancinska, Xue Zhang

#### Complexity Classification of Two-Qubit Commuting Hamiltonians

We classify two-qubit commuting Hamiltonians in terms of their computational complexity. Suppose one has a two-qubit commuting Hamiltonian $H$ which one can apply to any pair of qubits, starting in a computational basis state. We prove a dichotomy theorem: either this model is efficiently classically simulable or it allows one ... more >>>

TR11-093 | 8th June 2011
Pinyan Lu

#### Complexity Dichotomies of Counting Problems

In order to study the complexity of counting problems, several interesting frameworks have been proposed, such as Constraint Satisfaction Problems (#CSP) and Graph Homomorphisms. Recently, we proposed and explored a novel alternative framework, called Holant Problems. It is a refinement with a more explicit role for constraint functions. Both graph ... more >>>

TR97-046 | 3rd October 1997
Alexander Barg

#### Complexity Issues in Coding Theory

This is a research-expository paper. It deals with
complexity issues in the theory of linear block codes. The main
emphasis is on the theoretical performance limits of the
best known codes. Therefore, the main subject of the paper are
families of asymptotically good codes, i.e., codes whose rate and
relative ... more >>>

TR11-138 | 24th October 2011
Guy Moshkovitz

#### Complexity Lower Bounds through Balanced Graph Properties

In this paper we present a combinatorial approach for proving complexity lower bounds. We mainly focus on the following instantiation of it. Consider a pair of properties of $m$-edge regular hypergraphs. Suppose they are indistinguishable'' with respect to hypergraphs with $m-t$ edges, in the sense that every such hypergraph has ... more >>>

TR13-125 | 11th September 2013
Venkatesan Guruswami, Euiwoong Lee

#### Complexity of approximating CSP with Balance / Hard Constraints

We study two natural extensions of Constraint Satisfaction Problems (CSPs). {\em Balance}-Max-CSP requires that in any feasible assignment each element in the domain is used an equal number of times. An instance of {\em Hard}-Max-CSP consists of {\em soft constraints} and {\em hard constraints}, and the goal is to maximize ... more >>>

TR16-031 | 7th March 2016
Titus Dose

#### Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers

Revisions: 5

We study the computational complexity of constraint satisfaction problems that are based on integer expressions and algebraic circuits. On input of a finite set of variables and a finite set of constraints the question is whether the variables can be mapped onto finite subsets of natural numbers (resp., finite intervals ... more >>>

TR08-044 | 2nd April 2008
Miki Hermann, Reinhard Pichler

#### Complexity of Counting the Optimal Solutions

Following the approach of Hemaspaandra and Vollmer, we can define
counting complexity classes #.C for any complexity class C of decision
problems. In particular, the classes #.Pi_{k}P with k >= 1
corresponding to all levels of the polynomial hierarchy have thus been
studied. However, for a large variety of counting ... more >>>

TR15-174 | 18th October 2015
Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

#### Complexity of distributions and average-case hardness

We address a natural question in average-case complexity: does there exist a language $L$ such that for all easy distributions $D$ the distributional problem $(L, D)$ is easy on the average while there exists some more hard distribution $D'$ such that $(L, D')$ is hard on the average? We consider ... more >>>

TR04-035 | 10th April 2004
Scott Contini, Ernie Croot, Igor E. Shparlinski

#### Complexity of Inverting the Euler Function

We present an algorithm to invert the Euler function $\varphi(m)$. The algorithm, for a given integer $n\ge 1$, in polynomial time on average'', finds theset $\Psi(n)$ of all solutions $m$ to the equation $\varphi(m) =n$. In fact, in the worst case the set $\Psi(n)$ is exponentially large and cannot be ... more >>>

TR19-002 | 31st December 2018
Alexander Kulikov, Ivan Mikhailin, Andrey Mokhov, Vladimir Podolskii

#### Complexity of Linear Operators

Let $A \in \{0,1\}^{n \times n}$ be a matrix with $z$ zeroes and $u$ ones and $x$ be an $n$-dimensional vector of formal variables over a semigroup $(S, \circ)$. How many semigroup operations are required to compute the linear operator $Ax$?

As we observe in this paper, this problem contains ... more >>>

TR15-018 | 31st January 2015
Eric Allender, Ian Mertz

#### Complexity of Regular Functions

Revisions: 1

We give complexity bounds for various classes of functions computed by cost register automata.

more >>>

TR01-103 | 14th December 2001
Dima Grigoriev, Edward Hirsch, Dmitrii V. Pasechnik

#### Complexity of semi-algebraic proofs

Revisions: 3

It is a known approach to translate propositional formulas into
systems of polynomial inequalities and to consider proof systems
for the latter ones. The well-studied proof systems of this kind
are the Cutting Planes proof system (CP) utilizing linear
inequalities and the Lovasz-Schrijver calculi (LS) utilizing

TR02-068 | 10th December 2002
Tobias Riege, Jörg Rothe

#### Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem

Revisions: 2

We prove that the exact versions of the domatic number problem are complete
for the levels of the boolean hierarchy over NP. The domatic number
problem, which arises in the area of computer networks, is the problem of
partitioning a given graph into a maximum number ... more >>>

TR18-039 | 23rd February 2018
Md Lutfar Rahman, Thomas Watson

#### Complexity of Unordered CNF Games

Revisions: 1

The classic TQBF problem is to determine who has a winning strategy in a game played on a given CNF formula, where the two players alternate turns picking truth values for the variables in a given order, and the winner is determined by whether the CNF gets satisfied. We study ... more >>>

TR94-013 | 12th December 1994
Pavel Pudlak

#### Complexity Theory and Genetics

We introduce a population genetics model in which the operators
are effectively computable -- computable in polynomial time on
Probabilistic Turing Machines. We shall show that in this model
a population can encode easily large amount of information
from enviroment into genetic code. Then it can process the
information as ... more >>>

TR18-001 | 2nd January 2018
Tim Roughgarden

#### Complexity Theory, Game Theory, and Economics

Revisions: 2

This document collects the lecture notes from my mini-course "Complexity Theory, Game Theory, and Economics," taught at the Bellairs Research Institute of McGill University, Holetown, Barbados, February 19-23, 2017, as the 29th McGill Invitational Workshop on Computational Complexity.

The goal of this mini-course is twofold: (i) to explain how complexity ... more >>>

TR16-200 | 18th December 2016
Scott Aaronson, Lijie Chen

#### Complexity-Theoretic Foundations of Quantum Supremacy Experiments

Revisions: 1

In the near future, there will likely be special-purpose quantum computers with 40-50 high-quality qubits. This paper lays general theoretical foundations for how to use such devices to demonstrate "quantum supremacy": that is, a clear quantum speedup for some task, motivated by the goal of overturning the Extended Church-Turing Thesis ... more >>>

TR17-014 | 23rd January 2017

#### Composition and Simulation Theorems via Pseudo-random Properties

We prove a randomized communication-complexity lower bound for a composed OrderedSearch $\circ$ IP — by lifting the randomized query-complexity lower-bound of OrderedSearch to the communication-complexity setting. We do this by extending ideas from a paper of Raz and Wigderson. We think that the techniques we develop will be useful in ... more >>>

TR09-042 | 5th May 2009

#### Composition of low-error 2-query PCPs using decodable PCPs

The main result of this paper is a simple, yet generic, composition theorem for low error two-query probabilistically checkable proofs (PCPs). Prior to this work, composition of PCPs was well-understood only in the constant error regime. Existing composition methods in the low error regime were non-modular (i.e., very much tailored ... more >>>

TR11-070 | 1st May 2011
Eli Ben-Sasson, Michael Viderman

#### Composition of semi-LTCs by two-wise Tensor Products

In this paper we obtain a composition theorem that allows us to construct locally testable codes (LTCs) by repeated two-wise tensor products. This is the First composition theorem showing that repeating the two-wise tensor operation any constant number of times still results in a locally testable code, improving upon previous ... more >>>

TR03-065 | 19th June 2003
Wee, Hoeteck

#### Compressibility Lower Bounds in Oracle Settings

A source is compressible if we can efficiently compute short
descriptions of strings in the support and efficiently
recover the strings from the descriptions. In this paper, we
present a technique for proving lower bounds on
compressibility in an oracle setting, which yields the
following results:

- We ... more >>>

TR15-092 | 31st May 2015
Yael Tauman Kalai, Ilan Komargodski

#### Compressing Communication in Distributed Protocols

Revisions: 2

We show how to compress communication in distributed protocols in which parties do not have private inputs. More specifically, we present a generic method for converting any protocol in which parties do not have private inputs, into another protocol where each message is "short" while preserving the same number of ... more >>>

TR16-081 | 20th May 2016
Alexander A. Sherstov

#### Compressing interactive communication under product distributions

We study the problem of compressing interactive communication to its
information content $I$, defined as the amount of information that the
participants learn about each other's inputs. We focus on the case when
the participants' inputs are distributed independently and show how to
compress the communication to $O(I\log^{2}I)$ bits, with ... more >>>

TR13-024 | 7th February 2013
Valentine Kabanets, Antonina Kolokolova

#### Compression of Boolean Functions

We consider the problem of compression for easy'' Boolean functions: given the truth table of an $n$-variate Boolean function $f$ computable by some \emph{unknown small circuit} from a \emph{known class} of circuits, find in deterministic time $\poly(2^n)$ a circuit $C$ (no restriction on the type of $C$) computing $f$ so ... more >>>

TR05-012 | 17th January 2005
Luca Trevisan, Salil Vadhan, David Zuckerman

#### Compression of Samplable Sources

We study the compression of polynomially samplable sources. In particular, we give efficient prefix-free compression and decompression algorithms for three classes of such sources (whose support is a subset of {0,1}^n).

1. We show how to compress sources X samplable by logspace machines to expected length H(X)+O(1).

Our next ... more >>>

TR08-031 | 14th January 2008
James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers

#### Computability and Complexity in Self-Assembly

This paper explores the impact of geometry on computability =
and complexity in
Winfree's model of nanoscale self-assembly. We work in the =
two-dimensional
tile assembly model, i.e., in the discrete Euclidean plane Z x Z. Our =
first
main theorem says that there is a roughly quadratic function f ... more >>>

TR16-146 | 18th September 2016
Scott Aaronson, Mohammad Bavarian, Giulio Gueltrini

#### Computability Theory of Closed Timelike Curves

We ask, and answer, the question of what's computable by Turing machines equipped with time travel into the past: that is, closed timelike curves or CTCs (with no bound on their size). We focus on a model for CTCs due to Deutsch, which imposes a probabilistic consistency condition to avoid ... more >>>

TR03-081 | 10th October 2003
Valentin E. Brimkov, Bruno Codenotti, Valentino Crespi, Reneta Barneva, Mauro Leoncini

#### Computation of the Lov\'asz Theta Function for Circulant Graphs

The Lov\'asz theta function $\theta(G)$ of a graph $G$ has attracted a lot of attention for its connection with diverse issues, such as communicating without errors and computing large cliques in graphs. Indeed this function enjoys the remarkable property of being computable in polynomial time, despite being sandwitched between clique ... more >>>

TR21-001 | 1st January 2021
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

#### Computation Over the Noisy Broadcast Channel with Malicious Parties

We study the $n$-party noisy broadcast channel with a constant fraction of malicious parties. Specifically, we assume that each non-malicious party holds an input bit, and communicates with the others in order to learn the input bits of all non-malicious parties. In each communication round, one of the parties broadcasts ... more >>>

TR20-067 | 30th April 2020
Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin

#### Computational and proof complexity of partial string avoidability

The partial string avoidability problem is stated as follows: given a finite set of strings with possible holes'' (wildcard symbols), determine whether there exists a two-sided infinite string containing no substrings from this set, assuming that a hole matches every symbol. The problem is known to be NP-hard and in ... more >>>

TR06-137 | 13th November 2006
Prashant Joshi, Eduardo D. Sontag

#### Computational aspects of feedback in neural circuits

It had previously been shown that generic cortical microcircuit
models can perform complex real-time computations on continuous
input streams, provided that these computations can be carried out
computational capability of such circuits in the ... more >>>

TR11-114 | 8th August 2011

#### Computational Bottlenecks for Evolvability

Valiant (2007) proposed a computational model for evolution and suggested that evolvability be studied in the framework of computational learning theory. Feldman (2008) showed that Valiant’s evolution model is equivalent to the correlational statistical query (CSQ) learning model, which is a restricted setting of the statistical query (SQ) model. Evolvability ... more >>>

TR94-007 | 12th December 1994
Oded Goldreich, Rafail Ostrovsky, Erez Petrank

#### Computational Complexity and Knowledge Complexity

We study the computational complexity of languages which have
interactive proofs of logarithmic knowledge complexity. We show that
all such languages can be recognized in ${\cal BPP}^{\cal NP}$. Prior
to this work, for languages with greater-than-zero knowledge
complexity (and specifically, even for knowledge complexity 1) only
trivial computational complexity bounds ... more >>>

TR06-159 | 3rd October 2006
Predrag Tosic

#### Computational Complexity of Some Enumeration Problems About Uniformly Sparse Boolean Network Automata

We study the computational complexity of counting the fixed point configurations (FPs), the predecessor configurations and the ancestor configurations in certain classes of graph or network automata viewed as discrete dynamical systems. Early results of this investigation are presented in two recent ECCC reports [39, 40]. In particular, it is ... more >>>

TR04-111 | 30th November 2004
Piotr Berman, Marek Karpinski, Alexander D. Scott, Alexander D. Scott

#### Computational Complexity of Some Restricted Instances of 3SAT

We prove results on the computational complexity of instances of 3SAT in which every variable occurs 3 or 4 times.

more >>>

TR02-014 | 10th December 2001
Klaus Weihrauch

#### Computational Complexity on Computable Metric Spaces

Revisions: 1

We introduce a new Turing machine based concept of time complexity for functions on computable metric spaces. It generalizes the ordinary complexity of word functions and the complexity of real functions studied by Ko \cite{Ko91} et al. Although this definition of ${\rm TIME}$ as the maximum of a generally infinite ... more >>>

TR12-009 | 28th November 2011
Prabhu Manyem, Julien Ugon

#### Computational Complexity, NP Completeness and Optimization Duality: A Survey

We survey research that studies the connection between the computational complexity
of optimization problems on the one hand, and the duality gap between the primal and
dual optimization problems on the other. To our knowledge, this is the first survey that
connects the two very important areas. We further look ... more >>>

TR96-067 | 20th December 1996
Oded Goldreich, Bernd Meyer

#### Computational Indistinguishability -- Algorithms vs. Circuits.

We present a simple proof to the existence of a probability ensemble
with tiny support which cannot be distinguished from the uniform ensemble
by any recursive computation.
Since the support is tiny (i.e, sub-polynomial),
this ensemble can be distinguish from the uniform ensemble
by a (non-uniform) family ... more >>>

TR98-017 | 29th March 1998

#### Computational Indistinguishability: A Sample Hierarchy.

We consider the existence of pairs of probability ensembles which
may be efficiently distinguished given $k$ samples
but cannot be efficiently distinguished given $k'<k$ samples.
It is well known that in any such pair of ensembles it cannot be that
both are efficiently computable
(and that such phenomena ... more >>>

TR97-028 | 12th July 1997
Scott E. Decatur, Oded Goldreich, Dana Ron

#### Computational Sample Complexity

In a variety of PAC learning models, a tradeoff between time and
information seems to exist: with unlimited time, a small amount of
sometimes seems to be required.
In addition, it has long been known that there are
concept classes ... more >>>

TR18-071 | 15th April 2018
Iftach Haitner, Kobbi Nissim, Eran Omri, Ronen Shaltiel, Jad Silbak

#### Computational Two-Party Correlation

Revisions: 1

Let $\pi$ be an efficient two-party protocol that given security parameter $\kappa$, both parties output single bits $X_\kappa$ and $Y_\kappa$, respectively. We are interested in how $(X_\kappa,Y_\kappa)$ appears'' to an efficient adversary that only views the transcript $T_\kappa$. We make the following contributions:

\begin{itemize}
\item We develop new tools to ... more >>>

TR15-042 | 30th March 2015
Ilya Volkovich

#### Computations beyond Exponentiation Gates and Applications

In Arithmetic Circuit Complexity the standard operations are $\{+,\times\}$.
Yet, in some scenarios exponentiation gates are considered as well (see e.g. \cite{BshoutyBshouty98,ASSS12,Kayal12,KSS14}).
In this paper we study the question of efficiently evaluating a polynomial given an oracle access to its power.
That is, beyond an exponentiation gate. As ... more >>>

TR07-067 | 22nd May 2007
Paul Spirakis, haralampos tsaknakis

#### Computing 1/3-approximate Nash equilibria of bimatrix games in polynomial time.

Revisions: 2

In this paper we propose a methodology for determining approximate Nash equilibria of non-cooperative bimatrix games and, based on that, we provide a polynomial time algorithm that computes $\frac{1}{3} + \frac{1}{p(n)}$ -approximate equilibria, where $p(n)$ is a polynomial controlled by our algorithm and proportional to its running time. The ... more >>>

TR12-126 | 23rd September 2012
Shiva Kintali, Sinziana Munteanu

#### Computing Bounded Path Decompositions in Logspace

We present a logspace algorithm to compute path decompositions of bounded pathwidth graphs, thus settling its complexity. Prior to our work, the best known upper bound to compute such decompositions was linear time. We also show that deciding if the pathwidth of a graph is at most a given constant ... more >>>

TR02-052 | 3rd September 2002
Vince Grolmusz

#### Computing Elementary Symmetric Polynomials with a Sub-Polynomial Number of Multiplications

Revisions: 1

Elementary symmetric polynomials $S_n^k$ are used as a
benchmark for the bounded-depth arithmetic circuit model of computation.
In this work we prove that $S_n^k$ modulo composite numbers $m=p_1p_2$
can be computed with much fewer multiplications than over any field, if
the coefficients of monomials $x_{i_1}x_{i_2}\cdots x_{i_k}$ ... more >>>

TR15-153 | 21st September 2015
Tim Roughgarden

#### Computing Equilibria: A Computational Complexity Perspective

Computational complexity is the subfield of computer science that rigorously studies the intrinsic difficulty of computational problems. This survey explains how complexity theory defines “hard problems”; applies these concepts to several equilibrium computation problems; and discusses implications for computation, games, and behavior. We assume minimal prior background in computer science.

... more >>>

TR20-092 | 16th June 2020
Ashish Dwivedi, Nitin Saxena

#### Computing Igusa's local zeta function of univariates in deterministic polynomial-time

Igusa's local zeta function $Z_{f,p}(s)$ is the generating function that counts the number of integral roots, $N_{k}(f)$, of $f(\mathbf x) \bmod p^k$, for all $k$. It is a famous result, in analytic number theory, that $Z_{f,p}$ is a rational function in $\mathbb{Q}(p^s)$. We give an elementary proof of this fact ... more >>>

TR16-158 | 9th October 2016

#### Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates

We study the following computational problem: for which values of $k$, the majority of $n$ bits $\text{MAJ}_n$ can be computed with a depth two formula whose each gate computes a majority function of at most $k$ bits? The corresponding computational model is denoted by $\text{MAJ}_k \circ \text{MAJ}_k$. We observe that ... more >>>

TR06-023 | 7th February 2006
Xi Chen, Xiaotie Deng, Shang-Hua Teng

By proving that the problem of computing a $1/n^{\Theta(1)}$-approximate Nash equilibrium remains \textbf{PPAD}-complete, we show that the BIMATRIX game is not likely to have a fully polynomial-time approximation scheme. In other words, no algorithm with time polynomial in $n$ and $1/\epsilon$ can compute an $\epsilon$-approximate Nash equilibrium of an $n\times ... more >>> TR14-106 | 9th August 2014 Craig Gentry #### Computing on the edge of chaos: Structure and randomness in encrypted computation This survey, aimed mainly at mathematicians rather than practitioners, covers recent developments in homomorphic encryption (computing on encrypted data) and program obfuscation (generating encrypted but functional programs). Current schemes for encrypted computation all use essentially the same "noisy" approach: they encrypt via a noisy encoding of the message, they decrypt ... more >>> TR11-094 | 20th June 2011 Shachar Lovett #### Computing polynomials with few multiplications A folklore result in arithmetic complexity shows that the number of multiplications required to compute some$n$-variate polynomial of degree$d$is$\sqrt{{n+d \choose n}}$. We complement this by an almost matching upper bound, showing that any$n$-variate polynomial of degree$d$over any field can be computed with only ... more >>> TR16-179 | 15th November 2016 Avishay Tal #### Computing Requires Larger Formulas than Approximating A de Morgan formula over Boolean variables$x_1, \ldots, x_n$is a binary tree whose internal nodes are marked with AND or OR gates and whose leaves are marked with variables or their negation. We define the size of the formula as the number of leaves in it. Proving that ... more >>> TR96-027 | 20th February 1996 Lane A. Hemaspaandra, Ashish Naik, Mitsunori Ogihara, Alan L. Selman #### Computing Solutions Uniquely Collapses the Polynomial Hierarchy Is there an NP function that, when given a satisfiable formula as input, outputs one satisfying assignment uniquely? That is, can a nondeterministic function cull just one satisfying assignment from a possibly exponentially large collection of assignments? We show that if there is such a nondeterministic function, then the polynomial ... more >>> TR94-025 | 12th December 1994 David P. Dobkin, Dimitrios Gunopulos #### Computing the Maximum Bichromatic Discrepancy with applications to Computer Graphics and Machine Learning Computing the maximum bichromatic discrepancy is an interesting theoretical problem with important applications in computational learning theory, computational geometry and computer graphics. In this paper we give algorithms to compute the maximum bichromatic discrepancy for simple geometric ranges, including rectangles and halfspaces. In addition, we give ... more >>> TR18-020 | 30th January 2018 Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari #### Computing the maximum using$(\min, +)$formulas Comments: 1 We study computation by formulas over$(min, +)$. We consider the computation of$\max\{x_1,\ldots,x_n\}$over$\mathbb{N}$as a difference of$(\min, +)$formulas, and show that size$n + n \log n$is sufficient and necessary. Our proof also shows that any$(\min, +)$formula computing the minimum of all ... more >>> TR14-053 | 15th April 2014 Harry Buhrman, Richard Cleve, Michal Koucky, Bruno Loff, Florian Speelman #### Computing with a full memory: Catalytic space Revisions: 1 We define the notion of a catalytic-space computation. This is a computation that has a small amount of clean space available and is equipped with additional auxiliary space, with the caveat that the additional space is initially in an arbitrary, possibly incompressible, state and must be returned to this state ... more >>> TR08-054 | 13th May 2008 Venkatesan Guruswami, Atri Rudra #### Concatenated codes can achieve list-decoding capacity We prove that binary linear concatenated codes with an outer algebraic code (specifically, a folded Reed-Solomon code) and independently and randomly chosen linear inner codes achieve the list-decoding capacity with high probability. In particular, for any$0 < \rho < 1/2$and$\epsilon > 0$, there exist concatenated codes of ... more >>> TR07-002 | 8th November 2006 Moti Yung, Yunlei Zhao #### Concurrent Knowledge-Extraction in the Public-Key Model Comments: 2 Knowledge extraction is a fundamental notion, modeling knowledge possession in a computational complexity sense. The notion provides a tool for cryptographic protocol design and analysis, enabling one to argue about the internal state of protocol players. We define and investigate the relative power of the notion of concurrent knowledge-extraction'' ... more >>> TR06-095 | 25th July 2006 Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti #### Concurrent Non-Malleable Witness Indistinguishability and its Applications Revisions: 1 One of the central questions in Cryptography today is proving security of the protocols on the Internet'', i.e., in a concurrent setting where there are multiple interactions between players, and where the adversary can play so called man-in-the-middle'' attacks, forwarding and modifying messages between two or more unsuspecting players. Indeed, ... more >>> TR05-093 | 24th August 2005 Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil Vadhan #### Concurrent Zero Knowledge without Complexity Assumptions We provide <i>unconditional</i> constructions of <i>concurrent</i> statistical zero-knowledge proofs for a variety of non-trivial problems (not known to have probabilistic polynomial-time algorithms). The problems include Graph Isomorphism, Graph Nonisomorphism, Quadratic Residuosity, Quadratic Nonresiduosity, a restricted version of Statistical Difference, and approximate versions of the (<b>coNP</b> forms of the) Shortest Vector ... more >>> TR01-091 | 27th November 2001 Oded Goldreich #### Concurrent Zero-Knowledge With Timing, Revisited Following Dwork, Naor, and Sahai (30th STOC, 1998), we consider concurrent execution of protocols in a semi-synchronized network. Specifically, we assume that each party holds a local clock such that a constant bound on the relative rates of these clocks is a-priori known, and consider protocols that employ ... more >>> TR21-026 | 23rd February 2021 Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep #### Conditional Dichotomy of Boolean Ordered Promise CSPs Promise Constraint Satisfaction Problems (PCSPs) are a generalization of Constraint Satisfaction Problems (CSPs) where each predicate has a strong and a weak form and given a CSP instance, the objective is to distinguish if the strong form can be satisfied vs. even the weak form cannot be satisfied. Since their ... more >>> TR17-189 | 25th December 2017 Benny Applebaum, Barak Arkis #### Conditional Disclosure of Secrets and$d$-Uniform Secret Sharing with Constant Information Rate Revisions: 1 Consider the following secret-sharing problem. Your goal is to distribute a long file$s$between$n$servers such that$(d-1)$-subsets cannot recover the file,$(d+1)$-subsets can recover the file, and$d$-subsets should be able to recover$s$if and only if they appear in some predefined list$L$. How small ... more >>> TR17-038 | 23rd February 2017 Benny Applebaum, Barak Arkis, Pavel Raykov, Prashant Nalini Vasudevan #### Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lower-bounds, and Separations Revisions: 1 In the \emph{conditional disclosure of secrets} problem (Gertner et al., J. Comput. Syst. Sci., 2000) Alice and Bob, who hold inputs$x$and$y$respectively, wish to release a common secret$s$to Carol (who knows both$x$and$y$) if only if the input$(x,y)$satisfies some predefined predicate ... more >>> TR05-039 | 13th April 2005 Irit Dinur, Elchanan Mossel, Oded Regev #### Conditional Hardness for Approximate Coloring We study the approximate-coloring(q,Q) problem: Given a graph G, decide whether \chi(G) \le q or \chi(G)\ge Q. We derive conditional hardness for this problem for any constant 3\le q < Q. For q \ge 4, our result is based on Khot's 2-to-1 conjecture [Khot'02]. For q=3, we base our hardness ... more >>> TR09-125 | 24th November 2009 David Steurer, Nisheeth Vishnoi #### Connections Between Unique Games and Multicut In this paper we demonstrate a close connection between UniqueGames and MultiCut. % In MultiCut, one is given a network graph'' and a demand graph'' on the same vertex set and the goal is to remove as few edges from the network graph as ... more >>> TR19-077 | 30th May 2019 Jan Bydzovsky, Igor Carboni Oliveira, Jan Krajicek #### Consistency of circuit lower bounds with bounded theories Proving that there are problems in$P^{NP}$that require boolean circuits of super-linear size is a major frontier in complexity theory. While such lower bounds are known for larger complexity classes, existing results only show that the corresponding problems are hard on infinitely many input lengths. For instance, proving almost-everywhere ... more >>> TR16-197 | 7th December 2016 Igor Carboni Oliveira, Rahul Santhanam #### Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness We prove several results giving new and stronger connections between learning theory, circuit complexity and pseudorandomness. Let C be any typical class of Boolean circuits, and C[s(n)] denote n-variable C-circuits of size at most s(n). We show: Learning Speedups: If C[$n^{O(1)}$] admits a randomized weak learning algorithm under the uniform ... more >>> TR20-183 | 6th December 2020 Rahul Ilango #### Constant Depth Formula and Partial Function Versions of MCSP are Hard Attempts to prove the intractability of the Minimum Circuit Size Problem (MCSP) date as far back as the 1950s and are well-motivated by connections to cryptography, learning theory, and average-case complexity. In this work, we make progress, on two fronts, towards showing MCSP is intractable under worst-case assumptions. While ... more >>> TR13-085 | 13th June 2013 Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, Henning Stichtenoth #### Constant rate PCPs for circuit-SAT with sublinear query complexity The PCP theorem (Arora et. al., J. ACM 45(1,3)) says that every NP-proof can be encoded to another proof, namely, a probabilistically checkable proof (PCP), which can be tested by a verifier that queries only a small part of the PCP. A natural question is how large is the blow-up ... more >>> TR03-025 | 14th April 2003 Kristoffer Arnsfelt Hansen #### Constant width planar computation characterizes ACC0 We obtain a characterization of ACC0 in terms of a natural class of constant width circuits, namely in terms of constant width polynomial size planar circuits. This is shown via a characterization of the class of acyclic digraphs which can be embedded on a cylinder surface in such a way ... more >>> TR05-087 | 9th August 2005 Alexander Healy, Emanuele Viola #### Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two We study the complexity of arithmetic in finite fields of characteristic two,$\F_{2^n}$. We concentrate on the following two problems: Iterated Multiplication: Given$\alpha_1, \alpha_2,..., \alpha_t \in \F_{2^n}$, compute$\alpha_1 \cdot \alpha_2 \cdots \alpha_t \in \F_{2^n}$. Exponentiation: Given$\alpha \in \F_{2^n}$and a$t$-bit integer$k$, compute$\alpha^k \in \F_{2^n}$. ... more >>> TR22-116 | 17th August 2022 Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir Podolskii #### Constant-Depth Sorting Networks In this paper, we address sorting networks that are constructed from comparators of arity$k > 2$. That is, in our setting the arity of the comparators -- or, in other words, the number of inputs that can be sorted at the unit cost -- is a parameter. We study ... more >>> TR18-133 | 26th July 2018 Emanuele Viola #### Constant-error pseudorandomness proofs from hardness require majority Revisions: 1 Research in the 80's and 90's showed how to construct a pseudorandom generator from a function that is hard to compute on more than$99\%$of the inputs. A more recent line of works showed however that if the generator has small error, then the proof of correctness cannot be ... more >>> TR15-197 | 7th December 2015 Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler #### Constant-rate coding for multiparty interactive communication is impossible We study coding schemes for multiparty interactive communication over synchronous networks that suffer from stochastic noise, where each bit is independently flipped with probability$\epsilon$. We analyze the minimal overhead that must be added by the coding scheme in order to succeed in performing the computation despite the noise. Our ... more >>> TR17-095 | 26th May 2017 Ran Gelles, Yael Tauman Kalai #### Constant-Rate Interactive Coding Is Impossible, Even In Constant-Degree Networks Multiparty interactive coding allows a network of$n$parties to perform distributed computations when the communication channels suffer from noise. Previous results (Rajagopalan and Schulman, STOC '94) obtained a multiparty interactive coding protocol, resilient to random noise, with a blowup of$O(\log(\Delta+1))$for networks whose topology has a maximal degree ... more >>> TR05-048 | 11th April 2005 Moti Yung, Yunlei Zhao #### Constant-Round Concurrently-Secure rZK in the (Real) Bare Public-Key Model Revisions: 3 We present constant-round concurrently secure (sound) resettable zero-knowledge (rZK-CS) arguments in the bare public-key (BPK) model. Our constructions deal with general NP ZK-arguments as well as with highly efficient ZK-arguments for number-theoretic languages, most relevant to identification scenarios. These are the first constant-round protocols of ... more >>> TR18-069 | 14th April 2018 Oded Goldreich, Guy Rothblum #### Constant-round interactive proof systems for AC0[2] and NC1 Revisions: 1 We present constant-round interactive proof systems for sufficiently uniform versions of AC0[2] and NC1. Both proof systems are doubly-efficient, and offer a better trade-off between the round complexity and the total communication than the work of Reingold, Rothblum, and Rothblum (STOC, 2016). Our proof system for AC0[2] supports a more ... more >>> TR16-061 | 17th April 2016 Omer Reingold, Ron Rothblum, Guy Rothblum #### Constant-Round Interactive Proofs for Delegating Computation Revisions: 2 The celebrated IP=PSPACE Theorem [LFKN92,Shamir92] allows an all-powerful but untrusted prover to convince a polynomial-time verifier of the validity of extremely complicated statements (as long as they can be evaluated using polynomial space). The interactive proof system designed for this purpose requires a polynomial number of communication rounds and an ... more >>> TR11-003 | 10th January 2011 Yehuda Lindell #### Constant-Round Zero-Knowledge Proofs of Knowledge Revisions: 1 In this note, we show the existence of \emph{constant-round} computational zero-knowledge \emph{proofs of knowledge} for all$\cal NP$. The existence of constant-round zero-knowledge proofs was proven by Goldreich and Kahan (Journal of Cryptology, 1996), and the existence of constant-round zero-knowledge \emph{arguments} of knowledge was proven by Feige and Shamir (CRYPTO ... more >>> TR05-005 | 20th December 2004 Tomas Feder #### Constraint Satisfaction on Finite Groups with Near Subgroups Constraint satisfaction on finite groups, with subgroups and their cosets described by generators, has a polynomial time algorithm. For any given group, a single additional constraint type that is not a coset of a near subgroup makes the problem NP-complete. We consider constraint satisfaction on groups with subgroups, near subgroups, ... more >>> TR08-008 | 8th February 2008 Venkatesan Guruswami, Prasad Raghavendra #### Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness Revisions: 1 We study the approximability of the \maxcsp problem over non-boolean domains, more specifically over$\{0,1,\ldots,q-1\}$for some integer$q$. We obtain a approximation algorithm that achieves a ratio of$C(q) \cdot k/q^k$for some constant$C(q)$depending only on$q$. Further, we extend the techniques of Samorodnitsky and Trevisan to ... more >>> TR07-055 | 22nd May 2007 Oliver Kullmann #### Constraint satisfaction problems in clausal form: Autarkies and minimal unsatisfiability Revisions: 1 We consider the next step from boolean conjunctive normal forms to arbitrary constraint satisfaction problems (with arbitrary constraints), namely "generalised clause-sets" (or "sets of no-goods"), which allow negative literals "v <> e" for variables v and values e --- this level of generality appears to be the right level for ... more >>> TR06-021 | 10th February 2006 Tomas Feder #### Constraint satisfaction: a personal perspective Attempts at classifying computational problems as polynomial time solvable, NP-complete, or belonging to a higher level in the polynomial hierarchy, face the difficulty of undecidability. These classes, including NP, admit a logic formulation. By suitably restricting the formulation, one finds the logic class MMSNP, or monotone monadic strict NP without more >>> TR96-064 | 11th December 1996 Sanjeev Khanna, Madhu Sudan, Luca Trevisan #### Constraint satisfaction: The approximability of minimization problems. This paper continues the work initiated by Creignou [Cre95] and Khanna, Sudan and Williamson [KSW96] who classify maximization problems derived from boolean constraint satisfaction. Here we study the approximability of {\em minimization} problems derived thence. A problem in this framework is characterized by a collection F ... more >>> TR12-114 | 15th July 2012 Mikhail Anokhin #### Constructing a Pseudo-Free Family of Finite Computational Groups under the General Integer Factoring Intractability Assumption Revisions: 5 We construct a provably pseudo-free family of finite computational groups under the general integer factoring intractability assumption. Moreover, this family has exponential size. But each element of a group in our pseudo-free family is represented by many bit strings. more >>> TR14-140 | 31st October 2014 Hong Van Le #### Constructing elusive functions with help of evaluation mappings We develop a method to construct elusive functions using techniques of commutative algebra and algebraic geometry. The key notions of this method are elusive subsets and evaluation mappings. We also develop the effective elimination theory combined with algebraic number field theory in order to construct concrete points outside the image ... more >>> TR18-212 | 26th December 2018 Prerona Chatterjee, Ramprasad Saptharishi #### Constructing Faithful Homomorphisms over Fields of Finite Characteristic Revisions: 1 We study the question of algebraic rank or transcendence degree preserving homomorphisms over finite fields. This concept was first introduced by Beecken, Mittmann and Saxena (Information and Computing, 2013), and exploited by them, and Agrawal, Saha, Saptharishi and Saxena (Journal of Computing, 2016) to design algebraic independence based identity tests ... more >>> TR13-129 | 17th September 2013 Adam Klivans, Pravesh Kothari, Igor Oliveira #### Constructing Hard Functions from Learning Algorithms Revisions: 1 Fortnow and Klivans proved the following relationship between efficient learning algorithms and circuit lower bounds: if a class$\mathcal{C} \subseteq P/poly$of Boolean circuits is exactly learnable with membership and equivalence queries in polynomial-time, then$EXP^{NP} \not \subseteq \mathcal{C}$(the class$EXP^{NP}$was subsequently improved to$P$by Hitchcock and ... more >>> TR20-192 | 27th December 2020 Oded Goldreich, Avi Wigderson #### Constructing Large Families of Pairwise Far Permutations: Good Permutation Codes Based on the Shuffle-Exchange Network We consider the problem of efficiently constructing an as large as possible family of permutations such that each pair of permutations are far part (i.e., disagree on a constant fraction of their inputs). Specifically, for every$n\in\N$, we present a collection of$N=N(n)=(n!)^{\Omega(1)}$pairwise far apart permutations$\{\pi_i:[n]\to[n]\}_{i\in[N]}$and ... more >>> TR15-019 | 3rd February 2015 Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira #### Constructing Near Spanning Trees with Few Local Inspections Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. Motivated by several recent studies of local graph algorithms, we consider the following variant of this problem. Let$G$be a connected bounded-degree graph. Given an edge$e$in$G$we would like ... more >>> TR05-143 | 29th November 2005 Parikshit Gopalan #### Constructing Ramsey Graphs from Boolean Function Representations Explicit construction of Ramsey graphs or graphs with no large clique or independent set has remained a challenging open problem for a long time. While Erdos's probabilistic argument shows the existence of graphs on 2^n vertices with no clique or independent set of size 2n, the best known explicit constructions ... more >>> TR01-002 | 6th December 2000 Venkatesan Guruswami #### Constructions of Codes from Number Fields We define number-theoretic error-correcting codes based on algebraic number fields, thereby providing a generalization of Chinese Remainder Codes akin to the generalization of Reed-Solomon codes to Algebraic-geometric codes. Our construction is very similar to (and in fact less general than) the one given by (Lenstra 1986), but the ... more >>> TR05-155 | 10th December 2005 Amir Shpilka #### Constructions of low-degree and error-correcting epsilon-biased sets In this work we give two new constructions of$\epsilon$-biased generators. Our first construction answers an open question of Dodis and Smith, and our second construction significantly extends a result of Mossel et al. In particular we obtain the following results: 1. We construct a family of asymptotically good binary ... more >>> TR98-055 | 4th September 1998 Luca Trevisan #### Constructions of Near-Optimal Extractors Using Pseudo-Random Generators Comments: 1 We introduce a new approach to construct extractors -- combinatorial objects akin to expander graphs that have several applications. Our approach is based on error correcting codes and on the Nisan-Wigderson pseudorandom generator. An application of our approach yields a construction that is simple to ... more >>> TR10-072 | 19th April 2010 Russell Impagliazzo, Valentine Kabanets #### Constructive Proofs of Concentration Bounds We give a simple combinatorial proof of the Chernoff-Hoeffding concentration bound~\cite{Chernoff, Hof63}, which says that the sum of independent$\{0,1\}$-valued random variables is highly concentrated around the expected value. Unlike the standard proofs, our proof does not use the method of higher moments, but rather uses a simple ... more >>> TR21-159 | 15th November 2021 Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams #### Constructive Separations and Their Consequences For a complexity class$C$and language$L$, a constructive separation of$L \notin C$gives an efficient algorithm (also called a refuter) to find counterexamples (bad inputs) for every$C$-algorithm attempting to decide$L$. We study the questions: Which lower bounds can be made constructive? What are the consequences ... more >>> TR08-047 | 17th March 2008 Vijay V. Vazirani, Wang Lei #### Continuity Properties of Equilibria in Some Fisher and Arrow-Debreu Market Models Following up on the work of Megiddo and Vazirani \cite{MV.2007}, who determined continuity properties of equilibrium prices and allocations for perhaps the simplest market model, Fisher's linear case, we do the same for: \begin{itemize} \item Fisher's model with piecewise-linear, concave utilities \item Fisher's model with spending constraint utilities \item Arrow-Debreu's ... more >>> TR09-136 | 9th December 2009 Michael Burr, Felix Krahmer, Chee Yap #### Continuous Amortization: A Non-Probabilistic Adaptive Analysis Technique Let$f$be a univariate polynomial with real coefficients,$f\in\RR[X]$. Subdivision algorithms based on algebraic techniques (e.g., Sturm or Descartes methods) are widely used for isolating the roots of$f$in a given interval. In this paper, we consider subdivision algorithms based on purely numerical primitives such as function evaluation. more >>> TR20-080 | 19th May 2020 Joan Bruna, Oded Regev, Min Jae Song, Yi Tang #### Continuous LWE Revisions: 1 We introduce a continuous analogue of the Learning with Errors (LWE) problem, which we name CLWE. We give a polynomial-time quantum reduction from worst-case lattice problems to CLWE, showing that CLWE enjoys similar hardness guarantees to those of LWE. Alternatively, our result can also be seen as opening new avenues ... more >>> TR18-170 | 4th October 2018 Nicola Galesi, Navid Talebanfard, Jacobo Toran #### Cops-Robber games and the resolution of Tseitin formulas We characterize several complexity measures for the resolution of Tseitin formulas in terms of a two person cop-robber game. Our game is a slight variation of the one Seymour and Thomas used in order to characterize the tree-width parameter. For any undirected graph, by counting the number of cops needed ... more >>> TR12-172 | 8th December 2012 Mahdi Cheraghchi, Anna Gal, Andrew Mills #### Correctness and Corruption of Locally Decodable Codes Revisions: 1 Locally decodable codes (LDCs) are error correcting codes with the extra property that it is sufficient to read just a small number of positions of a possibly corrupted codeword in order to recover any one position of the input. To achieve this, it is necessary to use randomness in the ... more >>> TR22-142 | 3rd November 2022 Emanuele Viola #### Correlation bounds against polynomials A survey on correlation bounds against polynomials. more >>> TR14-184 | 29th December 2014 Ruiwen Chen, Valentine Kabanets #### Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits We revisit the gate elimination method, generalize it to prove correlation bounds of boolean circuits with Parity, and also derive deterministic #SAT algorithms for small linear-size circuits. In particular, we prove that, for boolean circuits of size$3n - n^{0.51}$, the correlation with Parity is at most$2^{-n^{\Omega(1)}}$, and there ... more >>> TR15-122 | 29th July 2015 Shiteng Chen, Periklis Papakonstantinou #### Correlation lower bounds from correlation upper bounds We show that for any coprime$m,r$there is a circuit of the form$\text{MOD}_m\circ \text{AND}_{d(n)}$whose correlation with$\text{MOD}_r$is at least$2^{-O\left( \frac{n}{d(n)} \right) }$. This is the first correlation lower bound for arbitrary$m,r$, whereas previously lower bounds were known for prime$m$. Our motivation is the ... more >>> TR11-029 | 6th March 2011 Hamed Hatami, Shachar Lovett #### Correlation testing for affine invariant properties on$\mathbb{F}_p^n$in the high error regime Revisions: 1 Recently there has been much interest in Gowers uniformity norms from the perspective of theoretical computer science. This is mainly due to the fact that these norms provide a method for testing whether the maximum correlation of a function$f:\mathbb{F}_p^n \rightarrow \mathbb{F}_p$with polynomials of degree at most$d \le ... more >>>

TR18-134 | 24th July 2018
Tali Kaufman, David Mass

#### Cosystolic Expanders over any Abelian Group

In this work we show a general reduction from high dimensional complexes to their links based on the spectral properties of the links. We use this reduction to show that if a certain property is testable in the links, then it is also testable in the complex. In particular, we ... more >>>

TR18-046 | 9th March 2018
Oded Goldreich, Guy Rothblum

#### Counting $t$-cliques: Worst-case to average-case reductions and Direct interactive proof systems

Revisions: 2

We present two main results regarding the complexity of counting the number of $t$-cliques in a graph.

\begin{enumerate}
\item{\em A worst-case to average-case reduction}:
We reduce counting $t$-cliques in any $n$-vertex graph to counting $t$-cliques in typical $n$-vertex graphs that are drawn from a simple distribution of min-entropy ${\widetilde\Omega}(n^2)$. For ... more >>>

TR19-033 | 20th February 2019
Ashish Dwivedi, Rajat Mittal, Nitin Saxena

#### Counting basic-irreducible factors mod $p^k$ in deterministic poly-time and $p$-adic applications

Finding an irreducible factor, of a polynomial $f(x)$ modulo a prime $p$, is not known to be in deterministic polynomial time. Though there is such a classical algorithm that {\em counts} the number of irreducible factors of $f\bmod p$. We can ask the same question modulo prime-powers $p^k$. The irreducible ... more >>>

TR10-101 | 25th June 2010
Samir Datta, Meena Mahajan, Raghavendra Rao B V, Michael Thomas, Heribert Vollmer

#### Counting Classes and the Fine Structure between NC$^1$ and L.

The class NC$^1$ of problems solvable by bounded fan-in circuit families of logarithmic depth is known to be contained in logarithmic space L, but not much about the converse is known. In this paper we examine the structure of classes in between NC$^1$ and L based on counting functions or, ... more >>>

TR05-091 | 11th August 2005
Predrag Tosic

#### Counting Fixed Points and Gardens of Eden of Sequential Dynamical Systems on Planar Bipartite Graphs

Revisions: 1

We study counting various types of con gurations in certain classes of graph
automata viewed as discrete dynamical systems. The graph automata models
of our interest are Sequential and Synchronous Dynamical Systems (SDSs and
SyDSs, respectively). These models have been proposed as a mathematical foun-
dation for a theory of ... more >>>

TR97-034 | 3rd September 1997
Jui-Lin Lee

#### Counting in uniform $TC^0$

In this paper we first give a uniform $AC^0$ algorithm which uses
partial sums to compute multiple addition. Then we use it to show
that multiple addition is computable in uniform $TC^0$ by using
$count$ only once sequentially. By constructing bit matrix for

TR10-103 | 28th June 2010
Andreas Krebs, Nutan Limaye, Meena Mahajan

#### Counting paths in VPA is complete for \#NC$^1$

We give a \#NC$^1$ upper bound for the problem of counting accepting paths in any fixed visibly pushdown automaton. Our algorithm involves a non-trivial adaptation of the arithmetic formula evaluation algorithm of Buss, Cook, Gupta, Ramachandran (BCGR: SICOMP 21(4), 1992). We also show that the problem is \#NC$^1$ hard. Our ... more >>>

TR09-083 | 24th September 2009
Dana Ron, Mira Gonen, Yuval Shavitt

#### Counting Stars and Other Small Subgraphs in Sublinear Time

Detecting and counting the number of copies of certain subgraphs (also known as {\em network motifs\/} or {\em graphlets\/}), is motivated by applications in a variety of areas ranging from Biology to the study of the World-Wide-Web. Several polynomial-time algorithms have been suggested for counting or detecting the number of ... more >>>

TR20-177 | 12th October 2020
Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira

#### Counting Subgraphs in Degenerate Graphs

We consider the problem of counting the number of copies of a fixed graph $H$ within an input graph $G$. This is one of the most well-studied algorithmic graph problems, with many theoretical and practical applications. We focus on solving this problem when the input $G$ has {\em bounded degeneracy}. ... more >>>

TR14-079 | 11th June 2014
Simon Straub, Thomas Thierauf, Fabian Wagner

#### Counting the Number of Perfect Matchings in $K_5$-free Graphs

Counting the number of perfect matchings in arbitrary graphs is a $\#$P-complete problem. However, for some restricted classes of graphs the problem can be solved efficiently. In the case of planar graphs, and even for $K_{3,3}$-free graphs, Vazirani showed that it is in NC$^2$. The technique there is to compute ... more >>>

TR04-011 | 16th January 2004
Christian Glaßer

#### Counting with Counterfree Automata

We study the power of balanced regular leaf-languages.
First, we investigate (i) regular languages that are
polylog-time reducible to languages in dot-depth 1/2 and
(ii) regular languages that are polylog-time decidable.
For both classes we provide

- forbidden-pattern characterizations, and
- characterizations in terms of regular expressions.

Both ... more >>>

TR19-180 | 6th December 2019
Andreas Lenz, Cyrus Rashtchian, Paul Siegel, Eitan Yaakobi

#### Covering Codes for Insertions and Deletions

Revisions: 1

A covering code is a set of codewords with the property that the union of balls, suitably defined, around these codewords covers an entire space. Generally, the goal is to find the covering code with the minimum size codebook. While most prior work on covering codes has focused on the ... more >>>

TR12-088 | 7th July 2012
Irit Dinur, Gillat Kol

#### Covering CSPs

We study the covering complexity of constraint satisfaction problems (CSPs). The covering number of a CSP instance C, denoted $\nu(C)$, is the smallest number of assignments to the variables, such that each constraint is satisfied by at least one of the assignments. This covering notion describes situations in which we ... more >>>

TR22-182 | 16th December 2022
Prahladh Harsha, Tulasi mohan Molli, A. Shankar

#### Criticality of AC0-Formulae

Revisions: 1

Rossman [In Proc. 34th Comput. Complexity Conf., 2019] introduced the notion of criticality. The criticality of a Boolean function $f : \{0, 1\}^n\to \{0, 1\}$ is the minimum $\lambda \geq 1$ such that for all positive integers $t$,
$Pr_{\rho\sim R_p} [\text{DT}_{\text{depth}}(f|_\rho) \geq t] \leq (p\lambda)^t.$
.
Håstad’s celebrated switching lemma ... more >>>

TR17-047 | 10th March 2017
Kasper Green Larsen, Omri Weinstein, Huacheng Yu

#### Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds

This paper proves the first super-logarithmic lower bounds on the cell probe complexity of dynamic \emph{boolean} (a.k.a. decision) data structure problems, a long-standing milestone in data structure lower bounds.

We introduce a new method for proving dynamic cell probe lower bounds and use it to prove a $\tilde{\Omega}(\log^{1.5} ... more >>> TR04-101 | 28th September 2004 Miroslav Chlebik, Janka Chlebíková #### Crown reductions for the Minimum Weighted Vertex Cover problem TR09-123 | 23rd November 2009 Hemanta Maji, Manoj Prabhakaran, Mike Rosulek #### Cryptographic Complexity Classes and Computational Intractability Assumptions Which computational intractability assumptions are inherent to cryptography? We present a broad framework to pose and investigate this question. We first aim to understand the “cryptographic complexity” of various tasks, independent of any computational assumptions. In our framework the cryptographic tasks are modeled as multi- party computation functionalities. We consider ... more >>> TR08-050 | 12th March 2008 Manoj Prabhakaran, Mike Rosulek #### Cryptographic Complexity of Multi-party Computation Problems: Classifications and Separations We develop new tools to study the relative complexities of secure multi-party computation tasks (functionalities) in the Universal Composition framework. When one task can be securely realized using another task as a black-box, we interpret this as a qualitative, complexity-theoretic reduction between the two tasks. Virtually all previous characterizations of ... more >>> TR02-017 | 12th March 2002 Aggelos Kiayias, Moti Yung #### Cryptographic Hardness based on the Decoding of Reed-Solomon Codes with Applications We investigate the decoding problem of Reed-Solomon Codes (aka: the Polynomial Reconstruction Problem -- PR) from a cryptographic hardness perspective. First, following the standard methodology for constructing cryptographically strong primitives, we formulate a decisional intractability assumption related to the PR problem. Then, based on this assumption we show: (i) hardness ... more >>> TR15-027 | 25th February 2015 Benny Applebaum #### Cryptographic Hardness of Random Local Functions -- Survey Revisions: 1 Constant parallel-time cryptography allows to perform complex cryptographic tasks at an ultimate level of parallelism, namely, by local functions that each of their output bits depend on a constant number of input bits. A natural way to obtain local cryptographic constructions is to use \emph{random local functions} in which each ... more >>> TR06-057 | 19th April 2006 Adam Klivans, Alexander A. Sherstov #### Cryptographic Hardness Results for Learning Intersections of Halfspaces We give the first representation-independent hardness results for PAC learning intersections of halfspaces, a central concept class in computational learning theory. Our hardness results are derived from two public-key cryptosystems due to Regev, which are based on the worst-case hardness of well-studied lattice problems. Specifically, we prove that a polynomial-time ... more >>> TR21-010 | 11th February 2021 Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle #### Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity Revisions: 2 A version of time-bounded Kolmogorov complexity, denoted KT, has received attention in the past several years, due to its close connection to circuit complexity and to the Minimum Circuit Size Problem MCSP. Essentially all results about the complexity of MCSP hold also for MKTP (the problem of computing the KT ... more >>> TR20-044 | 8th April 2020 Marshall Ball, Elette Boyle, Akshay Degwekar, Apoorvaa Deshpande, Alon Rosen, Vinod Vaikuntanathan, Prashant Vasudevan #### Cryptography from Information Loss Revisions: 1 Reductions between problems, the mainstay of theoretical computer science, efficiently map an instance of one problem to an instance of another in such a way that solving the latter allows solving the former. The subject of this work is lossy'' reductions, where the reduction loses some information about the input ... more >>> TR21-055 | 20th April 2021 Yanyi Liu, Rafael Pass #### Cryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity Let$\mktp[s]$be the set of strings$x$such that$K^t(x) \leq s(|x|)$, where$K^t(x)$denotes the$t$-bounded Kolmogorov complexity of the truthtable described by$x$. Our main theorem shows that for an appropriate notion of mild average-case hardness, for every$\varepsilon>0$, polynomial$t(n) \geq (1+\varepsilon)n$, and every `nice'' class ... more >>> TR08-104 | 23rd November 2008 Madhur Tulsiani #### CSP Gaps and Reductions in the Lasserre Hierarchy We study integrality gaps for SDP relaxations of constraint satisfaction problems, in the hierarchy of SDPs defined by Lasserre. Schoenebeck recently showed the first integrality gaps for these problems, showing that for MAX k-XOR, the ratio of the SDP optimum to the integer optimum may be as large as ... more >>> TR19-013 | 31st January 2019 Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami #### CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations We study the complexity of Boolean constraint satisfaction problems (CSPs) when the assignment must have Hamming weight in some congruence class modulo$M$, for various choices of the modulus$M$. Due to the known classification of tractable Boolean CSPs, this mainly reduces to the study of three cases: 2SAT, HornSAT, ... more >>> TR16-205 | 22nd December 2016 Amey Bhangale, Irit Dinur, Inbal Livni Navon #### Cube vs. Cube Low Degree Test We revisit the Raz-Safra plane-vs.-plane test and study the closely related cube vs. cube test. In this test the tester has access to a "cubes table" which assigns to every cube a low degree polynomial. The tester randomly selects two cubes (affine sub-spaces of dimension$3$) that intersect on a ... more >>> TR18-160 | 12th September 2018 Anna Gal, Avishay Tal, Adrian Trejo Nuñez #### Cubic Formula Size Lower Bounds Based on Compositions with Majority We define new functions based on the Andreev function and prove that they require$n^{3}/polylog(n)\$ formula size to compute. The functions we consider are generalizations of the Andreev function using compositions with the majority function. Our arguments apply to composing a hard function with any function that agrees with the ... more >>>

TR23-005 | 13th January 2023
Paul Beame, Niels Kornerup

#### Cumulative Memory Lower Bounds for Randomized and Quantum Computation

Cumulative memory---the sum of space used over the steps of a computation---is a fine-grained measure of time-space complexity that is a more accurate measure of cost for algorithms with infrequent spikes in memory usage in the context of technologies such as cloud computing that allow dynamic allocation and de-allocation of ... more >>>

TR08-037 | 29th February 2008
Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo

#### Curves That Must Be Retraced

Revisions: 1

We exhibit a polynomial time computable plane curve GAMMA that has finite length, does not intersect itself, and is smooth except at one endpoint, but has the following property. For every computable parametrization f of GAMMA and every positive integer n, there is some positive-length subcurve of GAMMA that f ... more >>>

ISSN 1433-8092 | Imprint