Under the auspices of the Computational Complexity Foundation (CCF)

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

M
TR05-147 | 5th December 2005
Christian Glaßer, Stephen Travers

#### Machines that can Output Empty Words

We propose the e-model for leaf languages which generalizes the known balanced and unbalanced concepts. Inspired by the neutral behavior of rejecting paths of NP machines, we allow transducers to output empty words.

The paper explains several advantages of the new model. A central aspect is that it allows us ... more >>>

TR17-003 | 24th November 2016
Yi Deng

#### Magic Adversaries Versus Individual Reduction: Science Wins Either Way

Revisions: 1

We prove that \emph{at least} one of the following statements is true:

-- (Infinitely-often) Public-key encryption and key agreement can be based on injective one-way functions;
-- For every inverse polynomial $\epsilon$, the 4-round protocol from [Feige and Shamir, STOC 90] is distributional concurrent zero knowledge for any ... more >>>

TR14-159 | 27th November 2014
A. C. Cem Say, Abuzer Yakaryilmaz

#### Magic coins are useful for small-space quantum machines

Although polynomial-time probabilistic Turing machines can utilize uncomputable transition probabilities to recognize uncountably many languages with bounded error when allowed to use logarithmic space, it is known that such magic coins'' give no additional computational power to constant-space versions of those machines. We show that adding a few quantum bits ... more >>>

TR14-173 | 13th December 2014
Igor Carboni Oliveira, Rahul Santhanam

#### Majority is incompressible by AC$^0[p]$ circuits

Revisions: 1

We consider $\cal C$-compression games, a hybrid model between computational and communication complexity. A $\cal C$-compression game for a function $f \colon \{0,1\}^n \to \{0,1\}$ is a two-party communication game, where the first party Alice knows the entire input $x$ but is restricted to use strategies computed by $\cal C$-circuits, ... more >>>

TR21-040 | 15th March 2021
Lijie Chen, Zhenjian Lu, Xin Lyu, Igor Carboni Oliveira

#### Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC1

We develop a general framework that characterizes strong average-case lower bounds against circuit classes $\mathcal{C}$ contained in $\mathrm{NC}^1$, such as $\mathrm{AC}^0[\oplus]$ and $\mathrm{ACC}^0$. We apply this framework to show:

- Generic seed reduction: Pseudorandom generators (PRGs) against $\mathcal{C}$ of seed length $\leq n -1$ and error $\varepsilon(n) = n^{-\omega(1)}$ can ... more >>>

TR06-003 | 8th January 2006
Joshua Buresh-Oppenheim, Rahul Santhanam

#### Making Hard Problems Harder

We consider a general approach to the hoary problem of (im)proving circuit lower bounds. We define notions of hardness condensing and hardness extraction, in analogy to the corresponding notions from the computational theory of randomness. A hardness condenser is a procedure that takes in a Boolean function as input, as ... more >>>

TR97-014 | 25th April 1997
Klaus Reinhardt, Eric Allender

#### Making Nondeterminism Unambiguous

We show that in the context of nonuniform complexity,
nondeterministic logarithmic space bounded computation can be made
unambiguous. An analogous result holds for the class of problems
reducible to context-free languages. In terms of complexity classes,
this can be stated as:
NL/poly = UL/poly
LogCFL/poly ... more >>>

TR12-037 | 10th April 2012
Alexander A. Sherstov

#### Making Polynomials Robust to Noise

A basic question in any computational model is how to reliably compute a given function when the inputs or intermediate computations are subject to noise at a constant rate. Ideally, one would like to use at most a constant factor more resources compared to the noise-free case. This question has ... more >>>

TR10-104 | 29th June 2010

#### Making RAMs Oblivious Requires Superlogarithmic Overhead

We prove a time-space tradeoff lower bound of $T = \Omega\left(n\log(\frac{n}{S}) \log \log(\frac{n}{S})\right)$ for
randomized oblivious branching programs to compute $1GAP$, also
known as the pointer jumping problem, a problem for which there is a
simple deterministic time $n$ and space $O(\log n)$ RAM (random
access machine) algorithm.

In ... more >>>

TR11-142 | 2nd November 2011
Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer

#### Making the long code shorter, with applications to the Unique Games Conjecture

Revisions: 1

The long code is a central tool in hardness of approximation, especially in
questions related to the unique games conjecture. We construct a new code that
is exponentially more ecient, but can still be used in many of these applications.
Using the new code we obtain exponential improvements over several ... more >>>

TR16-052 | 7th April 2016
Gil Cohen

#### Making the Most of Advice: New Correlation Breakers and Their Applications

Revisions: 1

A typical obstacle one faces when constructing pseudorandom objects is undesired correlations between random variables. Identifying this obstacle and constructing certain types of "correlation breakers" was central for recent exciting advances in the construction of multi-source and non-malleable extractors. One instantiation of correlation breakers is correlation breakers with advice. These ... more >>>

