China Theory Week 2016

China Theory Week 2016 will take place from August 22 to 26 at The Chinese University of Hong Kong. The event is hosted by Institute of Theoretical Computer Science and Communications.

China Theory Week is an annual workshop for PhD students in the Theory of Computing from institutions worldwide to present and discuss their exciting research. It was founded in 2007 by Professor Andrew Chi-Chih Yao at Tsinghua University and was held in Beijing (2007, 2008, 2009, 2010, 2014), Aarhus (2011, 2012, 2013) and Shanghai (2015).

Workshop attendance is open but space is limited. If you would like to attend, please register by email with your name, institution, and contact email.

Organizing Committee

Header photo CC BY-NC by Gary Elsasser

Keynote Speakers


Talk Abstracts

Arturs Backurs
Which Regular Expression Patterns are Hard to Match?

Regular expressions constitute a fundamental notion in formal language theory and are frequently used in computer science to define search patterns. In particular, regular expression matching  and membership testing are widely used computational primitives, employed in many programming languages and text processing utilities. A classic algorithm for these problems constructs and simulates a non-deterministic finite automaton corresponding to the expression, resulting in an O(m n) running time (where m is the length of the pattern and n is the length of the text). This running time can be improved slightly (by a polylogarithmic factor), but no significantly faster solutions are known. At the same time, much faster algorithms exist for various special cases of regular expressions, including dictionary matching, wildcard matching, subset matching, word break problem etc.

In this paper, we show that the complexity of regular expression matching can be characterized based on its depth (when interpreted as a formula). Our results hold for expressions involving concatenation, OR, Kleene star and Kleene plus. For regular expressions of depth two (involving any combination of the above operators), we show the following dichotomy: matching and membership testing can be solved in near-linear time, except for “concatenations of stars”, which  cannot be solved in sub-quadratic time unless the Strong Exponential Time Hypothesis (SETH) is false. For regular expressions of depth three the picture is more complex. Nevertheless, we show that all problems can either be solved in strongly sub-quadratic time, or cannot be solved in sub-quadratic time unless SETH fails.

An intriguing special case of membership testing involves regular expressions of the form  “a star of an OR of concatenations”, e.g., [a|ab|bc]*. This corresponds to the so-called word break problem, for which a dynamic programming algorithm with a runtime of (roughly) O(n√m) is known. We show that the latter bound is not tight and improve the runtime to O(n m0.44…).

Fabrice Benhamouda
Diverse Modules and Zero-Knowledge in Cryptography

Smooth (or universal) projective hash functions (SPHFs) were first introduced by Cramer and Shoup, at Eurocrypt'02, as a tool to construct efficient encryption schemes satisfying a strong security property: indistinguishability under chosen-ciphertext attacks. Since then, they have found many other applications in cryptography, including password-authenticated key exchange, oblivious transfer, and blind signatures. They also enable an informer to send a message to a secret agent, so that only a real secret agent can read the message, but the informer has no way to be sure whether he was talking to a secret agent or an impostor.

SPHFs can be seen as implicit proofs of membership for certain languages. An important question is to characterize which languages they can handle. In this talk, we make a step forward towards this goal, by introducing diverse modules. A diverse module is a representation of a language, as a submodule of a larger module, where a module is essentially a vector space over a ring. Any diverse module directly yields an SPHF for the corresponding language, and almost all the known smooth projective hash functions are constructed this way. Furthermore, diverse modules can easily be combined to provide new applications of SPHFs, such as zero-knowledge arguments.

Greg Bodwin
Distance Preservers and Their Applications

A “distance preserver” of a graph G is a sparse subgraph whose distances agree with G for a given set of node pairs P. A famous example is BFS trees, which preserve all distances from a single source s to all other nodes V using O(n) edges. The central goal of distance preserver research is simply to determine how many edges are needed when the node pairs have some other structure besides P = {s} x V.

We will survey basic results and techniques in this area, as well as some very recent developments in the state of the art. We will also briefly discuss a successful line of research using distance preservers to understand spanners (subgraphs that approximately preserve all pairwise distances), and show how certain fundamental facts about distance preservers directly imply some surprising behaviors in the landscape of spanners.

Mark Bun
The Price of Online Queries in Differential Privacy

We consider the problem of answering queries about a sensitive dataset subject to differential privacy. The queries may be chosen adversarially from a larger set of allowable queries via one of three interactive models. These models capture whether the queries are given to the mechanism all in a single batch (“offline”), whether they are chosen in advance but presented to the mechanism one at a time (“online”), or whether they may be chosen by an analyst adaptively (“adaptive”).

