All reports by Author Rani Izsak:

__
TR14-103
| 8th August 2014
__

Uriel Feige, Michal Feldman, Nicole Immorlica, Rani Izsak, Lucier Brendan, Vasilis Syrgkanis#### A Unifying Hierarchy of Valuations with Complements and Substitutes

__
TR13-095
| 24th June 2013
__

Uriel Feige, Rani Izsak#### Welfare Maximization and the Supermodular Degree

__
TR11-121
| 12th September 2011
__

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

Uriel Feige, Michal Feldman, Nicole Immorlica, Rani Izsak, Lucier Brendan, Vasilis Syrgkanis

We introduce a new hierarchy over monotone set functions, that we refer to as $MPH$ (Maximum over Positive Hypergraphs).

Levels of the hierarchy correspond to the degree of complementarity in a given function.

The highest level of the hierarchy, $MPH$-$m$ (where $m$ is the total number of items) captures all ...
more >>>

Uriel Feige, Rani Izsak

Given a set of items and a collection of players, each with a nonnegative monotone valuation set function over the items,

the welfare maximization problem requires that every item be allocated to exactly one player,

and one wishes to maximize the sum of values obtained by the players,

as computed ...
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 >>>