TR02-034 | 18th April 2002
Andrei Bulatov

#### Mal'tsev constraints are tractable

A wide variety of combinatorial problems can be represented in the form of the Constraint Satisfaction Problem (CSP). The general CSR is known to be NP-complete, however, some restrictions on the possible form of constraints may lead to a tractable subclass. Jeavons and coauthors have shown that the complexity of ... more >>>

TR04-097 | 2nd November 2004
Víctor Dalmau

We give in this paper a different and simpler proof of the tractability of Mal'tsev contraints.

more >>>

TR10-023 | 23rd February 2010
Adam Klivans, Homin Lee, Andrew Wan

#### Mansour’s Conjecture is True for Random DNF Formulas

Revisions: 3

In 1994, Y. Mansour conjectured that for every DNF formula on $n$ variables with $t$ terms there exists a polynomial $p$ with $t^{O(\log (1/\epsilon))}$ non-zero coefficients such that $\E_{x \in \{0,1\}}[(p(x)-f(x))^2] \leq \epsilon$. We make the first progress on this conjecture and show that it is true for several natural ... more >>>

TR11-133 | 4th October 2011
Maurice Jansen, Rahul Santhanam

#### Marginal Hitting Sets Imply Super-Polynomial Lower Bounds for Permanent

Suppose $f$ is a univariate polynomial of degree $r=r(n)$ that is computed by a size $n$ arithmetic circuit.
It is a basic fact of algebra that a nonzero univariate polynomial of degree $r$ can vanish on at most $r$ points. This implies that for checking whether $f$ is identically zero, ... more >>>

TR05-045 | 12th April 2005
Philippe Moser

#### Martingale Families and Dimension in P

Revisions: 1

We introduce a new measure notion on small complexity classes (called F-measure), based on martingale families,
that get rid of some drawbacks of previous measure notions:
martingale families can make money on all strings,
and yield random sequences with an equal frequency of 0's and 1's.
As applications to F-measure,
more >>>

TR12-107 | 30th August 2012
Brendan Juba, Ryan Williams

#### Massive Online Teaching to Bounded Learners

We consider a model of teaching in which the learners are consistent and have bounded state, but are otherwise arbitrary. The teacher is non-interactive and massively open'': the teacher broadcasts a sequence of examples of an arbitrary target concept, intended for every possible on-line learning algorithm to learn from. We ... more >>>

TR13-048 | 27th March 2013
Jin-Yi Cai, Aaron Gorenstein

#### Matchgates Revisited

We study a collection of concepts and theorems that laid the foundation of matchgate computation. This includes the signature theory of planar matchgates, and the parallel theory of characters of not necessarily planar matchgates. Our aim is to present a unified and, whenever possible, simplified account of this challenging theory. ... more >>>

TR19-175 | 4th December 2019
Emanuele Viola

#### Matching Smolensky's correlation bound with majority

We show that there are degree-$d$ polynomials over $\mathbb{F}_{2}$ with
correlation $\Omega(d/\sqrt{n})$ with the majority function on $n$
bits. This matches the $O(d/\sqrt{n})$ bound by Smolensky.

more >>>

TR10-012 | 27th January 2010
Zeev Dvir, Parikshit Gopalan, Sergey Yekhanin

#### Matching Vector Codes

Revisions: 1

An $(r,\delta,\epsilon)$-locally decodable code encodes a $k$-bit message $x$ to an $N$-bit codeword $C(x),$ such that for every $i\in [k],$ the $i$-th message bit can be recovered with probability $1-\epsilon,$ by a randomized decoding procedure that reads only $r$ bits, even if the codeword $C(x)$ is corrupted in up to ... more >>>

TR13-061 | 17th April 2013
Zeev Dvir, Guangda Hu

