Profiles2020-2026
Xi Chen
Columbia University
23Papers
0Last author
22Unique co-authors
18First author
0Solo
First and last author come from byline position, which some venues assign alphabetically.
Recent papers23
- A Mysterious Connection between Tolerant Junta Testing and Agnostically Learning ConjunctionsAuthor 1 of 3STOC 2026 · 4 citations
- Boolean Function Monotonicity Testing Requires (Almost) n1/2 QueriesAuthor 2 of 5STOC 2026
- Halfspaces are hard to test with relative errorAuthor 1 of 6SODA 2026
- Monotonicity Testing of High-Dimensional Distributions with Subcube ConditioningAuthor 2 of 5STOC 2025 · 2 citations
- Uniformity Testing over Hypergrids with Subcube ConditioningAuthor 1 of 2SODA 2024 · 2 citations
- Computing a Fixed Point of Contraction Maps in Polynomial QueriesAuthor 1 of 3STOC 2024 · 1 citation
- Smoothed Complexity of SWAP in Local Graph PartitioningAuthor 1 of 3SODA 2024
- Streaming Euclidean MST to a Constant FactorAuthor 2 of 5STOC 2023 · 5 citations
- Complexity of Equilibria in First-Price Auctions under General Tie-Breaking RulesAuthor 1 of 2STOC 2023 · 3 citations
- New Lower Bounds for Adaptive Tolerant Junta TestingAuthor 1 of 2FOCS 2023 · 3 citations
- Approximate Trace Reconstruction from a Single TraceAuthor 1 of 5SODA 2023 · 2 citations
- New streaming algorithms for high dimensional EMD and MSTAuthor 1 of 4STOC 2022 · 11 citations
- Computational Hardness of the Hylland-Zeckhauser SchemeAuthor 2 of 4SODA 2022 · 8 citations
- Near-Optimal Average-Case Approximate Trace Reconstruction from Few TracesAuthor 1 of 5SODA 2022 · 7 citations
- Memory Bounds for Continual LearningAuthor 1 of 3FOCS 2022 · 6 citations
- On the complexity of dynamic submodular maximizationAuthor 1 of 2STOC 2022 · 6 citations
- Average-Case Subset Balancing ProblemsAuthor 1 of 4SODA 2022 · 2 citations
- Polynomial-time trace reconstruction in the smoothed complexity modelAuthor 1 of 5SODA 2021 · 21 citations
- Random Restrictions of High Dimensional Distributions and Uniformity Testing with Subcube ConditioningAuthor 2 of 5SODA 2021 · 10 citations
- Hedging in games: Faster convergence of external and swap regretsAuthor 1 of 2NeurIPS 2020 · 88 citations
- Smoothed complexity of local max-cut and binary max-CSPAuthor 1 of 5STOC 2020 · 7 citations
- Nearly optimal edge estimation with independent set queriesAuthor 1 of 3SODA 2020 · 5 citations
- A Lower Bound on Cycle-Finding in Sparse DigraphsAuthor 1 of 4SODA 2020 · 2 citations
