All reports by Author Michael Saks:

__
TR22-074
| 20th May 2022
__

Michael Saks, Rahul Santhanam#### On Randomized Reductions to the Random Strings

__
TR17-009
| 19th January 2017
__

Joshua Grochow, Mrinal Kumar, Michael Saks, Shubhangi Saraf#### Towards an algebraic natural proofs barrier via polynomial identity testing

__
TR16-026
| 20th February 2016
__

Anindya De, Michael Saks, Sijian Tang#### Noisy population recovery in polynomial time

__
TR15-047
| 2nd April 2015
__

Swastik Kopparty, Mrinal Kumar, Michael Saks#### Efficient indexing of necklaces and irreducible polynomials over finite fields

__
TR14-064
| 24th April 2014
__

Arkadev Chattopadhyay, Michael Saks#### The Power of Super-logarithmic Number of Players

__
TR12-051
| 25th April 2012
__

Dmytro Gavinsky, Shachar Lovett, Michael Saks, Srikanth Srinivasan#### A Tail Bound for Read-k Families of Functions

__
TR09-010
| 29th January 2009
__

Nikos Leonardos, Michael Saks#### Lower bounds on the randomized communication complexity of read-once functions

__
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

__
TR02-002
| 3rd January 2002
__

Howard Barnum, Michael Saks#### A lower bound on the quantum query complexity of read-once functions

__
TR00-025
| 20th May 2000
__

Paul Beame, Michael Saks, Xiaodong Sun, Erik Vee#### Super-linear time-space tradeoff lower bounds for randomized computation

__
TR99-010
| 1st April 1999
__

Eric Allender, Igor E. Shparlinski, Michael Saks#### A Lower Bound for Primality

Comments: 1

__
TR98-053
| 30th August 1998
__

Paul Beame, Michael Saks, Jayram S. Thathachar#### Time-Space Tradeoffs for Branching Programs

Comments: 1

Michael Saks, Rahul Santhanam

We study the power of randomized polynomial-time non-adaptive reductions to the problem of approximating Kolmogorov complexity and its polynomial-time bounded variants.

As our first main result, we give a sharp dichotomy for randomized non-adaptive reducibility to approximating Kolmogorov complexity. We show that any computable language $L$ that has a randomized ... more >>>

Joshua Grochow, Mrinal Kumar, Michael Saks, Shubhangi Saraf

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

Anindya De, Michael Saks, Sijian Tang

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

Swastik Kopparty, Mrinal Kumar, Michael Saks

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

Arkadev Chattopadhyay, Michael Saks

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

Dmytro Gavinsky, Shachar Lovett, Michael Saks, Srikanth Srinivasan

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 >>>Nikos Leonardos, Michael Saks

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

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

Howard Barnum, Michael Saks

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

Paul Beame, Michael Saks, Xiaodong Sun, Erik Vee

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

Eric Allender, Igor E. Shparlinski, Michael Saks

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

Paul Beame, Michael Saks, Jayram S. Thathachar

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