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

__
TR17-003
| 24th November 2016
__

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

Revisions: 1

__
TR14-159
| 27th November 2014
__

A. C. Cem Say, Abuzer Yakaryilmaz#### Magic coins are useful for small-space quantum machines

__
TR14-173
| 13th December 2014
__

Igor Carboni Oliveira, Rahul Santhanam#### Majority is incompressible by AC$^0[p]$ circuits

Revisions: 1

__
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

__
TR06-003
| 8th January 2006
__

Joshua Buresh-Oppenheim, Rahul Santhanam#### Making Hard Problems Harder

__
TR97-014
| 25th April 1997
__

Klaus Reinhardt, Eric Allender#### Making Nondeterminism Unambiguous

__
TR12-037
| 10th April 2012
__

Alexander A. Sherstov#### Making Polynomials Robust to Noise

__
TR10-104
| 29th June 2010
__

Paul Beame, Widad Machmouchi#### Making RAMs Oblivious Requires Superlogarithmic Overhead

Revisions: 3
,
Comments: 1

__
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

__
TR16-052
| 7th April 2016
__

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

Revisions: 1

__
TR02-034
| 18th April 2002
__

Andrei Bulatov#### Mal'tsev constraints are tractable

__
TR04-097
| 2nd November 2004
__

Víctor Dalmau#### Malt'sev Constraints made Simple

__
TR10-023
| 23rd February 2010
__

Adam Klivans, Homin Lee, Andrew Wan#### Mansour’s Conjecture is True for Random DNF Formulas

Revisions: 3

__
TR11-133
| 4th October 2011
__

Maurice Jansen, Rahul Santhanam#### Marginal Hitting Sets Imply Super-Polynomial Lower Bounds for Permanent

__
TR05-045
| 12th April 2005
__

Philippe Moser#### Martingale Families and Dimension in P

Revisions: 1

__
TR12-107
| 30th August 2012
__

Brendan Juba, Ryan Williams#### Massive Online Teaching to Bounded Learners

__
TR13-048
| 27th March 2013
__

Jin-Yi Cai, Aaron Gorenstein#### Matchgates Revisited

__
TR19-175
| 4th December 2019
__

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

__
TR10-012
| 27th January 2010
__

Zeev Dvir, Parikshit Gopalan, Sergey Yekhanin#### Matching Vector Codes

Revisions: 1

__
TR13-061
| 17th April 2013
__

Zeev Dvir, Guangda Hu#### Matching-Vector Families and LDCs Over Large Modulo

__
TR21-130
| 7th September 2021
__

Srinivasan Arunachalam, João F. Doriguello#### Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case

__
TR22-042
| 31st March 2022
__

Vikraman Arvind, Pushkar Joglekar#### Matrix Polynomial Factorization via Higman Linearization

__
TR15-079
| 7th May 2015
__

Oded Goldreich, Avishay Tal#### Matrix Rigidity of Random Toeplitz Matrices

__
TR21-121
| 21st August 2021
__

Sumanta Ghosh, Rohit Gurjar#### Matroid Intersection: A pseudo-deterministic parallel reduction from search to weighted-decision

__
TR97-039
| 11th September 1997
__

Pierluigi Crescenzi, Luca Trevisan#### MAX NP-Completeness Made Easy

__
TR11-099
| 11th July 2011
__

Anant Jindal, Gazal Kochar, Manjish Pal#### Maximum Matchings via Glauber Dynamics

Revisions: 1
,
Comments: 1

__
TR04-040
| 4th May 2004
__

Venkatesan Guruswami, Alexander Vardy#### Maximum-likelihood decoding of Reed-Solomon codes is NP-hard

__
TR20-082
| 23rd May 2020
__

Yuval Filmus, Meena Mahajan, Gaurav Sood, Marc Vinyals#### MaxSAT Resolution and Subcube Sums

Revisions: 2

__
TR10-197
| 14th December 2010
__

Albert Atserias, Elitza Maneva#### Mean-payoff games and propositional proofs

