Lune

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

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