Usual coordinates:
Friday, 2:15PM
Room 1314
Warren Weaver Hall
251 Mercer Street

Spring 2015 Schedule

Upcoming talks

Friday January 30
2:15PM
WWH 1314

Michael Kapralov (IBM Watson)

Sample-Optimal Fourier Sampling in Any Constant Dimension

Abstract: We present an algorithm that computes a k-sparse approximation to any signal from O(k\log N) Fourier measurements of a length N signal. This matches the known lower
bound of O(k \log(N/k)) up to constant factors for any k\leq N^{1-\delta}. The algorithm runs in near-linear time, and provides the so-called \ell_2/\ell_2 guarantee. Our algorithm extends to higher dimensions, leading to sample complexity of O_d(k\log N), which is again optimal up to constant factors for any constant d. This is the first sample optimal algorithm for these problems.

Using similar techniques, we also obtain an algorithm with slightly suboptimal sample complexity O(k\log N (\log\log N)^2) and a sub-linear time O(k \log^{O(1)} N) for any constant d. This generalizes the result of [IKP] to higher dimensions.

We also present preliminary experimental evaluation of our sample-optimal near-linear time algorithm, indicating that the empirical sampling complexity of the algorithm is comparable to that of other recovery methods known in the literature, while providing strong provable guarantees on the recovery quality.

(joint work with Piotr Indyk)

Friday February 6
2:15PM
WWH 1314

Ofer Shayevitz (Tel Aviv University)

An Upper Bound on the Sizes of Multiset-Union-Free Families

Abstract: Two families of subsets of [n] are called multiset-union-free
if all their pairwise multiset unions are distinct. Despite much effort
over the years, not much is known on the largest possible sizes of such families,
and a wide gap remains between the best known constructions and upper bounds.
In this work we derive a new upper bound on the sizes of families that possess this property,
improving a result by Urbanke and Li. To that end, we introduce a soft variation of the
Sauer-Perles-Shelah Lemma, that is then used in conjunction with an information-theoretic
argument for a more general setup.

Joint work with Or Ordentlich.

Friday February 13
2:15PM
WWH 1314

Elliot Anshelevich (RPI)

Stable Matching, Friendship, and Altruism

Abstract: We will discuss both integral and fractional versions of "correlated stable matching"
problems. Each player is a node in a social network and strives to form a good match with a
neighboring player; the player utilities from forming a match are correlated. We consider
the existence, computation, and inefficiency of stable matchings from which no pair of players
wants to deviate. We especially focus on networks where players are embedded in a social context,
and may incorporate friendship relations or altruism into their decisions.

When the benefits from a match are the same for both players, we show that incorporating the
well-being of other players into their matching decisions significantly decreases the price of
stability, while the price of anarchy remains unaffected. Furthermore, a good stable matching
achieving the price of stability bound always exists and can be reached in polynomial time. We
extend these results to more general matching rewards, when players matched to each other may
receive different utilities from the match. For this more general case, we show that incorporating
social context (i.e., "caring about your friends") can make an even larger difference, and greatly
reduce the price of anarchy. Finally, we extend most of our results to network contribution games,
in which players can decide how much effort to contribute to each incident edge, instead of simply
choosing a single node to match with.

Friday March 13
2:15PM
WWH 1314

Justin Thaler (Yahoo! Labs)

TBD

Abstract: TBD

Friday March 27
2:15PM
WWH 1314

Michael Forbes (IAS)

Dimension Expanders via Rank Condensers

Abstract: Expander graphs are sparse graphs with good connectivity properties and they have
become ubiquitous in theoretical computer science. Dimension expanders are a linear-algebraic
variant where we ask for a constant number of linear maps that expand subspaces of a vector space
(instead of subsets of vertices). After their definition 10 years ago by Barak, Impagliazzo, Shpilka
and Wigderson there are now two constructions of constant-degree dimension expanders, both of which
suggest dimension expanders are more complicated than expander graphs.

In this work, we give a new construction of constant-degree dimension expanders (over large fields)
which is quite simple. It follows from an emerging theory of linear-algebraic pseudorandomness where
the rank of a subspace plays the role of the min-entropy of a random variable. In particular, we use
the recent near-optimal construction of subspace designs by Guruswami and Kopparty (based on Wronskians)
to construct a near optimal "lossy rank condenser". This condenser, in addition to a tensoring operation,
yields the desired dimension expanders.