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

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

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