22 citations · 115 across the 31 of their papers we have counts for
8 papers · 1 filter
Smoothed complexity of local Max-Cut and binary Max-CSP
Xi Chen, Chenghao Guo, Emmanouil-Vasileios Vlatakis-Gkaragkounis +2
We show that the smoothed complexity of the FLIP algorithm for local Max-Cut is at most , where is the number of nodes in the graph and is a…
Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning
Clément L. Canonne, Xi Chen, Gautam Kamath +2
We give a nearly-optimal algorithm for testing uniformity of distributions supported on , which makes queries to a subcube condition…
An Axiomatic Approach to Block Rewards
Xi Chen, Christos Papadimitriou, Tim Roughgarden
Proof-of-work blockchains reward each miner for one completed block by an amount that is, in expectation, proportional to the number of hashes the miner contributed to the mining o…
A Lower Bound on Cycle-Finding in Sparse Digraphs
Xi Chen, Tim Randolph, Rocco A. Servedio +1
We consider the problem of finding a cycle in a sparse directed graph that is promised to be far from acyclic, meaning that the smallest feedback arc set in is large. We pr…
Efficient average-case population recovery in the presence of insertions and deletions
Frank Ban, Xi Chen, Rocco A. Servedio +1
Several recent works have considered the \emph{trace reconstruction problem}, in which an unknown source string is transmitted through a probabilistic channel which…
Nearly optimal edge estimation with independent set queries
Xi Chen, Amit Levi, Erik Waingarten
We study the problem of estimating the number of edges of an unknown, undirected graph with access to an independent set oracle. When queried about a subset $S\subseteq…