We prove new upper bounds on the size of families of vectors in $\Z_m^n$ with restricted modular inner products, when $m$ is a large integer. More formally, if $\vec{u}_1,\ldots,\vec{u}_t \in \Z_m^n$ and $\vec{v}_1,\ldots,\vec{v}_t \in \Z_m^n$ satisfy $\langle\vec{u}_i,\vec{v}_i\rangle\equiv0\pmod m$ and $\langle\vec{u}_i,\vec{v}_j\rangle\not\equiv0\pmod m$ for all $i\neq j\in[t]$, we prove that $t \leq ... more >>> TR21-130 | 7th September 2021 Srinivasan Arunachalam, João F. Doriguello #### Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case Hypercontractive inequalities for real-valued functions over the Boolean cube play an important role in theoretical computer science. In this work, we prove a hypercontractive inequality for matrix-valued functions defined over large alphabets, generalizing the result of Ben-Aroya, Regev, de Wolf (FOCS'08) for the Boolean alphabet. To obtain our result we ... more >>> TR15-079 | 7th May 2015 Oded Goldreich, Avishay Tal #### Matrix Rigidity of Random Toeplitz Matrices We prove that random$n$-by-$n$Toeplitz (alternatively Hankel) matrices over$GF(2)$have rigidity$\Omega(\frac{n^3}{r^2\log n})$for rank$r \ge \sqrt{n}$, with high probability. This improves, for$r = o(n/\log n \log\log n)$, over the$\Omega(\frac{n^2}{r} \cdot\log(\frac{n}{r}))$bound that is known for many explicit matrices. Our result implies that the explicit ... more >>> TR21-121 | 21st August 2021 Sumanta Ghosh, Rohit Gurjar #### Matroid Intersection: A pseudo-deterministic parallel reduction from search to weighted-decision We study the matroid intersection problem from the parallel complexity perspective. Given two matroids over the same ground set, the problem asks to decide whether they have a common base and its search version asks to find a common base, if one exists. Another widely studied variant is the weighted ... more >>> TR97-039 | 11th September 1997 Pierluigi Crescenzi, Luca Trevisan #### MAX NP-Completeness Made Easy We introduce a simple technique to obtain reductions between optimization constraint satisfaction problems. The technique uses the probabilistic method to reduce the size of disjunctions. As a first application, we prove the MAX NP-completeness of MAX 3SAT without using the PCP theorem (thus solving an open ... more >>> TR11-099 | 11th July 2011 Anant Jindal, Gazal Kochar, Manjish Pal #### Maximum Matchings via Glauber Dynamics Revisions: 1 , Comments: 1 In this paper we study the classic problem of computing a maximum cardinality matching in general graphs$G = (V, E)$. This problem has been studied extensively more than four decades. The best known algorithm for this problem till date runs in$O(m \sqrt{n})$time due to Micali and Vazirani ... more >>> TR04-040 | 4th May 2004 Venkatesan Guruswami, Alexander Vardy #### Maximum-likelihood decoding of Reed-Solomon codes is NP-hard Maximum-likelihood decoding is one of the central algorithmic problems in coding theory. It has been known for over 25 years that maximum-likelihood decoding of general linear codes is NP-hard. Nevertheless, it was so far unknown whether maximum- likelihood decoding remains hard for any specific family of more >>> TR20-082 | 23rd May 2020 Yuval Filmus, Meena Mahajan, Gaurav Sood, Marc Vinyals #### MaxSAT Resolution and Subcube Sums Revisions: 1 We study the MaxRes rule in the context of certifying unsatisfiability. We show that it can be exponentially more powerful than tree-like resolution, and when augmented with weakening (the system MaxResW), p-simulates tree-like resolution. In devising a lower bound technique specific to MaxRes (and not merely inheriting lower bounds from ... more >>> TR10-197 | 14th December 2010 Albert Atserias, Elitza Maneva #### Mean-payoff games and propositional proofs We associate a CNF-formula to every instance of the mean-payoff game problem in such a way that if the value of the game is non-negative the formula is satisfiable, and if the value of the game is negative the formula has a polynomial-size refutation in$\Sigma_2$-Frege (i.e.~DNF-resolution). This reduces mean-payoff ... more >>> TR14-057 | 17th April 2014 Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar #### Measure of Non-pseudorandomness and Deterministic Extraction of Pseudorandomness Revisions: 3 In this paper, we propose a quantification of distributions on a set of strings, in terms of how close to pseudorandom the distribution is. The quantification is an adaptation of the theory of dimension of sets of infinite sequences first introduced by Lutz \cite{Lutz:DISS}. We show that this definition ... more >>> TR02-065 | 26th November 2002 Olivier Powell #### Measure on P revisited We revisit the problem of generalising Lutz's resource bounded measure (rbm) to small complexity classes. We propose a definition of a perfect rbm on P, and give sufficient and necessary conditions for such a measure to exist. We also revisit$\mu_\tau$, an rbm for P defined in previous articles (c.f. ... more >>> TR95-028 | 9th June 1995 Eric Allender, Martin Strauss #### Measure on P: Robustness of the Notion In (Allender and Strauss, FOCS '95), we defined a notion of measure on the complexity class P (in the spirit of the work of (Lutz, JCSS '92) that provides a notion of measure on complexity classes at least as large as E, and the work of (Mayordomo, Phd. ... more >>> TR94-004 | 12th December 1994 Eric Allender, Martin Strauss #### Measure on Small Complexity Classes, with Applications for BPP We present a notion of resource-bounded measure for P and other subexponential-time classes. This generalization is based on Lutz's notion of measure, but overcomes the limitations that cause Lutz's definitions to apply only to classes at least as large as E. We present many of the basic properties of this ... more >>> TR00-076 | 24th August 2000 Juraj Hromkovic, Juhani Karhumaki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert #### Measures of Nondeterminism in Finite Automata While deterministic finite automata seem to be well understood, surprisingly many important problems concerning nondeterministic finite automata (nfa's) remain open. One such problem area is the study of different measures of nondeterminism in finite automata and the estimation of the sizes of minimal nondeterministic finite automata. In this paper the ... more >>> TR05-004 | 3rd January 2005 Leslie G. Valiant #### Memorization and Association on a Realistic Neural Model A central open question of computational neuroscience is to identify the data structures and algorithms that are used in mammalian cortex to support successive acts of the basic cognitive tasks of memorization and association. This paper addresses the simultaneous challenges of realizing these two distinct tasks with the same data ... more >>> TR15-126 | 27th July 2015 Jacob Steinhardt, Gregory Valiant, Stefan Wager #### Memory, Communication, and Statistical Queries Revisions: 1 If a concept class can be represented with a certain amount of memory, can it be efficiently learned with the same amount of memory? What concepts can be efficiently learned by algorithms that extract only a few bits of information from each example? We introduce a formal framework for studying ... more >>> TR11-092 | 2nd June 2011 Doerr Benjamin, Winzen Carola #### Memory-Restricted Black-Box Complexity We show that the black-box complexity with memory restriction one of the$n$-dimensional$\onemax$function class is at most$2n$. This disproves the$\Theta(n \log n)$conjecture of Droste, Jansen, and Wegener (Theory of Computing Systems 39 (2006) 525--544). more >>> TR05-151 | 7th December 2005 Magnus Bordewich, Martin Dyer, Marek Karpinski #### Metric Construction, Stopping Times and Path Coupling. In this paper we examine the importance of the choice of metric in path coupling, and the relationship of this to \emph{stopping time analysis}. We give strong evidence that stopping time analysis is no more powerful than standard path coupling. In particular, we prove a stronger theorem for path coupling ... more >>> TR16-128 | 13th August 2016 Irit Dinur #### Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover We show that if gap-3SAT has no sub-exponential time algorithms then a weak form of the sliding scale conjecture holds. Namely, for every$\alpha>0$any algorithm for$n^\alpha$-approximating the value of label cover must run in time at least$n^{\Omega(\exp(1/\alpha))}$, where$n$is the size of the instance. Put differently, ... more >>> TR21-152 | 8th November 2021 Gal Arnon, Tomer Grossman #### Min-Entropic Optimality We introduce the notion of \emph{Min-Entropic Optimality} thereby providing a framework for arguing that a given algorithm computes a function better than any other algorithm. An algorithm is$k(n)$Min-Entropic Optimal if for every distribution$D$with min-entropy at least$k(n)$, its expected running time when its input is drawn ... more >>> TR09-008 | 15th January 2009 Stasys Jukna, Georg Schnitger #### Min-Rank Conjecture for Log-Depth Circuits A completion of an m-by-n matrix A with entries in {0,1,*} is obtained by setting all *-entries to constants 0 or 1. A system of semi-linear equations over GF(2) has the form Mx=f(x), where M is a completion of A and f:{0,1}^n --> {0,1}^m is an operator, the i-th coordinate ... more >>> TR03-002 | 13th December 2002 Stefan Szeider #### Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable Revisions: 1 The deficiency of a propositional formula F in CNF with n variables and m clauses is defined as m-n. It is known that minimal unsatisfiable formulas (unsatisfiable formulas which become satisfiable by removing any clause) have positive deficiency. Recognition of minimal unsatisfiable formulas is NP-hard, and it was shown recently ... more >>> TR02-054 | 5th September 2002 Detlef Sieling #### Minimization of Decision Trees is Hard to Approximate Decision trees are representations of discrete functions with widespread applications in, e.g., complexity theory and data mining and exploration. In these areas it is important to obtain decision trees of small size. The minimization problem for decision trees is known to be NP-hard. In this paper the problem is shown ... more >>> TR05-126 | 5th November 2005 Eric Allender, Lisa Hellerstein, Paul McCabe, Michael Saks #### Minimizing DNF Formulas and AC0 Circuits Given a Truth Table Comments: 2 For circuit classes R, the fundamental computational problem, Min-R, asks for the minimum R-size of a boolean function presented as a truth table. Prominent examples of this problem include Min-DNF, and Min-Circuit (also called MCSP). We begin by presenting a new reduction proving that Min-DNF is NP-complete. It is significantly ... more >>> TR15-045 | 1st April 2015 Benny Applebaum, Yuval Ishai, Eyal Kushilevitz #### Minimizing Locality of One-Way Functions via Semi-Private Randomized Encodings Revisions: 1 A one-way function is$d$-local if each of its outputs depends on at most$d$input bits. In (Applebaum, Ishai, and Kushilevitz, FOCS 2004) it was shown that, under relatively mild assumptions, there exist$4$-local one-way functions (OWFs). This result is not far from optimal as it is not hard ... more >>> TR17-158 | 23rd October 2017 Eric Allender, Joshua Grochow, Dieter van Melkebeek, Cris Moore, Andrew Morgan #### Minimum Circuit Size, Graph Isomorphism, and Related Problems We study the computational power of deciding whether a given truth-table can be described by a circuit of a given size (the Minimum Circuit Size Problem, or MCSP for short), and of the variant denoted as MKTP where circuit size is replaced by a polynomially-related Kolmogorov measure. All prior reductions ... more >>> TR13-057 | 5th April 2013 Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman #### Mining Circuit Lower Bound Proofs for Meta-Algorithms We show that circuit lower bound proofs based on the method of random restrictions yield non-trivial compression algorithms for easy'' Boolean functions from the corresponding circuit classes. The compression problem is defined as follows: given the truth table of an$n$-variate Boolean function$f$computable by some unknown small circuit ... more >>> TR17-017 | 5th February 2017 Michal Moshkovitz, Dana Moshkovitz #### Mixing Implies Lower Bounds for Space Bounded Learning One can learn any hypothesis class$H$with$O(\log|H|)$labeled examples. Alas, learning with so few examples requires saving the examples in memory, and this requires$|X|^{O(\log|H|)}$memory states, where$X$is the set of all labeled examples. A question that arises is how many labeled examples are needed in ... more >>> TR17-116 | 5th July 2017 Michal Moshkovitz, Dana Moshkovitz #### Mixing Implies Strong Lower Bounds for Space Bounded Learning With any hypothesis class one can associate a bipartite graph whose vertices are the hypotheses H on one side and all possible labeled examples X on the other side, and an hypothesis is connected to all the labeled examples that are consistent with it. We call this graph the hypotheses ... more >>> TR21-017 | 19th February 2021 Timothy Gowers, Emanuele Viola #### Mixing in non-quasirandom groups We initiate a systematic study of mixing in non-quasirandom groups. Let$A$and$B$be two independent, high-entropy distributions over a group$G$. We show that the product distribution$AB$is statistically close to the distribution$F(AB)$for several choices of$G$and$F$, including: (1)$G$is the affine ... more >>> TR21-142 | 1st October 2021 Amey Bhangale, Prahladh Harsha, Sourya Roy #### Mixing of 3-term progressions in Quasirandom Groups In this note, we show the mixing of three-term progressions$(x, xg, xg^2)$in every finite quasirandom group, fully answering a question of Gowers. More precisely, we show that for any$D$-quasirandom group$G$and any three sets$A_1, A_2, A_3 \subset G$, we have \[ \left|\Pr_{x,y\sim G}\left[ x \in ... more >>> TR09-111 | 5th November 2009 Walid Gomaa #### Model-Theoretic Characterization of Complexity Classes Model theory is a branch of mathematical logic that investigates the logical properties of mathematical structures. It has been quite successfully applied to computational complexity resulting in an area of research called descriptive complexity theory. Descriptive complexity is essentially a syntactical characterization of complexity classes using logical formalisms. However, there ... more >>> TR05-120 | 14th October 2005 Sashka Davis, Russell Impagliazzo #### Models of Greedy Algorithms for Graph Problems Borodin, Nielsen, and Rackoff gave a model of greedy-like algorithms for scheduling problems and Angelopoulos and Borodin extended their work to facility location and set cover problems. We generalize their notion to include other optimization problems, and apply the generalized framework to graph problems. Our goal is to define an ... more >>> TR96-001 | 10th January 1996 Manindra Agrawal, Richard Beigel, Thomas Thierauf #### Modulo Information from Nonadaptive Queries to NP The classes of languages accepted by nondeterministic polynomial-time Turing machines (NP machines, in short) that have restricted access to an NP oracle --- the machines can ask k queries to the NP oracle and the answer they receive is the number of queries ... more >>> TR13-008 | 7th January 2013 Adam Klivans, Raghu Meka #### Moment-Matching Polynomials We give a new framework for proving the existence of low-degree, polynomial approximators for Boolean functions with respect to broad classes of non-product distributions. Our proofs use techniques related to the classical moment problem and deviate significantly from known Fourier-based methods, which require the underlying distribution to have some product ... more >>> TR21-018 | 20th February 2021 Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil Vadhan #### Monotone Branching Programs: Pseudorandomness and Circuit Complexity Revisions: 1 We study monotone branching programs, wherein the states at each time step can be ordered so that edges with the same labels never cross each other. Equivalently, for each fixed input, the transition functions are a monotone function of the state. We prove that constant-width monotone branching programs of ... more >>> TR17-175 | 13th November 2017 Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov #### Monotone Circuit Lower Bounds from Resolution Revisions: 1 For any unsatisfiable CNF formula$F$that is hard to refute in the Resolution proof system, we show that a gadget-composed version of$F$is hard to refute in any proof system whose lines are computed by efficient communication protocols---or, equivalently, that a monotone function associated with$F$has large ... more >>> TR20-181 | 4th December 2020 Bruno Pasqualotto Cavalar, Mrinal Kumar, Benjamin Rossman #### Monotone Circuit Lower Bounds from Robust Sunflowers Revisions: 1 Robust sunflowers are a generalization of combinatorial sunflowers that have applications in monotone circuit complexity, DNF sparsification, randomness extractors, and recent advances on the Erd\H{o}s-Rado sunflower conjecture. The recent breakthrough of Alweiss, Lovett, Wu and Zhang gives an improved bound on the maximum size of a$w$-set system that excludes ... more >>> TR11-121 | 12th September 2011 Oded Goldreich, Rani Izsak #### Monotone Circuits: One-Way Functions versus Pseudorandom Generators We study the computability of one-way functions and pseudorandom generators by monotone circuits, showing a substantial gap between the two: On one hand, there exist one-way functions that are computable by (uniform) polynomial-size monotone functions, provided (of course) that one-way functions exist at all. On the other hand, ... more >>> TR02-007 | 14th January 2002 Pavel Pudlak #### Monotone complexity and the rank of matrices Comments: 1 The rank of a matrix has been used a number of times to prove lower bounds on various types of complexity. In particular it has been used for the size of monotone formulas and monotone span programs. In most cases that this approach was used, there is not a single ... more >>> TR09-135 | 10th December 2009 Zeev Dvir, Avi Wigderson #### Monotone expanders - constructions and applications The main purpose of this work is to formally define monotone expanders and motivate their study with (known and new) connections to other graphs and to several computational and pseudorandomness problems. In particular we explain how monotone expanders of constant degree lead to: (1) Constant degree dimension expanders in finite ... more >>> TR15-171 | 28th October 2015 Joshua Grochow #### Monotone projection lower bounds from extended formulation lower bounds Revisions: 2 , Comments: 1 In this short note, we show that the permanent is not complete for non-negative polynomials in$VNP_{\mathbb{R}}$under monotone p-projections. In particular, we show that Hamilton Cycle polynomial and the cut polynomials are not monotone p-projections of the permanent. To prove this we introduce a new connection between monotone projections ... more >>> TR00-008 | 20th January 2000 Albert Atserias, Nicola Galesi, Ricard Gavaldà #### Monotone Proofs of the Pigeon Hole Principle We study the complexity of proving the Pigeon Hole Principle (PHP) in a monotone variant of the Gentzen Calculus, also known as Geometric Logic. We show that the standard encoding of the PHP as a monotone sequent admits quasipolynomial-size proofs in this system. This result is a consequence of ... more >>> TR11-025 | 19th February 2011 Yang Li #### Monotone Rank and Separations in Computational Complexity Revisions: 1 , Comments: 1 In the paper, we introduce the concept of monotone rank, and using it as a powerful tool, we obtain several important and strong separation results in computational complexity. \begin{itemize} \item We show a super-exponential separation between monotone and non-monotone computation in the non-commutative model, and thus give the answer to ... more >>> TR00-087 | 14th November 2000 Albert Atserias, Nicola Galesi, Pavel Pudlak #### Monotone simulations of nonmonotone propositional proofs We show that an LK proof of size$m$of a monotone sequent (a sequent that contains only formulas in the basis$\wedge,\vee$) can be turned into a proof containing only monotone formulas of size$m^{O(\log m)}$and with the number of proof lines polynomial in$m$. Also we show ... more >>> TR10-048 | 24th March 2010 David García Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briet #### Monotonicity Testing and Shortest-Path Routing on the Cube We study the problem of monotonicity testing over the hypercube. As previously observed in several works, a positive answer to a natural question about routing properties of the hypercube network would imply the existence of efficient monotonicity testers. In particular, if any$\ell$disjoint source-sink pairs on the directed hypercube ... more >>> TR19-133 | 2nd October 2019 Nutan Limaye, Srikanth Srinivasan, Utkarsh Tripathi #### More on$AC^0[\oplus]$and Variants of the Majority Function Revisions: 1 In this paper we prove two results about$AC^0[\oplus]$circuits. We show that for$d(N) = o(\sqrt{\log N/\log \log N})$and$N \leq s(N) \leq 2^{dN^{1/d^2}}$there is an explicit family of functions$\{f_N:\{0,1\}^N\rightarrow \{0,1\}\}$such that$f_N$has uniform$AC^0$formulas of depth$d$and size at ... more >>> TR17-167 | 3rd November 2017 Chin Ho Lee, Emanuele Viola #### More on bounded independence plus noise: Pseudorandom generators for read-once polynomials Revisions: 1 We construct pseudorandom generators with improved seed length for several classes of tests. First we consider the class of read-once polynomials over GF(2) in$m$variables. For error$\e$we obtain seed length$\tilde O (\log(m/\e)) \log(1/\e)$, where$\tilde O$hides lower-order terms. This is optimal up to the factor ... more >>> TR18-025 | 1st February 2018 Olaf Beyersdorff, Judith Clymo #### More on Size and Width in QBF Resolution In their influential paper Short proofs are narrow -- resolution made simple', Ben-Sasson and Wigderson introduced a crucial tool for proving lower bounds on the lengths of proofs in the resolution calculus. Over a decade later their technique for showing lower bounds on the size of proofs, by examining the ... more >>> TR17-097 | 31st May 2017 Itay Berman, Akshay Degwekar, Ron Rothblum, Prashant Nalini Vasudevan #### Multi Collision Resistant Hash Functions and their Applications Revisions: 1 Collision resistant hash functions are functions that shrink their input, but for which it is computationally infeasible to find a collision, namely two strings that hash to the same value (although collisions are abundant). In this work we study multi-collision resistant hash functions (MCRH) a natural relaxation of collision resistant ... more >>> TR15-015 | 30th January 2015 Neeraj Kayal, Chandan Saha #### Multi-$k$-ic depth three circuit lower bound In a multi-$k$-ic depth three circuit every variable appears in at most$k$of the linear polynomials in every product gate of the circuit. This model is a natural generalization of multilinear depth three circuits that allows the formal degree of the circuit to exceed the number of underlying variables ... more >>> TR17-099 | 5th June 2017 Nir Bitansky, Omer Paneth, Yael Tauman Kalai #### Multi-Collision Resistance: A Paradigm for Keyless Hash Functions Revisions: 2 We study multi-collision-resistant hash functions --- a natural relaxation of collision-resistant hashing that only guarantees the intractability of finding many (rather than two) inputs that map to the same image. An appealing feature of such hash functions is that unlike their collision-resistant counterparts, they do not necessarily require a key. ... more >>> TR00-015 | 16th February 2000 Andrej Muchnik, Alexej Semenov #### Multi-conditional Descriptions and Codes in Kolmogorov Complexity TR03-067 | 14th August 2003 Ran Raz #### Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size An arithmetic formula is multi-linear if the polynomial computed by each of its sub-formulas is multi-linear. We prove that any multi-linear arithmetic formula for the permanent or the determinant of an$n \times n$matrix is of size super-polynomial in$n$. more >>> TR19-012 | 27th January 2019 Oded Goldreich #### Multi-pseudodeterministic algorithms Revisions: 1 In this work, dedicated to Shafi Goldwasser, we consider a relaxation of the notion of pseudodeterministic algorithms, which was put forward by Gat and Goldwasser ({\em ECCC}, TR11--136, 2011). Pseudodeterministic algorithms are randomized algorithms that solve search problems by almost always providing the same canonical solution (per each input). ... more >>> TR14-149 | 10th November 2014 Kai-Min Chung, Xin Li, Xiaodi Wu #### Multi-Source Randomness Extractors Against Quantum Side Information, and their Applications We study the problem of constructing multi-source extractors in the quantum setting, which extract almost uniform random bits against quantum side information collected from several initially independent classical random sources. This is a natural generalization of seeded randomness extraction against quantum side information and classical independent source extraction. With new ... more >>> TR13-011 | 10th January 2013 Nader Bshouty #### Multilinear Complexity is Equivalent to Optimal Tester Size In this paper we first show that Tester for an$F$-algebra$A$and multilinear forms (see Testers and their Applications ECCC 2012) is equivalent to multilinear algorithm for the product of elements in$A$(see Algebraic complexity theory. vol. 315, Springer-Verlag). Our result is constructive in deterministic polynomial time. ... more >>> TR03-079 | 8th November 2003 Scott Aaronson #### Multilinear Formulas and Skepticism of Quantum Computing Several researchers, including Leonid Levin, Gerard 't Hooft, and Stephen Wolfram, have argued that quantum mechanics will break down before the factoring of large numbers becomes possible. If this is true, then there should be a natural "Sure/Shor separator" -- that is, a set of quantum ... more >>> TR07-085 | 2nd September 2007 Ran Raz, Amir Yehudayoff #### Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors We study multilinear formulas, monotone arithmetic circuits, maximal-partition discrepancy, best-partition communication complexity and extractors constructions. We start by proving lower bounds for an explicit polynomial for the following three subclasses of syntactically multilinear arithmetic formulas over the field C and the set of variables {x1,...,xn}: 1. Noise-resistant. A syntactically multilinear ... more >>> TR04-042 | 21st May 2004 Ran Raz #### Multilinear-$NC_1\ne$Multilinear-$NC_2$An arithmetic circuit or formula is multilinear if the polynomial computed at each of its wires is multilinear. We give an explicit example for a polynomial$f(x_1,...,x_n)$, with coefficients in$\{0,1\}$, such that over any field: 1)$f$can be computed by a polynomial-size multilinear circuit of depth$O(\log^2 ... more >>>

