We investigate the problem of monotonicity reconstruction, as defined in [3], in a distributed setting. We have oracle access to a nonnegative real-valued function f defined on domain [n] d =...
Andrew V. Goldberg, Andrew Wright, Jason D. Hartline, Michael Saks, Anna R. Karlin
We study a class of single-round, sealed-bid auctions for items in unlimited supply, such as digital goods. We introduce the notion of competitive auctions. A competitive auction is truthful (i.e.,...
Abstract Parallel Monotonicity Reconstruction (2008)
We investigate the problem of monotonicity reconstruction, as defined in [3], in a parallel setting. We have oracle access to a nonnegative real-valued function f defined on domain [n] d = {1,..., n}...
Andrew V. Goldberg, Jason D. Hartline, Michael Saks, Andrew Wright, Anna R. Karlin
We study a class of single-round, sealed-bid auctions for an item in unlimited supply, such as a digital good. We introduce the notion of competitive auctions. A competitive auction is truthful...
Optimal Separation of EROW and CROW PRAMs (2008)
Navin Goyal, Michael Saks, S. Venkatesh
Abstract We consider the problem of evaluating a booleanfunction on PRAMs. We exhibit a boolean function f: {0, 1}n! {0, 1} that can be evaluated in time O(log log n) in a deterministic CROW...
We answer in negative a question of Gál and Miltersen [3] about a combinatorial game arising in the study of timespace trade-offs for data structures.
[Computers and Society]: Electronic Commerce—payment (2008)
Weak monotonicity is a simple necessary condition for a social choice function to be implementable by a truthful mechanism. Roberts [10] showed that it is sufficient for all social choice functions...
We answer in negative a question of Gál and Miltersen [3] about a combinatorial game arising in the study of timespace trade-offs for data structures.
Eric Allender, Igor Shparlinski, Michael Saks
Recent work by Bernasconi, Damm and Shparlinski showed that the set of square-free numbers is not in AC 0, and raised as an open question if similar (or stronger) lower bounds could be proved for the...
Nathan Linial, Michael Saks, David Statter
Two sets are non-crossing if they are disjoint or one contains the other. The noncrossing graph NCn is the graph whose vertex set is the set of nonempty subsets of [n] ={1,...,n} with an edge between...
Andrew V. Goldberg, Jason D. Hartline, Michael Saks, Andrew Wright, Anna R. Karlin
We study a class of single-round, sealed-bid auctions for items in unlimited supply, such as digital goods. We introduce the notion of competitive auctions. A competitive auction is truthful (i.e.,...
Andrew V. Goldberg, Andrew Wright, Jason D. Hartline, Michael Saks, Anna R. Karlin
We study a class of single-round, sealed-bid auctions for items in unlimited supply, such as digital goods. We introduce the notion of competitive auctions. A competitive auction is truthful (i.e.,...
Michael Saks, Aravind Srinivasan, Shiyu Zhou, David Zuckerman
Motivated by a problem of filtering near-duplicate Web documents, Broder, Charikar, Frieze & Mitzenmacher defined the following notion of #-approximate min-wise independent permutation families....
Adapting to Asynchronous Dynamic Networks (2007)
Extend Ed, Baruch Awerbuch, Boaz Patt-shamir, David Peleg, Michael Saks
Baruch Awerbuch Boaz Patt-Shamir y David Peleg z Michael Saks x Abstract The computational power of different communication models is a fundamental question in the theory of distributed computation....
Paul Beame, Michael Saks, Jayram S. Thathachar
We obtain the first non-trivial time-space tradeo # lower bound for functions f: {0,
Paul Beame, Michael Saks, Jayram S. Thathachar
We obtain the first non-trivial time-space tradeo # lower bound for functions f: {0,
Bourgain [1] showed that every embedding of the complete binary tree of depth n into l 2 has metric distortion
On the Complexity of Some Arithmetic Problems over IF2[T] (2007)
Eric Allender, Anna Bernasconi, Carsten Damm, Michael Saks, Igor Shparlinski
In this paper, we study various combinatorial complexity characteristics of Boolean functions related to some natural arithmetic problems about polynomials over IF2. In particular, we consider the...
Discrete Localization and Correlation Inequalities for Set Functions (2007)
Laszlo Lovasz Michael, László Lovász, Michael Saks
Three theorems for set functions, closely related to the AhlswedeDaykin 4-function theorem (4FT), are proved. First, the conclusion of the 4FT is generalized to norms other than the L 1 norm....
Paul Beame, Richard Karp, Michael Saks
Abstract. We consider several problems related to the use of resolution-based methods for determining whether a given boolean formula in conjunctive normal form is satisable. First, building on work...
Avrim Blum, Howard Karloff, Michael Saks
We consider the problem faced by a mobile robot that has to reach a given target by traveling through an unmapped region in the plane containing oriented rectangular obstacles. We assume the robot...
Rounds vs Queries Trade-off in Noisy Computation (2006)
We show that a noisy parallel decision tree making O(n) queries needs Ω(log ∗ n) rounds to compute OR of n bits. This answers a question of Newman [IEEE Conference on Computational Complexity,...
Every decision tree has an influential variable (2005)
O'Donnell, Ryan, Saks, Michael, Schramm, Oded, Servedio, Rocco A.
We prove that for any decision tree calculating a boolean function $f:\{-1,1\}^n\to\{-1,1\}$, \[ \Var[f] \le \sum_{i=1}^n \delta_i \Inf_i(f), \] where $\delta_i$ is the probability that the $i$th...
Lower bounds for the noisy broadcast problem (2005)
Navin Goyal, Michael Saks, Guy Kindler
We prove the first non-trivial (super linear) lower bound in the noisy broadcast model, defined by El Gamal in [6]. In this model there are n + 1 processors P0, P1,..., Pn, each of which is initially...
Optimal Separation of EROW and CROW PRAMs (2005)
Navin Goyal, Michael Saks, S. Venkatesh
We consider the problem of evaluating a Boolean function on PRAMs. We exhibit a Boolean function f: {0, 1} n → {0, 1} that can be evaluated in time O(log log n) on a deterministic CROW (Concurrent...
Lower bounds for the noisy broadcast problem (2005)
Navin Goyal, Michael Saks, Guy Kindler
We prove the first non-trivial (super linear) lower bound in the noisy broadcast model, defined by El Gamal in [6]. In this model there are n + 1 processors P0, P1,..., Pn, each of which is initially...
Weak monotonicity suffices for truthfulness on convex domains (2005)
Weak monotonicity is a simple necessary condition for a social choice function to be implementable by a truthful mechanism. Roberts [10] showed that it is sufficient for all social choice functions...
A Lower Bound on the Competitive Ratio of Truthful Auctions (2004)
Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Michael Saks
Abstract We study a class of single-round, sealed-bid auctions for a set of identical items. We adopt the worst case competitive framework defined by [1,2] that compares the profit of an auction to...
A Lower Bound on the Competitive Ratio of Truthful Auctions (2004)
Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Michael Saks
Abstract We study a class of single-round, sealed-bid auctions for a set of identical items. We adopt the worst case competitive framework defined by [1,2] that compares the profit of an auction to...
The non-crossing graph Nathan Linial \Lambda (2004)
Abstract Two sets are non-crossing if they are disjoint or one contains the other. The non-crossing graph N Cn is the graph whose vertex set is the set of nonempty subsets of [n] = f1; : : : ; ng...
A lower bound on the quantum query complexity of read-once functions (2002)
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...
The efficiency of resolution and Davis-Putnam procedures (2002)
Paul Beame, Richard Karp, Toniann Pitassi, Michael Saks
We consider several problems related to the use of resolution-based methods for determining whether a given boolean formula in conjunctive normal form is satisfiable. First, building on work of...
Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Andrew Wright, Michael Saks
We study a class of single-round, sealed-bid auctions for items in unlimited supply, such as digital goods. We introduce the notion of competitive auctions. A competitive auction is truthful (i.e.,...
Super-linear time-space tradeoff lower bounds for randomized computation (2000)
Paul Beame, Michael Saks, Xiaodong Sun, Erik Vee
problems
Super-Linear Time-Space Tradeoff Lower Bounds for Randomized Computation (2000)
Paul Beame, Michael Saks, Xiaodong Sun, Erik Vee
We prove the first time-space lower bound tradeo#s for randomized computation of decision problems where computation error is allowed. Our techniques are an extension of those used by Ajtai [4, 5] in...
A dual version of Reimer’s inequality and a proof of Rudich’s conjecture (2000)
Jeff Kahn, Cliff Smyth, Michael Saks
We prove a dual version of the celebrated inequality of D. Reimer (a.k.a. the van den Berg-Kesten conjecture). We use the dual inequality to prove a combinatorialconjecture of S. Rudich motivated by...
Low discrepancy sets yield approximate min-wise independent permutation families (1999)
Michael Saks, Aravind Srinivasan, Shiyu Zhou, David Zuckerman
Motivated by a problem of filtering near-duplicate Web documents, Broder, Charikar, Frieze & Mitzenmacher defined the following notion of ffl-approximate min-wise independent permutation...
On List Update and Work Function Algorithms (1999)
Eric J. Anderson, Kris Hildrum, Anna R. Karlin, April Rasala, Michael Saks
. The list update problem, a well-studied problem in dynamic data structures, can be described abstractly as a metrical task system. In this paper, we prove that a generic metrical task system...
Alexander Russell Computer, Alexander Russell, Michael Saks, David Zuckerman
Collective coin-flipping is the problem of producing common random bits in a distributed computing environment with adversarial faults. We consider the perfect information model: all communication is...
A Lower Bound for Primality (1999)
Eric Allender Dept, Eric Allender, Michael Saks, Igor Shparlinski
Recent work by Bernasconi, Damm and Shparlinski showed that the set of square-free numbers is not in AC , and raised as an open question whether similar (or stronger) lower bounds could be proved for...
A Lower Bound for Primality (1999)
Eric Allender, Michael Saks, Igor Shparlinski
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...
Alexander Russell, Michael Saks, David Zuckerman
Collective coin-flipping is the problem of producing common random bits in a distributed computing environment with adversarial faults. We consider the perfect information model: all communication is...
Time-space tradeoffs for branching programs (1998)
Paul Beame, Michael Saks, Jayram S. Thathachar
We obtain the first non-trivial time-space tradeoff lower bound for functions f: f0; 1g
Explicit OR-Dispersers with Polylogarithmic Degree (1998)
Michael Saks, Aravind Srinivasan, Shiyu Zhou
An (N; M;T)-OR-disperser is a bipartite multigraph G = (V; W;E) with jV j = N , and jW j = M , having the following expansion property: any subset of V having at least T vertices has a neighbor set...
On the Complexity of Unsatisfiability Proofs for Random k-CNF Formulas (1997)
Paul Beame, Richard Karp, Toniann Pitassi, Michael Saks
We study the complexity of proving unsatisfiability for random k-CNF formulas with clause density D = m=n where m is number of clauses and n is the number of variables. We prove the first nontrivial...
Efficient Construction of a Small Hitting Set for Combinatorial Rectangles in High Dimension (1997)
Nathan Linial, Michael Luby, Michael Saks, David Zuckerman, Michael Saks
We describe a deterministic algorithm which, on input integers d, m and real number ffl 2 (0; 1), produces a subset S of [m] d = f1; 2; 3; : : : ; mg d that hits every combinatorial rectangle in [m]...
Randomization and derandomization in space-bounded computation (1996)
This is a survey of space-bounded probabilistic computation, summarizing the present state of knowledge about the relationships between the various complexity classes associated with such...
Randomized Robot Navigation Algorithms (1996)
Piotr Berman, Avrim Blum, Amos Fiat, Howard Karloff, Adi Rosén, Michael Saks
We consider the problem faced by a mobile robot that has to reach a given target by traveling through an unmapped region in the plane containing oriented rectangular obstacles. We assume the robot...
Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles (1996)
Roy Armoni, Michael Saks, Avi Wigderson, Shiyu Zhou
A common subproblem of DNF approximate counting and derandomizing RL is the discrepancy problem for combinatorial rectangles. We explicitly construct a poly(n)-size sample space that approximates the...
Discrepancy sets and pseudorandom generators for combinatorial rectangles (1996)
Roy Armoni, Michael Saks, Avi Wigderson, Shiyu Zhou
A common subproblem of DNF approximate counting and derandomizing RL is the discrepancy problem for combinatorial rectangles. We explicitly construct a poly(n)-size sample space that approximates the...
Local Management of a Global Resource in a Communication Network (1995)
Yehuda Afek, Baruch Awerbuch, Serge Plotkin, Michael Saks
This paper introduces a new distributed data object called Resource Controller which provides an abstraction for managing the consumption of a global resource in a distributed system. Examples of...
Products and Help Bits in Decision Trees (1994)
Noam Nisan, Steven Rudich, Michael Saks
We investigate two problems concerning the complexity of evaluating a function f at a k-tuple of unrelated inputs by k parallel decision tree algorithms. In the product problem, for some fixed depth...
Products and Help Bits in Decision Trees (1994)
Noam Nisan, Steven Rudich, Michael Saks
We investigate two problems concerning the complexity of evaluating a function f at a k-tuple of unrelated inputs by k parallel decision tree algorithms. In the product problem, for some fixed depth...
Abstract On the bandwidth of triangulated triangles* (1993)
Robert Hochberg A, Colin Mcdiarmid B, Michael Saks
We give a technique for obtaining a lower bound on the bandwidth of any planar graph with an embedding in which all bounded faces are triangles. This technique is applied to show that, for each...
Efficient Construction of a Small Hitting Set for Combinatorial Rectangles in High Dimension (1993)
Nati Linial, Michael Luby, Michael Saks, David Zuckerman
Given d, m and epsilon, we deterministically produce a sequence of points S that hits every combinatorial rectangle in [m]^d of volume at least epsilon. Both the running time of the algorithm and |S|...
Adapting to Asynchronous Dynamic Networks (Extended Abstract) (1992)
Baruch Awerbuch, Boaz Patt-shamir, David Peleg, Michael Saks
Baruch Awerbuch Boaz Patt-Shamir y David Peleg z Michael Saks x Abstract The computational power of different communication models is a fundamental question in the theory of distributed computation....
Local Management of a Global Resource in a Communication Network (1987)
Yehuda Afek Baruch, Baruch Awerbuch, Serge Plotkin, Michael Saks
This paper introduces a new distributed data object called Resource Controller which provides an abstraction for managing the consumption of a global resource in a distributed system. Examples of...
A phenomenological study of eight successful competitive men and women / (1980)
Thesis (Ph. D.)--California School of Professional Psychology, San Diego, 1980.