Many differentially private mechanisms are just as efficient in the adaptive model as they are in the offline model. Meanwhile, most lower bounds for differential privacy hold in the offline setting. This suggests that the three models might be equivalent.

We prove that these models are all, in fact, distinct. Specifically, we show that there is a family of statistical queries such that exponentially more queries from this family can be answered in the offline model than in the online model. We also exhibit a family of search queries such that many more queries from this family can be answered in the online model than in the adaptive model. We also investigate whether such separations might hold for simple queries, such as threshold queries over the real line.

Joint work with Thomas Steinke and Jonathan Ullman.

Sarah Cannon
A Markov Chain Algorithm for Compression in Self-Organizing Particle Systems

Many programmable matter systems have been proposed and realized recently, each often tailored to a specific task or physical setting. In our work on self-organizing particle systems, we abstract away from specific settings and instead describe programmable matter as a collection of simple computational elements (called particles) with limited computational power that each perform fully distributed, local, asynchronous algorithms to solve system-wide problems of movement, configuration, and coordination. Here, we focus on the compression problem, where we seek fully distributed and asynchronous algorithms that lead the system to gather together as tightly as possible, that is, to converge to a configuration with small perimeter, where we measure the perimeter of a configuration by the length of the walk along the configuration boundary. We present a Markov chain based algorithm that solves the compression problem under the geometric amoebot model, using the triangular lattice as the underlying graph, for particle systems that begin in a connected configuration with no holes. The Markov chain M takes as input a bias parameter λ, where λ > 1 corresponds to particles favoring inducing more lattice triangles within the particle system. We prove that during the execution of M, the particles stay connected and no holes form. We furthermore prove M is a reversible and ergodic Markov chain, which leads to our main result: for all λ > 2 + √2, there is a constant α > 1 such that at stationarity the particles are α-compressed, meaning the perimeter of the particle configuration is at most α times the minimum perimeter for those particles. We additionally show λ > 1 is not enough to guarantee compression: for all 0 < λ < 2.17, there is a constant β < 1 such that the perimeter is at least a β fraction of the maximum perimeter.

Eshan Chattopadhyay
Explicit Constructions of Two-Source Extractors

Randomness is widely used in various areas of computer science, and many of the applications require uniform, uncorrelated bit. However, most sources of randomness in nature are defective and at best, only contain some amount of entropy. This leads to the area of randomness extraction, where an extractor is a deterministic procedure to produce pure random bits from a weak source. A central problem in this area is to extract from 2 independent weak sources (it is known that it is impossible to extract from just 1 weak source). This problem was raised by Chor and Goldreich, and Santha and Vazirani in the 80's.

In joint work with David Zuckerman, we resolve this problem. I will discuss the main ideas we use to solve this problem. Some of the ingredients that we use interestingly arise from cryptography and distributed computing. 

As a corollary of our 2-source extractor, we obtain explicit constructions of Ramsey graphs within quasi-polynomial factors of the existential bound proved by Erdos in 1947, in his seminal paper introducing the probabilistic method. This is in a line of work spanning the last 67 years in an attempt to meet Erdos' challenge of matching the probabilistic bound.

Xi Chen
On the Query Complexity of Boolean Monotonicity Testing

Monotonicity testing has been a touchstone problem in property testing for more than fifteen years, with many exciting recent developments in just the past few years. When specialized to Boolean-valued functions over {0,1}n, we are interested in the number of queries required to distinguish whether an unknown function is monotone or far from every monotone function. In this talk we discuss recent results on Boolean monotonicity testing and some related problems, focusing on the lower bound side.

Based on joint works with Anindya De, Rocco Servedio, Li-Yang Tan, Erik Waingarten, and Jinyu Xie.

Michael Cohen
Computing the Stationary Distribution

Given an explicit description of a Markov chain, we present a new algorithm to (approximately) compute its stationary distribution.  The traditional approaches to this problem involve either solving general systems of linear equations (taking nω time) or in some way simulating the Markov chain itself (giving a linear dependence on the mixing time of the Markov chain).  In contrast, our new approach has a subquadratic dependence on the size of the Markov chain and a polylogarithmic dependence on mixing time.  Our methods can also be used for other random walk problems, such as Personalized Page Rank and commute times.

Joint work with Jonathan Kelner, John Peebles, Richard Peng, Aaron Sidford, and Adrian Vladu.

Vincent Cohen-Addad
The Power of Local Search for Clustering: Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics

We give the first polynomial-time approximation schemes (PTASs) for the following classical problems:

  1. uniform facility location in edge-weighted planar graphs;
  2. k-median and k-means in edge-weighted planar graphs;
  3. k-means in Euclidean space of bounded dimension.