TR08-082 | 11th September 2008
Paul Beame, Trinh Huynh

#### Multiparty Communication Complexity and Threshold Circuit Size of AC^0

Revisions: 2

We prove an n^{Omega(1)}/2^{O(k)} lower bound on the randomized k-party communication complexity of read-once depth 4 AC^0 functions in the number-on-forehead (NOF) model for O(log n) players. These are the first non-trivial lower bounds for general NOF multiparty communication complexity for any AC^0 function for omega(log log n) players. For ... more >>>

TR08-061 | 11th June 2008
Paul Beame, Trinh Huynh

#### Multiparty Communication Complexity of AC^0

Revisions: 1

We prove n^Omega(1) lower bounds on the multiparty communication complexity of AC^0 functions in the number-on-forehead (NOF) model for up to Theta(log n) players. These are the first lower bounds for any AC^0 function for omega(loglog n) players. In particular we show that there are families of depth 3 read-once ... more >>>

TR08-002 | 19th December 2007

#### Multiparty Communication Complexity of Disjointness

Revisions: 3

We extend the 'Generalized Discrepancy' technique suggested by Sherstov to the Number on the Forehead' model of multiparty communication. This allows us to prove strong lower bounds of n^{\Omega(1)} on the communication needed by k players to compute the Disjointness function, provided $k$ is a constant. In general, our method ... more >>>

