17 citations · 56 across the 22 of their papers we have counts for
24 papers
Continual Learning With Participation Privacy: An Auditable Buffering-Aggregation Recipe
T-H. Hubert Chan, Elaine Shi, Mengshi Zhao +1
Modern federated and streaming learning systems often release intermediate models, so privacy must hold for the full trajectory under adaptive interaction. Motivated by participati…
Game-Theoretically Secure Protocols for the Ordinal Random Assignment Problem
T-H. Hubert Chan, Ting Wen, Hao Xie +1
We study game-theoretically secure protocols for the classical ordinal assignment problem (aka matching with one-sided preference), in which each player has a total preference orde…
Towards More Robust Natural Language Understanding
Xinliang Frederick Zhang
Natural Language Understanding (NLU) is a branch of Natural Language Processing (NLP) that uses intelligent computer software to understand texts that encode human knowledge. Recen…
On the Hardness of Opinion Dynamics Optimization with -Budget on Varying Susceptibility to Persuasion
T-H. Hubert Chan, Chui Shan Lee
Recently, Abebe et al. (KDD 2018) and Chan et al. (WWW 2019) have considered an opinion dynamics optimization problem that is based on a popular model for social opinion dynamics,…
Opinion Dynamics with Varying Susceptibility to Persuasion via Non-Convex Local Search
Rediet Abebe, T-H. Hubert Chan, Jon Kleinberg +4
A long line of work in social psychology has studied variations in people's susceptibility to persuasion -- the extent to which they are willing to modify their opinions on a topic…
Limit theorems for excursion sets of subordinated Gaussian random fields with long-range dependence
Vitalii Makogin, Evgeny Spodarev
This paper considers the asymptotic behaviour of volumes of excursion sets of subordinated Gaussian random fields with (possibly) infinite variance. Actually, we consider integral…
Small Memory Robust Simulation of Client-Server Interactive Protocols over Oblivious Noisy Channels
T-H. Hubert Chan, Zhibin Liang, Antigoni Polychroniadou +1
We revisit the problem of low-memory robust simulation of interactive protocols over noisy channels. Haeupler [FOCS 2014] considered robust simulation of two-party interactive prot…
More is Less: Perfectly Secure Oblivious Algorithms in the Multi-Server Setting
T-H. Hubert Chan, Jonathan Katz, Kartik Nayak +2
The problem of Oblivious RAM (ORAM) has traditionally been studied in a single-server setting, but more recently the multi-server setting has also been considered. Yet it is still…
An SDP Primal-Dual Approximation Algorithm for Directed Hypergraph Expansion and Sparsest Cut with Product Demands
T-H. Hubert Chan, Bintao Sun
We give approximation algorithms for the edge expansion and sparsest cut with product demands problems on directed hypergraphs, which subsume previous graph models such as undirect…
Communication Complexity of Byzantine Agreement, Revisited
Ittai Abraham, T-H. Hubert Chan, Danny Dolev +4
As Byzantine Agreement (BA) protocols find application in large-scale decentralized cryptocurrencies, an increasingly important problem is to design BA protocols with improved comm…
Generalizing the Hypergraph Laplacian via a Diffusion Process with Mediators
T-H. Hubert Chan, Zhibin Liang
In a recent breakthrough STOC~2015 paper, a continuous diffusion process was considered on hypergraphs (which has been refined in a recent JACM 2018 paper) to define a Laplacian op…
Diffusion Operator and Spectral Analysis for Directed Hypergraph Laplacian
T-H. Hubert Chan, Zhihao Gavin Tang, Xiaowei Wu +1
In spectral graph theory, the Cheeger's inequality gives upper and lower bounds of edge expansion in normal graphs in terms of the second eigenvalue of the graph's Laplacian operat…
A Unified PTAS for Prize Collecting TSP and Steiner Tree Problem in Doubling Metrics
T-H. Hubert Chan, Haotian Jiang, Shaofeng H. -C. Jiang
We present a unified polynomial-time approximation scheme (PTAS) for the prize collecting traveling salesman problem (PCTSP) and the prize collecting Steiner tree problem (PCSTP) i…
Online Submodular Maximization Problem with Vector Packing Constraint
T-H. Hubert Chan, Shaofeng H. -C. Jiang, Zhihao Gavin Tang +1
We consider the online vector packing problem in which we have a dimensional knapsack and items with weight vectors arrive online in an ar…
On (, )-Restricted Max-Min Fair Allocation Problem
T-H. Hubert Chan, Zhihao Gavin Tang, Xiaowei Wu
We study the max-min fair allocation problem in which a set of indivisible items are to be distributed among agents such that the minimum utility among all agents is maximi…
Online Submodular Maximization with Free Disposal: Randomization Beats 0.25 for Partition Matroids
T-H. Hubert Chan, Zhiyi Huang, Shaofeng H. -C. Jiang +2
We study the online submodular maximization problem with free disposal under a matroid constraint. Elements from some ground set arrive one by one in rounds, and the algorithm main…
A PTAS for the Steiner Forest Problem in Doubling Metrics
T-H. Hubert Chan, Shuguang Hu, Shaofeng H. -C. Jiang
We achieve 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 pl…
Spectral Properties of Hypergraph Laplacian and Approximation Algorithms
T-H. Hubert Chan, Anand Louis, Zhihao Gavin Tang +1
The celebrated Cheeger's Inequality establishes a bound on the edge expansion of a graph via its spectrum. This inequality is central to a rich spectral theory of graphs, based on…
Spectral Properties of Laplacian and Stochastic Diffusion Process for Edge Expansion in Hypergraphs
T-H. Hubert Chan, Zhihao Gavin Tang, Chenzi Zhang
There has been recent work [Louis STOC 2015] to analyze the spectral properties of hypergraphs with respect to edge expansion. In particular, a diffusion process is defined on a hy…
Influence Maximization under The Non-progressive Linear Threshold Model
T. -H. Hubert Chan, Li Ning
In the problem of influence maximization in information networks, the objective is to choose a set of initially active nodes subject to some budget constraints such that the expect…
Online Convex Covering and Packing Problems
T-H. Hubert Chan, Zhiyi Huang, Ning Kang
We study the online convex covering problem and online convex packing problem. The (offline) convex covering problem is modeled by the following convex program: $\min_{x \in R_+^n}…
Ranking on Arbitrary Graphs: Rematch via Continuous LP with Monotone and Boundary Condition Constraints
T-H. Hubert Chan, Fei Chen, Xiaowei Wu +1
Motivated by online advertisement and exchange settings, greedy randomized algorithms for the maximum matching problem have been studied, in which the algorithm makes (random) deci…
A Primal-Dual Continuous LP Method on the Multi-choice Multi-best Secretary Problem
T-H. Hubert Chan, Fei Chen
The J-choice K-best secretary problem, also known as the (J,K)-secretary problem, is a generalization of the classical secretary problem. An algorithm for the (J,K)-secretary probl…
Incubators vs Zombies: Fault-Tolerant, Short, Thin and Lanky Spanners for Doubling Metrics
T-H. Hubert Chan, Mingfei Li, Li Ning
Recently Elkin and Solomon gave a construction of spanners for doubling metrics that has constant maximum degree, hop-diameter O(log n) and lightness O(log n) (i.e., weight O(log n…