Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Michael Saks:

TR17-009 | 19th January 2017
Joshua Grochow, Mrinal Kumar, Michael Saks, Shubhangi Saraf

Towards an algebraic natural proofs barrier via polynomial identity testing

We observe that a certain kind of algebraic proof - which covers essentially all known algebraic circuit lower bounds to date - cannot be used to prove lower bounds against VP if and only if what we call succinct hitting sets exist for VP. This is analogous to the Razborov-Rudich ... more >>>

TR16-026 | 20th February 2016
Anindya De, Michael Saks, Sijian Tang

Noisy population recovery in polynomial time

In the noisy population recovery problem of Dvir et al., the goal is to learn
an unknown distribution $f$ on binary strings of length $n$ from noisy samples. For some parameter $\mu \in [0,1]$,
a noisy sample is generated by flipping each coordinate of a sample from $f$ independently with
more >>>

TR15-047 | 2nd April 2015
Swastik Kopparty, Mrinal Kumar, Michael Saks

Efficient indexing of necklaces and irreducible polynomials over finite fields

We study the problem of indexing irreducible polynomials over finite fields, and give the first efficient algorithm for this problem. Specifically, we show the existence of poly(n, log q)-size circuits that compute a bijection between {1, ... , |S|} and the set S of all irreducible, monic, univariate polynomials of ... more >>>

TR14-064 | 24th April 2014
Arkadev Chattopadhyay, Michael Saks

The Power of Super-logarithmic Number of Players

In the `Number-on-Forehead' (NOF) model of multiparty communication, the input is a $k \times m$ boolean matrix $A$ (where $k$ is the number of players) and Player $i$ sees all bits except those in the $i$-th row, and the players communicate by broadcast in order to evaluate a specified ... more >>>

TR12-051 | 25th April 2012
Dmitry Gavinsky, Shachar Lovett, Michael Saks, Srikanth Srinivasan

A Tail Bound for Read-k Families of Functions

We prove a Chernoff-like large deviation bound on the sum of non-independent random variables that have the following dependence structure. The variables $Y_1,\ldots,Y_r$ are arbitrary Boolean functions of independent random variables $X_1,\ldots,X_m$, modulo a restriction that every $X_i$ influences at most $k$ of the variables $Y_1,\ldots,Y_r$.

more >>>

TR09-010 | 29th January 2009
Nikos Leonardos, Michael Saks

Lower bounds on the randomized communication complexity of read-once functions

We prove lower bounds on the randomized two-party communication complexity of functions that arise from read-once boolean formulae.

A read-once boolean formula is a formula in propositional logic with the property that every variable appears exactly once. Such a formula can be represented by a tree, where the leaves correspond ... more >>>

TR05-126 | 5th November 2005
Eric Allender, Lisa Hellerstein, Paul McCabe, Michael Saks

Minimizing DNF Formulas and AC0 Circuits Given a Truth Table

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

TR02-002 | 3rd January 2002
Howard Barnum, Michael Saks

A lower bound on the quantum query complexity of read-once functions

We establish a lower bound of $\Omega{(\sqrt{n})}$ on the bounded-error quantum query complexity of read-once Boolean functions, providing evidence for the conjecture that $\Omega(\sqrt{D(f)})$ is a lower bound for all Boolean functions.Our technique extends a result of Ambainis, based on the idea that successful computation of a function requires ``decoherence'' ... more >>>

TR00-025 | 20th May 2000
Paul Beame, Michael Saks, Xiaodong Sun, Erik Vee

Super-linear time-space tradeoff lower bounds for randomized computation

We prove the first time-space lower bound tradeoffs for randomized
computation of decision problems. The bounds hold even in the
case that the computation is allowed to have arbitrary probability
of error on a small fraction of inputs. Our techniques are an
extension of those used by Ajtai in his ... more >>>

TR99-010 | 1st April 1999
Eric Allender, Igor E. Shparlinski, Michael Saks

A Lower Bound for Primality

Comments: 1

Recent work by Bernasconi, Damm and Shparlinski
proved lower bounds on the circuit complexity of the square-free
numbers, and raised as an open question if similar (or stronger)
lower bounds could be proved for the set of prime numbers. In
this short note, we answer this question ... more >>>

TR98-053 | 30th August 1998
Paul Beame, Michael Saks, Jayram S. Thathachar

Time-Space Tradeoffs for Branching Programs

Comments: 1

We obtain the first non-trivial time-space tradeoff lower bound for
functions f:{0,1}^n ->{0,1} on general branching programs by exhibiting a
Boolean function f that requires exponential size to be computed by any
branching program of length cn, for some constant c>1. We also give the first
separation result between the ... more >>>

ISSN 1433-8092 | Imprint