TR20-017 | 18th February 2020

#### Multiparty Karchmer-Wigderson Games and Threshold Circuits

Revisions: 1

We suggest a generalization of Karchmer-Wigderson communication games to the multiparty setting. Our generalization turns out to be tightly connected to circuits consisting of threshold gates. This allows us to obtain new explicit constructions of such circuits for several functions. In particular, we provide an explicit (polynomial-time computable) log-depth monotone ... more >>>

TR16-160 | 26th October 2016
Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen

#### Multiplayer parallel repetition for expander games

Revisions: 1

We investigate the value of parallel repetition of one-round games with any number of players $k\ge 2$. It has been an open question whether an analogue of Raz's Parallel Repetition Theorem holds for games with more than two players, i.e., whether the value of the repeated game decays exponentially ... more >>>

TR95-017 | 27th March 1995
Claudia Bertram, Thomas Hofmeister

#### Multiple Product Modulo Arbitrary Numbers

We consider the threshold circuit complexity of computing
the multiple product modulo m in threshold circuits.

more >>>

TR16-185 | 18th November 2016
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

#### Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere

Revisions: 1

We consider the following basic problem: given an $n$-variate degree-$d$ homogeneous polynomial $f$ with real coefficients, compute a unit vector $x \in \mathbb{R}^n$ that maximizes $|f(x)|$. Besides its fundamental nature, this problem arises in many diverse contexts ranging from tensor and operator norms to graph expansion to quantum information ... more >>>

