Hong Kong TheoryFest 2016

Tue 20 Dec, 2016 @ CUHK

Speakers

Program

9:30 - 10:00Coffee
10:00 - 11:00Lap Chi Lau: Approximating Unique Games in Minor-Closed Graph Families
11:00 - 12:00Elchanan Mossel: Reconstruction of Graphical Models: Algorithms, Information Theory and Complexity
12:30 - 2:30Lunch
2:30 - 3:30Amnon Ta-Shma: An Efficient Reduction from Non-malleable to Two-source Extractors: Achieving Near-logarithmic Min-entropy
3:30 - 4:30Luca Trevisan: Know Your Place: Simple Distributed Graph-Partitioning Algorithms

Information

Venue
ERB1009 William M. W. Mong Engineering Building, The Chinese University of Hong Kong
Registration
Please email itcsc@cuhk.edu.hk with your first name, last name, email, university and whether you will join the complementary lunch. To reserve car parking for the event, please let us know your car plate number by 13 Dec, 2016
Contact
For enquiry, please email us at itcsc@cuhk.edu.hk

Talks

Lap Chi Lau
Approximating Unique Games in Minor-Closed Graph Families

We present approximation algorithms for the Unique Games Problem in minor-closed graph families. As a corollary, this implies an improved approximation algorithm for the min-uncut problem in these graphs. The algorithms are based on low diameter graph decomposition.

The talk will be self-contained. I will begin with an introduction of the Unique Games Conjecture and also low diameter graph decomposition.

Joint work with Vedat Alev.

Elchanan Mossel
Reconstruction of Graphical Models: Algorithms, Information Theory and Complexity

TBA

Amnon Ta-Shma
An Efficient Reduction from Non-malleable to Two-source Extractors: Achieving Near-logarithmic Min-entropy

The breakthrough result of Chattopadhyay and Zuckerman gives a reduction from the construction of explicit non-malleable extractors to the construction of explicit two-source extractors and bipartite Ramsey graphs. However, even assuming the existence of optimal explicit non-malleable extractors only gives a two-source extractor (or a Ramsey graph) for poly(log n) entropy, rather than the optimal O(log n).

In this paper we modify the construction to solve the above barrier. Using the currently best explicit non-malleable extractors we get an explicit bipartite Ramsey graphs for sets of size 2k, for k=O(log n loglog n). Any further improvement in the construction of non-malleable extractors would immediately yield a corresponding two-source extractor.

Intuitively, Chattopadhyay and Zuckerman use an extractor as a sampler, and we observe that one could use a weaker object — a somewhere-random condenser with a small entropy gap and a very short seed. We also show how to explicitly construct this weaker object using the error reduction technique of Raz et. al., and the constant degree dispersers of Zuckerman that also work against extremely small tests.

This is joint work with Avraham Ben-Aroya and Dean Doron

Luca Trevisan
Know Your Place: Simple Distributed Graph-Partitioning Algorithms

We study network distributed processes of the following type: each node, independently, picks an initial state according to a certain distribution, then nodes repeatedly exchange information about their states with some or all of their neighbors. At each iteration, each node, based on its state, assigns itself to a cluster.

We show that a synchronous discrete-time algorithm of this sort (in which, at each time step, all nodes communicate their state to all neighbors) converges to the partition found by a centralized spectral partitioning algorithms, and we discuss preliminary results concerning an asynchronous continuous-time version of the algorithm (in which, at Poisson intervals, two adjacent nodes along a random edge exchange information about their states).

(Joint work with Luca Becchetti, Andrea Clementi, Francesco Pasquale, Prasad Raghavendra, and Emanuele Natale)

Header photo by Gary Elsasser CC BY-NC