__
TR14-057
| 17th April 2014
__

Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar#### Measure of Non-pseudorandomness and Deterministic Extraction of Pseudorandomness

Revisions: 3

__
TR02-065
| 26th November 2002
__

Olivier Powell#### Measure on P revisited

__
TR95-028
| 9th June 1995
__

Eric Allender, Martin Strauss#### Measure on P: Robustness of the Notion

__
TR94-004
| 12th December 1994
__

Eric Allender, Martin Strauss#### Measure on Small Complexity Classes, with Applications for BPP

__
TR00-076
| 24th August 2000
__

Juraj Hromkovic, Juhani Karhumaki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert#### Measures of Nondeterminism in Finite Automata

__
TR05-004
| 3rd January 2005
__

Leslie G. Valiant#### Memorization and Association on a Realistic Neural Model

__
TR15-126
| 27th July 2015
__

Jacob Steinhardt, Gregory Valiant, Stefan Wager#### Memory, Communication, and Statistical Queries

Revisions: 1

__
TR11-092
| 2nd June 2011
__

Doerr Benjamin, Winzen Carola#### Memory-Restricted Black-Box Complexity

__
TR23-018
| 1st March 2023
__

Qipeng Liu, Ran Raz, Wei Zhan#### Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory

__
TR05-151
| 7th December 2005
__

Magnus Bordewich, Martin Dyer, Marek Karpinski#### Metric Construction, Stopping Times and Path Coupling.

__
TR16-128
| 13th August 2016
__

Irit Dinur#### Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover

__
TR21-152
| 8th November 2021
__

Gal Arnon, Tomer Grossman#### Min-Entropic Optimality

__
TR09-008
| 15th January 2009
__

Stasys Jukna, Georg Schnitger#### Min-Rank Conjecture for Log-Depth Circuits

__
TR03-002
| 13th December 2002
__

Stefan Szeider#### Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable

Revisions: 1

__
TR02-054
| 5th September 2002
__

Detlef Sieling#### Minimization of Decision Trees is Hard to Approximate

__
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

__
TR15-045
| 1st April 2015
__

Benny Applebaum, Yuval Ishai, Eyal Kushilevitz#### Minimizing Locality of One-Way Functions via Semi-Private Randomized Encodings

Revisions: 1

__
TR17-158
| 23rd October 2017
__

Eric Allender, Joshua Grochow, Dieter van Melkebeek, Cris Moore, Andrew Morgan#### Minimum Circuit Size, Graph Isomorphism, and Related Problems

__
TR13-057
| 5th April 2013
__

Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman#### Mining Circuit Lower Bound Proofs for Meta-Algorithms

__
TR17-017
| 5th February 2017
__

Michal Moshkovitz, Dana Moshkovitz#### Mixing Implies Lower Bounds for Space Bounded Learning

__
TR17-116
| 5th July 2017
__

Michal Moshkovitz, Dana Moshkovitz#### Mixing Implies Strong Lower Bounds for Space Bounded Learning

__
TR21-017
| 19th February 2021
__

Timothy Gowers, Emanuele Viola#### Mixing in non-quasirandom groups

__
TR21-142
| 1st October 2021
__

Amey Bhangale, Prahladh Harsha, Sourya Roy#### Mixing of 3-term progressions in Quasirandom Groups

__
TR09-111
| 5th November 2009
__

Walid Gomaa#### Model-Theoretic Characterization of Complexity Classes

__
TR05-120
| 14th October 2005
__

Sashka Davis, Russell Impagliazzo#### Models of Greedy Algorithms for Graph Problems

__
TR96-001
| 10th January 1996
__

Manindra Agrawal, Richard Beigel, Thomas Thierauf#### Modulo Information from Nonadaptive Queries to NP

__
TR13-008
| 7th January 2013
__

Adam Klivans, Raghu Meka#### Moment-Matching Polynomials

__
TR21-018
| 20th February 2021
__

Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil Vadhan#### Monotone Branching Programs: Pseudorandomness and Circuit Complexity

Revisions: 1