TR06-006 | 16th December 2005
Alexander Shen

#### Multisource algorithmic information theory

Multisource information theory in Shannon setting is well known. In this article we try to develop its algorithmic information theory counterpart and use it as the general framework for many interesting questions about Kolmogorov complexity.

more >>>

TR08-096 | 8th September 2008
Andrew Drucker

#### Multitask Efficiencies in the Decision Tree Model

In Direct Sum problems [KRW], one tries to show that for a given computational model, the complexity of computing a collection $F = \{f_1(x_1), \ldots f_l(x_l)\}$ of finite functions on independent inputs is approximately the sum of their individual complexities. In this paper, by contrast, we study the diversity of ... more >>>

TR10-202 | 9th December 2010
Bin Fu

#### Multivariate Polynomial Integration and Derivative Are Polynomial Time Inapproximable unless P=NP

We investigate the complexity of integration and
derivative for multivariate polynomials in the standard computation
model. The integration is in the unit cube $[0,1]^d$ for a
multivariate polynomial, which has format
$f(x_1,\cdots, x_d)=p_1(x_1,\cdots, x_d)p_2(x_1,\cdots, x_d)\cdots p_k(x_1,\cdots, x_d)$,
where each $p_i(x_1,\cdots, x_d)=\sum_{j=1}^d q_j(x_j)$ with
all single variable polynomials $q_j(x_j)$ ... more >>>

TR14-133 | 15th October 2014

#### Mutual Dimension

We define the lower and upper mutual dimensions $mdim(x:y)$ and $Mdim(x:y)$ between any two points $x$ and $y$ in Euclidean space. Intuitively these are the lower and upper densities of the algorithmic information shared by $x$ and $y$. We show that these quantities satisfy the main desiderata for a satisfactory ... more >>>

TR94-021 | 12th December 1994
Lance Fortnow

#### My Favorite Ten Complexity Theorems of the Past Decade

We review the past ten years in computational complexity theory by
focusing on ten theorems that the author enjoyed the most. We use
each of the theorems as a springboard to discuss work done in
various areas of complexity theory.

more >>>

ISSN 1433-8092 | Imprint