Our first and second results extend to minor-closed families of graphs. The algorithm is local search where the local neighborhood of a solution S consists of all solutions obtained from S by removing and adding 1/εO(1) centers.

Shuichi Hirahara
Limits of Minimum Circuit Size Problem as Oracle

The Minimum Circuit Size Problem (MCSP) is known to be hard for statistical zero knowledge via a BPP-Turing reduction (Allender and Das, 2014), whereas establishing NP-hardness of MCSP via a polynomial-time many-one reduction is difficult (Murray and Williams, 2015) in the sense that it implies ZPP ≠ EXP, which is a major open problem in computational complexity.

In this talk, we provide strong evidence that current techniques cannot establish NP-hardness of MCSP, even under polynomial-time Turing reductions or randomized reductions: Specifically, we introduce the notion of oracle-independent reduction to MCSP, which captures all the currently known reductions.  We say that a reduction to MCSP is oracle-independent if the reduction can be generalized to a reduction to MCSPA for any oracle A, where MCSPA denotes an oracle version of MCSP.  We prove that no language outside P is reducible to MCSP via an oracle-independent polynomial-time Turing reduction.  We also show that the class of languages reducible to MCSP via an oracle-independent randomized reduction that makes at most one query is contained in AM and coAM.  Thus, NP-hardness of MCSP cannot be established via such oracle-independent reductions unless the polynomial hierarchy collapses.

Shaofeng Jiang
A PTAS for the Steiner Forest Problem in Doubling Metrics

We present a (randomized) polynomial-time approximation scheme (PTAS) for the Steiner Forest Problem in doubling metrics. Before our work, a PTAS is given only for the Euclidean plane in [FOCS 2008: Borradaile, Klein and Mathieu]. Our PTAS also shares similarities with the dynamic programming for sparse instances used in [STOC 2012: Bartal, Gottlieb and Krauthgamer] and [SODA 2016: Chan and Jiang]. However, extending previous approaches requires overcoming several non-trivial hurdles.

We introduce the following novel technical ideas.

  1. We prove a technical lemma showing that Steiner points have to be “near” the terminals in an optimal Steiner tree. This enables us to define an estimator to estimate the local behavior of the optimal solution, even though the Steiner points are unknown in advance. This lemma also generalizes previous results in the Euclidean plane, and may be of independent interest for related problems involving Steiner points.
  2. We develop a novel algorithmic technique known as “adaptive cells” to overcome the difficulty of keeping track of multiple components in a solution. Our idea is based on but significantly different from the previously proposed “uniform cells” in the FOCS 2008 paper, whose techniques cannot be readily applied to doubling metrics.
Gautam Kamath
Robust Estimators in High Dimensions without the Computational Intractability

We study high-dimensional distribution learning in an agnostic setting where an adversary is allowed to arbitrarily corrupt an ε-fraction of the samples. Such questions have a rich history spanning statistics, machine learning and theoretical computer science. Even in the most basic settings, the only known approaches are either computationally inefficient or lose dimension-dependent factors in their error guarantees. This raises the following question: is high-dimensional agnostic distribution learning even possible, algorithmically?

In this talk, we present the first computationally efficient algorithms with dimension-independent error guarantees for agnostically learning several fundamental classes of high-dimensional distributions: (1) a single Gaussian, (2) a product distribution on the hypercube, (3) mixtures of two product distributions (under a natural balancedness condition), and (4) mixtures of spherical Gaussians. Our algorithms achieve error that is independent of the dimension, and in many cases scales nearly optimally with the fraction of adversarially corrupted samples. Moreover, we develop a general recipe for detecting and correcting corruptions in high-dimensions, that may be applicable to many other problems.

Based on joint work with Ilias Diakonikolas, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart.

Young Kun Ko
How Exactly Hard are “Intermediately-Hard” Problems? Proving Quasi-Polynomial Hardness via Birthday Repetition