__
TR17-175
| 13th November 2017
__

Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov#### Monotone Circuit Lower Bounds from Resolution

Revisions: 1

__
TR20-181
| 4th December 2020
__

Bruno Pasqualotto Cavalar, Mrinal Kumar, Benjamin Rossman#### Monotone Circuit Lower Bounds from Robust Sunflowers

Revisions: 2

__
TR11-121
| 12th September 2011
__

Oded Goldreich, Rani Izsak#### Monotone Circuits: One-Way Functions versus Pseudorandom Generators

__
TR02-007
| 14th January 2002
__

Pavel Pudlak#### Monotone complexity and the rank of matrices

Comments: 1

__
TR09-135
| 10th December 2009
__

Zeev Dvir, Avi Wigderson#### Monotone expanders - constructions and applications

__
TR15-171
| 28th October 2015
__

Joshua Grochow#### Monotone projection lower bounds from extended formulation lower bounds

Revisions: 2
,
Comments: 1

__
TR00-008
| 20th January 2000
__

Albert Atserias, Nicola Galesi, Ricard Gavaldà#### Monotone Proofs of the Pigeon Hole Principle

__
TR11-025
| 19th February 2011
__

Yang Li#### Monotone Rank and Separations in Computational Complexity

Revisions: 1
,
Comments: 1

__
TR00-087
| 14th November 2000
__

Albert Atserias, Nicola Galesi, Pavel Pudlak#### Monotone simulations of nonmonotone propositional proofs

__
TR10-048
| 24th March 2010
__

David García Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briet#### Monotonicity Testing and Shortest-Path Routing on the Cube

__
TR19-133
| 2nd October 2019
__

Nutan Limaye, Srikanth Srinivasan, Utkarsh Tripathi#### More on $AC^0[\oplus]$ and Variants of the Majority Function

Revisions: 1

__
TR17-167
| 3rd November 2017
__

Chin Ho Lee, Emanuele Viola#### More on bounded independence plus noise: Pseudorandom generators for read-once polynomials

Revisions: 1

__
TR18-025
| 1st February 2018
__

Olaf Beyersdorff, Judith Clymo#### More on Size and Width in QBF Resolution

__
TR22-093
| 28th June 2022
__

Joshua Cook#### More Verifier Efficient Interactive Protocols For Bounded Space

Revisions: 4

__
TR17-097
| 31st May 2017
__

Itay Berman, Akshay Degwekar, Ron Rothblum, Prashant Nalini Vasudevan#### Multi Collision Resistant Hash Functions and their Applications

Revisions: 1

__
TR15-015
| 30th January 2015
__

Neeraj Kayal, Chandan Saha#### Multi-$k$-ic depth three circuit lower bound

__
TR17-099
| 5th June 2017
__

Nir Bitansky, Omer Paneth, Yael Tauman Kalai#### Multi-Collision Resistance: A Paradigm for Keyless Hash Functions

Revisions: 2

__
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

__
TR19-012
| 27th January 2019
__

Oded Goldreich#### Multi-pseudodeterministic algorithms

Revisions: 1

__
TR14-149
| 10th November 2014
__

Kai-Min Chung, Xin Li, Xiaodi Wu#### Multi-Source Randomness Extractors Against Quantum Side Information, and their Applications

__
TR13-011
| 10th January 2013
__

Nader Bshouty#### Multilinear Complexity is Equivalent to Optimal Tester Size

__
TR03-079
| 8th November 2003
__

Scott Aaronson#### Multilinear Formulas and Skepticism of Quantum Computing

__
TR07-085
| 2nd September 2007
__

Ran Raz, Amir Yehudayoff#### Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors

__
TR04-042
| 21st May 2004
__

Ran Raz#### Multilinear-$NC_1$ $\ne$ Multilinear-$NC_2$

__
TR08-082
| 11th September 2008
__

Paul Beame, Trinh Huynh#### Multiparty Communication Complexity and Threshold Circuit Size of AC^0

Revisions: 2

__
TR08-061
| 11th June 2008
__

Paul Beame, Trinh Huynh#### Multiparty Communication Complexity of AC^0

