Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR13-095 | 24th June 2013
Uriel Feige, Rani Izsak

Welfare Maximization and the Supermodular Degree

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

TR11-121 | 12th September 2011
Oded Goldreich, Rani Izsak

Monotone Circuits: One-Way Functions versus Pseudorandom Generators

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

ISSN 1433-8092 | Imprint