In this talk we give a broad introduction to Birthday Repetition, a technique introduced in [AIM '14] to prove quasi-polynomial hardness of “Free” game assuming the Exponential Time Hypothesis. The main observation of the technique is Birthday Paradox, in particular that aggregating the variables in 2CSPs to a tuple of size Õ(√n) then choosing two tuples at random will have a challenge from original 2CSP with high probability.

Using the technique, we show the following specific applications:

  1. ε-approximate Nash Equilibrium with good social welfare [BKW '15, KY '16];
  2. Densest-k-subgraph with perfect completeness (or additive approximation guarantees) [BKRW '15];
  3. Signaling for Bayesian Games [Rub '16, KY '16];
  4. Approximation guarantee for dense-CSPs [MR '16].
Weihao Kong
Estimating the Covariance Spectrum

Suppose one wishes to accurately recover the set of eigenvalues of the covariance matrix of a distribution, given access to samples from the distribution. To what extent can this set be accurately approximated given an amount of data that is sublinear in the dimension of the space? The naive empirical estimate has poor performance when the number of samples is linear or sub-linear in the dimension of the data. In the “large sample, large dimension” setting, we proposed an efficient and information theoretically near-optimal algorithm to learn the moments of the covariance spectral distribution. Further we show that given the first k moments of a distribution, we can pin down the distribution in Earthmover distance up to an error of O(1/k). These two results combined allow us to efficiently and accurately learn the spectrum of the underlying covariance matrix, yielding a consistent spectrum estimator even with sub-linear number of samples.

Rasmus Kyng
Approximate Gaussian Elimination for Laplacians — Fast, Sparse, and Simple

I will show how to perform sparse approximate Gaussian elimination on Laplacian matrices.

I present a simple, nearly linear time algorithm that approximates a Laplacian by a matrix with a sparse Cholesky factorization, which is essentially Gaussian elimination on symmetric matrices.

This gives the first nearly linear time solver for Laplacian systems that is based purely on random sampling, and does not use any graph theoretic constructions such as low-stretch trees, sparsifiers, or expanders.

Joint work with Sushant Sachdeva.

Yang Li
The Stochastic Matching Problem with (Very) Few Queries

Motivated by an application in kidney exchange, we study the following stochastic matching problem: we are given a graph G(V,E) (not necessarily bipartite), where each edge in E is realized with some constant probability p > 0 and the goal is to find a maximum matching in the realized graph. An algorithm in this setting is allowed to make queries to edges in E in order to determine whether or not they are realized, and we aim to design algorithms that make as few queries per vertex as possible.

We design algorithms for the stochastic matching problem that achieve the same approximation factor as the previous best algorithms of Blum et al. (EC 2015) while making exponentially smaller number of queries per vertex. Moreover, the approximation guarantee of our algorithms is instance-wise as opposed to only being competitive in expectation as is the case for Blum et al. This is of particular relevance to the key application of stochastic matching in kidney exchange.

This is based on joint work with Sepehr Assadi and Sanjeev Khanna.

Kurt Mehlhorn
Network Flow and Equilibrium Computation in the Linear Exchange Economy

Leon Walras introduced an economic market model in 1874. In this model, every agent participating in the market has an initial endowment of some goods and a utility function over sets of goods. Goods are assumed to be divisible.

The market clears at a set of prices if each agent can spend its entire budget (= the total value of its goods at the set of prices) on a bundle of goods with maximum utility, and all goods are completely sold. Market clearing prices are also called equilibrium prices. In the linear version of the problem, all utility functions are linear. For the case of linear utility functions, Walras' model is also known as the linear exchange economy.

Walras argued the existence of equilibrium prices by describing an iterative improvement algorithm. However, his argument was incomplete. A convincing proof of existence was only given in the 1950 by Arrow and Debreu. The proof is non-constructive. Starting in the '70s, the quest for algorithms arose. The first algorithms were exponential. Later, polynomial time algorithms were derived based on the formulation of the problem as a convex program and the use of the Ellipsoid or the interior point method.

In the technical part of the talk, we describe a combinatorial polynomial-time algorithm for computing equilibrium prices. We formulate the problem as a network flow problem in which the prices are modeled as capacities. We show that the problem can be solved by an iterative algorithm. In each iteration, we first adjust the prices and then compute a maximum flow. The adjustment of the prices is based on a careful examination of the current maximum flow.

We also report on an implementation of the algorithm.

(joint work with Ran Duan, Jugal Garg, and Omar Darwish).

Dor Minzer
Towards NP-Nardness of 2-to-2 Games?

We present a candidate reduction from 3-Lin to the 2-to-2 Games problem. Though we are unable to show that the reduction is sound, we present a combinatorial hypothesis about Grassmann graphs which, if correct, is sufficient to show the soundness of the reduction in a certain non-standard sense. The optimized parameter is the number of vertices that can be assigned a small list of colors, so that for every constraint, either one of its endpoints is unassigned, or there is a consistent pair of colors in the endpoints' lists.

This sense of soundness is sufficient to obtain new hardness gaps for IS: Assuming a combinatorial hypothesis on the Grassmann Graph, it is NP-hard to distinguish whether an n-vertex graph has an independent set of size (1 - 1/√2)n - εn or whether every independent set has size εn. In particular, it is NP-hard to approximate the Vertex Cover problem to within factor √2 - ε.

The talk is based on a joint work with Subhash Khot (NYU) and Muli Safra (Tel-Aviv University).

Seth Pettie
Optimal Compression of Graph Metrics

Every undirected, unweighted graph G=(V,E) defines a “graph metric” (V,d) where d is the distance function w.r.t. G. Graph spanners, emulators, and distance oracles can all be viewed as “lossy” compression schemes that take a (dense) undirected graph G and produce a representation of some approximation (V,d') of the true metric (V,d).

What does an information-theoretically optimal compression of (V,d') look like? In particular, given a budget of n1+ε bits for the compressed representation, how much must d' diverge from d, as a function of ε?

In this talk I will survey the history of graph compression. The talk will cover constructions of additive spanners, sublinear additive emulators, and a recent lower bound due to Abboud, Bodwin, and Pettie (2016) that mostly closes the problem.

Thatchaphol Saranurak
Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture

Consider the following Online Boolean Matrix-Vector Multiplication problem: We are given an n*n matrix M and will receive n column-vectors of size n, denoted by v1, …, vn, one by one. After seeing each vector vi, we have to output the product M*vi before we can see the next vector. A naive algorithm can solve this problem using O(n3) time in total, and its running time can be slightly improved to O(n3/log2 n) [Williams SODA'07].

We show that a conjecture that there is no truly subcubic (O(n3-ε)) time algorithm for this problem can be used to exhibit the underlying polynomial time hardness shared by many dynamic problems. For a number of problems, such as subgraph connectivity, Pagh's problem, d-failure connectivity, decremental single-source shortest paths, and decremental transitive closure, this conjecture implies tight hardness results. Thus, proving or disproving this conjecture will be very interesting as it will either imply several tight unconditional lower bounds or break through a common barrier that blocks progress with these problems. This conjecture might also be considered as strong evidence against any further improvement for these problems since refuting it will imply a major breakthrough for combinatorial Boolean matrix multiplication and other long-standing problems if the term “combinatorial algorithms” is interpreted as “non-Strassen-like algorithms”.

The conjecture also leads to hardness results for problems that were previously based on diverse problems and conjectures — such as 3SUM, combinatorial Boolean matrix multiplication, triangle detection, and multiphase — thus providing a uniform way to prove polynomial hardness results for dynamic algorithms; some of the new proofs are also simpler or even become trivial. The conjecture also leads to stronger and new, non-trivial, hardness results, e.g., for the fully dynamic densest subgraph and diameter problems.

Tselil Schramm
Strongly Refuting Random Constraint Satisfaction Problems Below the Spectral Threshold

Random instances of 3SAT are known to be unsatisfiable with high probability when there at least 5N clauses. However, given a random 3SAT instance on N variables, the task of refuting the instance, or of proving that the instance has no satisfying assignments, is hypothesized to be computationally hard if there are O(N) clauses—in fact, the best known efficient algorithms for refutation require instances with at least Ω(N3/2) clauses, a factor of N1/2 beyond the unsatisfiability threshold at ϴ(N).

In this talk, I will describe a new spectral algorithm that refutes 3SAT instances with fewer clauses, given more time. Our algorithm extends the best polynomial time algorithms at ϴ(N3/2) clauses, interpolating between them and the exponential brute-force search at the unsatisfiability threshold at ϴ(N) clauses.

Further, our algorithm strongly refutes the instances, certifying that no assignment satisfies more than a (7/8)-fraction of constraints.

This result also implies tight upper bounds on the value of sum-of-squares relaxations for random CSPs, as well as the value of sum-of-squares relaxations for random polynomial maximization over the unit sphere (injective tensor norm).

Based on joint work with Prasad Raghavendra and Satish Rao.

Noah Stephen-Davidowitz
The Reverse Minkowski Theorem—Proof of a Conjecture Due to Dadush

A classical question in the geometry of numbers asks how many lattice points lie in some ball around the origin. Minkowski's celebrated theorem gives us a tight lower bound for this number that depends only on the determinant of the lattice. (One can think of the determinant as the limit of the density of lattice points inside large balls. So, Minkowski's theorem gives a tight lower bound on a lattice's “local density” based on its “global density.”) We resolve a conjecture due to Dadush that gives a nearly tight converse to Minkowski's theorem—an upper bound on the number of lattice points in a ball that depends only on the determinants of sublattices. This theorem has numerous applications, from complexity theory, to the geometry of numbers, to the behavior of Brownian motion on flat tori.

Based on joint work with Oded Regev.

Ben Lee Volk
Efficiently Decoding Reed–Muller Codes from Random Errors

Reed–Muller codes encode an m-variate polynomial of degree r by evaluating it on all points in {0,1}m. Its distance is 2m-r and so it cannot correct more than half number of errors in the worst case. For random errors, however, one may hope for better results.

In this talk we will see an efficient algorithm for correcting random errors in Reed–Muller codes in various regimes that can handle many more errors than the minimal distance suggests, and discuss its connections with the recent progress regarding decoding erasures in Reed–Muller codes.

(Based on a joint work with Ramprasad Saptharishi and Amir Shpilka)

Sam Wong
Applying the Ellipsoid Method for Combinatorial Optimization: Convex is Better than Linear

The ellipsoid method, as analyzed by Khachiyan in 1979, is the first polynomial time algorithm for solving linear and convex programming in the presence a separation oracle for the underlying linear constraints. The seminal paper of Grotschel, Lovasz & Schrijver laid the foundation of its wide applicability in combinatorial optimization by formulating various discrete optimization problems as linear programs.

In this talk I will demonstrate that surprisingly, very often appropriately formulating the problem as a convex program instead would yield significantly faster algorithms. Applications of this simple idea include new algorithms for matroid intersection and computing market equilibrium with the aggregate demand oracle in buyers' market.

Leqi Zhu
A Tight Space Bound for Consensus

Existing n-process randomized wait-free (and obstruction-free) consensus protocols from registers all use at least n registers. In 1992, it was proved that such protocols must use Ω(√n) registers. In 2015, this was improved to Ω(n) registers in the anonymous setting, where processes do not have identifiers. Closing the gap in the general case, however, remained an open problem. Recently, I resolved this problem by proving that every randomized wait-free (or obstruction-free) consensus protocol for n processes must use at least n-1 registers. This talk will go over the lower bound and the necessary prerequisites from distributed computing.

Venue & Map

Talks will take place at Lecture Theatre, 9th floor, William M. W. Mong Engineering Building (map)

The map also shows a selection of cafeterias, coffee shops, and a bar. See the map for Monday lunch and Thursday dinner locations.


Monday Aug 22
8:30Bus from hotel to campus
9:00 - 9:30Registration, coffee and breakfast
9:30 - 10:15Leqi Zhu: A Tight Space Bound for Consensus
10:15 - 11:00Tselil Schramm: Strongly Refuting Random Constraint Satisfaction Problems Below the Spectral Threshold
11:00 - 11:15Coffee break
11:15 - 12:15Seth Pettie: Optimal Compression of Graph Metrics (Keynote)
12:15 - 2:15Lunch (at Lee Woo Sing Harmony Restaurant)
2:15 - 3:00Gautam Kamath: Robust Estimators in High Dimensions without the Computational Intractability
3:00 - 3:45Rasmus Kyng: Approximate Gaussian Elimination for Laplacians — Fast, Sparse, and Simple
3:45 - 4:15Coffee break
4:15 - 5:00Greg Bodwin: Distance Preservers and Their Applications
5:15Bus back to hotel
Tuesday Aug 23
8:45Bus from hotel to campus
9:00 - 9:30Coffee and breakfast
9:30 - 10:15Arturs Backurs: Which Regular Expression Patterns are Hard to Match?
10:15 - 11:00Thatchaphol Saranurak: Unifying and Strengthening Hardness for Dynamic Problems
11:00 - 11:15Coffee break
11:15 - 12:15Xi Chen: On the Query Complexity of Boolean Monotonicity Testing (Keynote)
12:15 - 2:15Lunch (on your own)
2:15 - 3:00Sam Wong: Applying the Ellipsoid Method for Combinatorial Optimization: Convex is Better than Linear
3:00 - 3:45Weihao Kong: Estimating the Covariance Spectrum
3:45 - 4:15Coffee break
4:15 - 5:00Shuichi Hirahara: Limits of Minimum Circuit Size Problem as Oracle
5:15Bus back to hotel
Wednesday Aug 24
8:45Bus from hotel to campus
9:00 - 9:30Coffee and breakfast
9:30 - 10:15Young Kun Ko: How Exactly Hard are “Intermediately-Hard” Problems?
10:15 - 11:00Dor Minzer: Towards NP-Nardness of 2-to-2 Games?
11:00 - 11:15Coffee break
11:15 - 12:15Kurt Mehlhorn: Network Flow and Equilibrium Computation in the Linear Exchange Economy (Keynote)
12:15 - 2:15Lunch (on your own)
2:15 - 3:00Noah Stephen-Davidowitz: The Reverse Minkowski Theorem: Proof of a Conjecture Due to Dadush
3:00 - 3:45Ben Lee Volk: Efficiently Decoding Reed–Muller Codes from Random Errors
3:45 - 4:15Coffee break
4:15 - 5:00Yang Li: The Stochastic Matching Problem with (Very) Few Queries
5:15 - 6:45Rump session (If you want to speak, contact Ran)
7:00Bus back to hotel
Thursday Aug 25
8:45Bus from hotel to campus
9:00 - 9:30Coffee and breakfast
9:30 - 10:15Michael Cohen: Computing the Stationary Distribution
10:15 - 11:00Sarah Cannon: A Markov Chain Algorithm for Compression in Self-Organizing Particle Systems
11:00 - 11:15Coffee break
11:15 - 12:00Eshan Chattopadhyay: Explicit Constructions of Two-Source Extractors
12:00 - 2:15Lunch (on your own)
2:15 - 3:00Vincent Cohen-Addad: The Power of Local Search for Clustering
3:00 - 3:45Shaofeng Jiang: A PTAS for the Steiner Forest Problem in Doubling Metrics
3:45 - 4:15Coffee break
4:15 - 5:00Mark Bun: The Price of Online Queries in Differential Privacy
5:00 - 5:45Fabrice Benhamouda: Diverse Modules and Zero-Knowledge in Cryptography
6:30 - 7:30Dinner (at Morningside College)
7:45Bus back to hotel

Interested in exploring Hong Kong with one of our PhD students on Friday (Aug 26)? Contact Chris by Thursday (Aug 25) 6pm. As an experienced worldwide traveler, he will show you an interesting side of the city.


Visa information


Participants will stay at Regal Riverside Hotel near Shatin Station

Getting from Hong Kong International Airport to the hotel

Recommended options:

  • Bus: Take bus A41 at the airport and get off at Regal Riverside Hotel bus stop (HK$22.3; duration: 1 hour)
  • Taxi: Take taxi in red (around HK$350; duration: 45 minutes)

Getting from the hotel to the lecture hall (if you miss the CTW shuttle bus)

From the hotel to University Station

  1. Walk across Shing Mun River and through shopping malls to Shatin Station (15-20 minutes)
  2. Take MTR from Shatin Station to University Station (2 stops towards Lo Wu/Lok Ma Chau direction)

From University Station to William M. W. Mong Engineering Building

  • Option 1 — university shuttle bus:
    1. Take university shuttle bus, route 1 (frequency: every 15 minutes) to Sir Run Run Shaw Hall
    2. Walk to William M. W. Mong Engineering Building via a footbridge (2 minutes)
  • Option 2 — walking:
    1. Walk 3 minutes to Yasumoto International Academic Park (a building sometimes known as YIA)
    2. Take outdoor escalators all the way up
    3. Walk 5 minutes along Nursery Path to William M. W. Mong Engineering Building

Alternative hotels

Contact if you need help with reservation


The shopping malls at Sha Tin Station (walkable from the hotel) have many local and international options. Here are some options at Sha Tin or accessible by MTR:


  • Chi Lin Vegetarian, an excellent vegan-friendly restaurant inside a beautiful garden near Diamond Hill Station.
  • Kung Tak Lam, featuring Shanghainese vegetarian cuisine. A branch is near Sha Tin Station.
  • Happy Veggies, a non-profit social enterprise serving vegetarian food near Mong Kok Station.
  • Veggie Family, a decent vegetarian restaurant near Mong Kok Station or Mong Kok East Station.
  • Loving Hut, a vegan fastfood place near Kowloon Bay Station.

Hong Kong/Cantonese

  • Tim Ho Wan, an inexpensive Michelin-starred dim sum restaurant. A branch is near Prince Edward Station.
  • Yum Cha, featuring avant-garde, photogenic dim sum, near Tsim Sha Tsui Station.
  • Dim Dim Sum, a dim sum chain, with a branch near Sha Tin Station.
  • Tsui Wah, a popular “cha chaan teng” chain. A branch is near Sha Tin Station.
  • Shing Kee, serving hot pot for the adventurous, near Sha Tin Station.
  • Keung Kee, a “dai pai dong” near Shek Kip Mei Station or Sham Shui Po Station.
  • Mak Man Kee, famous for wonton noodles, near Jordan Station.
  • Joy Hing, well known for “char siu” (barbecued pork in Cantonese sauce), near Wan Chai Station.
  • Yung Kee, a diner famous for roast goose, near Central Station.


  • Din Tai Fung, the famous dumpling chain. A branch is near Sha Tin Station.
  • Nha Trang, for Vietnamese cuisine. A branch is near Sha Tin Station.
  • Bangkok Thai, for Thai cuisine. A branch is near Sha Tin Station.
  • Mi-Ne Sushi, for Japanese sushi. A branch is near Sha Tin Station.
  • Butao, for Japanese ramen (noodle soup). A branch is near Sha Tin Station.


  • Simplylife, serving Western food. A branch is near Sha Tin Station.
  • PizzaExpress, for pizza and pasta. A branch is near Sha Tin Station.
  • The Spaghetti House, for pizza and pasta. A branch is near Sha Tin Station.
  • IKEA Bistro, Swedish fastfood that comes with the iconic furniture store. A branch is near Sha Tin Station.


  • Honeymoon Dessert, serving Hong Kong style desserts and famous for its durian options. A branch is near Sha Tin Station.


Hong Kong has an extensive public transportation system. Virtually all locations can be reached by MTR (subway), bus, or minibus. The octopus card can be used for electronic payment on all modes of public transport (except some red minibuses) and is highly recommended. It is also accepted as a form of payment in many shops.


Learn a few Cantonese phrases, especially those related to gratitude, to impress the locals.

Nightlife and Drinking

A good place to see the light show (8-8.15pm every night) with a cocktail in hand and away from the crowds is Wooloomooloo Prime in Tsim Sha Tsui.

On the Hong Kong Island side, the sister Wooloomooloo rooftop bar boasts equally impressive views in an open-air setting. Some prefer the experience at Sevva.

Lan Kwai Fong is the undisputed party central with drinking and dancing every night, all night long. The nearby Soho area has no shortage of bars and music venues and is generally more relaxed. We like the Gecko Lounge for the jazz, Lily & Bloom for the drinks, and Boom for the art, but it is best to explore and ask for local advice. Some of the more interesting establishments are hidden in basements reached through back alleys that only a seasoned local party animal would know about.

Two other areas to check out are Wan Chai, specifically the alleys intersecting Queen's Rd E (Andrej's favorite establishment Tai Lung Fung is located here) and Tai Hang for small wine and cocktail bars.

Coffee Shops

The Shatin area in and around the shopping malls has several branches of Starbucks and Pacific Coffee (a local alternative).

There are many excellent small cafes in the streets of Hong Kong Island and Kowloon, including 18 Grams, Coco Espresso, the Cupping Room, Coffee Academics, and Brew Bros.

Urban Activities

Hong Kong Park is a pleasant area to walk around amidst the urban jungle. It has several ponds, an aviary with exotic birds, and an interesting museum of teaware with its own teahouse offering an impressive selection of Chinese teas and vegetarian dimsum (reservations recommended).

The Avenue of Stars is a well-trodden attraction but is partially closed for renovations. (So is the nearby Hong Kong Museum of Art.) A walk along the Tsim Sha Tsui Waterfront and a ride on the Star Ferry to Central is nevertheless a must-do for any visitor to Hong Kong. Tamar Park on the HK Island side is an attractive alternative.

Mong Kok is one of the most densely populated areas in the World and is a popular part for teenagers to hang around. It has a large assortment of small shops selling clothing, electronics, shoes, and outdoor equipment, local restaurants and dessert places, and some fancier new places like this microbrewery. There are several street markets in the area, including Temple Street Night Market where local food can be had on the cheap.

The Ap Liu Market in Sham Shui Po has an impressive array of electronic equipment.

Kowloon City is a lively, gradually gentrifying area on the East side of Kowloon. It used to house the unusual Kowloon Walled City, which has since been replaced by a park and some museum exhibits documenting the past of this area. There are now many authentic Thai restaurants here.

Movie buffs might enjoy a visit to the Chunking Mansion in Tsim Sha Tsui.

Outdoor Activities

Hong Kong has an extensive system of hiking trails that is popular on the weekends but relatively uncrowded otherwise. Some options for serious hikers are Ma On Shan and Sai Kung and Dragonback. For lighter walks you can check out Bowen Rd. on Hong Kong Island or if you are into monkeys, the Kowloon Reservoirs. The summer weather is extremely hot and humid so bring plenty of water and sunscreen!

There are several nice beaches. We recommend Deep Water Bay, Shek O, and Big Wave Bay on Hong Kong Island, Cheung Sha in Lantau, and Sai Wan in the New Territories (accessible on foot only).

Some other possibilities are the Big Buddha on Lantau (which can be visited on your way to the airport) and exploring outlying islands like Cheung Chau and Lamma.