Revisions: 1

__
TR08-002
| 19th December 2007
__

Arkadev Chattopadhyay, Anil Ada#### Multiparty Communication Complexity of Disjointness

Revisions: 3

__
TR20-017
| 18th February 2020
__

Alexander Kozachinskiy, Vladimir Podolskii#### Multiparty Karchmer-Wigderson Games and Threshold Circuits

Revisions: 1

__
TR16-160
| 26th October 2016
__

Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen#### Multiplayer parallel repetition for expander games

Revisions: 1

__
TR95-017
| 27th March 1995
__

Claudia Bertram, Thomas Hofmeister#### Multiple Product Modulo Arbitrary Numbers

__
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

__
TR06-006
| 16th December 2005
__

Alexander Shen#### Multisource algorithmic information theory

__
TR08-096
| 8th September 2008
__

Andrew Drucker#### Multitask Efficiencies in the Decision Tree Model

__
TR10-202
| 9th December 2010
__

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

__
TR23-025
| 10th March 2023
__

Vikraman Arvind, Pushkar Joglekar#### Multivariate to Bivariate Reduction for Noncommutative Polynomial Factorization

__
TR14-133
| 15th October 2014
__

Adam Case, Jack H. Lutz#### Mutual Dimension

__
TR23-079
| 31st May 2023
__

Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich#### Mutual Empowerment between Circuit Obfuscation and Circuit Minimization

__
TR94-021
| 12th December 1994
__

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

Christian Glaßer, Stephen Travers

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

Yi Deng

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

A. C. Cem Say, Abuzer Yakaryilmaz

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

Igor Carboni Oliveira, Rahul Santhanam

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

Lijie Chen, Zhenjian Lu, Xin Lyu, Igor Carboni Oliveira

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

Joshua Buresh-Oppenheim, Rahul Santhanam

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

Klaus Reinhardt, Eric Allender

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

Alexander A. Sherstov

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

Paul Beame, Widad Machmouchi

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

Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer

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 ecient, but can still be used in many of these applications.

Using the new code we obtain exponential improvements over several ...
more >>>

Gil Cohen

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

Andrei Bulatov

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

Víctor Dalmau

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

more >>>Adam Klivans, Homin Lee, Andrew Wan

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

Maurice Jansen, Rahul Santhanam

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

Philippe Moser

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

Brendan Juba, Ryan Williams

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

Jin-Yi Cai, Aaron Gorenstein

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

Emanuele Viola

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.

Zeev Dvir, Parikshit Gopalan, Sergey Yekhanin

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

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

Srinivasan Arunachalam, João F. Doriguello

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

Vikraman Arvind, Pushkar Joglekar

In continuation to our recent work on noncommutative

polynomial factorization, we consider the factorization problem for

matrices of polynomials and show the following results.

\begin{itemize}

\item Given as input a full rank $d\times d$ matrix $M$ whose entries

$M_{ij}$ are polynomials in the free noncommutative ring

more >>>

Oded Goldreich, Avishay Tal

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

Sumanta Ghosh, Rohit Gurjar

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

Pierluigi Crescenzi, Luca Trevisan

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

Anant Jindal, Gazal Kochar, Manjish Pal

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

Venkatesan Guruswami, Alexander Vardy

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

Yuval Filmus, Meena Mahajan, Gaurav Sood, Marc Vinyals

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

Albert Atserias, Elitza Maneva

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

Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar

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

Olivier Powell

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

Eric Allender, Martin Strauss

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

Eric Allender, Martin Strauss

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

Juraj Hromkovic, Juhani Karhumaki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert

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

Leslie G. Valiant

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

Jacob Steinhardt, Gregory Valiant, Stefan Wager

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

Doerr Benjamin, Winzen Carola

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 >>>Qipeng Liu, Ran Raz, Wei Zhan

In a work by Raz (J. ACM and FOCS 16), it was proved that any algorithm for parity learning on $n$ bits requires either $\Omega(n^2)$ bits of classical memory or an exponential number (in~$n$) of random samples. A line of recent works continued that research direction and showed that for ... more >>>

Magnus Bordewich, Martin Dyer, Marek Karpinski

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

Irit Dinur

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

Gal Arnon, Tomer Grossman

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

Stasys Jukna, Georg Schnitger

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

Stefan Szeider

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

Detlef Sieling

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

Eric Allender, Lisa Hellerstein, Paul McCabe, Michael Saks

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

Benny Applebaum, Yuval Ishai, Eyal Kushilevitz

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

Eric Allender, Joshua Grochow, Dieter van Melkebeek, Cris Moore, Andrew Morgan

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

Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman

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

Michal Moshkovitz, Dana Moshkovitz

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

Michal Moshkovitz, Dana Moshkovitz

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

Timothy Gowers, Emanuele Viola

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

Amey Bhangale, Prahladh Harsha, Sourya Roy

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

Walid Gomaa

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

Sashka Davis, Russell Impagliazzo

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

Manindra Agrawal, Richard Beigel, Thomas Thierauf

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

Adam Klivans, Raghu Meka

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

Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil Vadhan

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

Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov

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

Bruno Pasqualotto Cavalar, Mrinal Kumar, Benjamin Rossman

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

Oded Goldreich, Rani Izsak

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

Pavel Pudlak

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

Zeev Dvir, Avi Wigderson

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

Joshua Grochow

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

Albert Atserias, Nicola Galesi, Ricard Gavaldà

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

Yang Li

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

Albert Atserias, Nicola Galesi, Pavel Pudlak

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 >>>David García Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briet

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

Nutan Limaye, Srikanth Srinivasan, Utkarsh Tripathi

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

Chin Ho Lee, Emanuele Viola

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

Olaf Beyersdorff, Judith Clymo

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

Joshua Cook

Let $\mathbf{TISP}[T, S]$, $\mathbf{BPTISP}[T, S]$, $\mathbf{NTISP}[T, S]$, and $\mathbf{CoNTISP}[T, S]$ be the set of languages recognized by deterministic, randomized, nondeterminsitic, and co-nondeterministic algorithms, respectively, running in time $T$ and space $S$. Let $\mathbf{ITIME}[T_V]$ be the set of languages recognized by an interactive protocol where the verifier runs in time $T_V$. ... more >>>

Itay Berman, Akshay Degwekar, Ron Rothblum, Prashant Nalini Vasudevan

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

Neeraj Kayal, Chandan Saha

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

Nir Bitansky, Omer Paneth, Yael Tauman Kalai

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

Andrej Muchnik, Alexej Semenov

Ran Raz

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

Oded Goldreich

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

Kai-Min Chung, Xin Li, Xiaodi Wu

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

Nader Bshouty

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

Scott Aaronson

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

Ran Raz, Amir Yehudayoff

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

Ran Raz

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

Paul Beame, Trinh Huynh

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

Paul Beame, Trinh Huynh

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

Arkadev Chattopadhyay, Anil Ada

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

Alexander Kozachinskiy, Vladimir Podolskii

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

Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen

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

Claudia Bertram, Thomas Hofmeister

We consider the threshold circuit complexity of computing

the multiple product modulo m in threshold circuits.

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

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

Alexander Shen

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

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

Bin Fu

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

Vikraman Arvind, Pushkar Joglekar

Based on a theorem of Bergman we show that multivariate noncommutative polynomial factorization is deterministic polynomial-time reducible to the factorization of bivariate noncommutative polynomials. More precisely, we show the following:

(1) In the white-box setting, given an n-variate noncommutative polynomial f in F over a field F (either a ... more >>>

Adam Case, Jack H. Lutz

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

Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich

We study close connections between Indistinguishability Obfuscation ($IO$) and the Minimum Circuit Size Problem ($MCSP$), and argue that algorithms for one of $MCSP$ or $IO$ would empower the other one. Some of our main results are:

\begin{itemize}

\item If there exists a perfect (imperfect) $IO$ that is computationally secure ...
more >>>

Lance Fortnow

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.