Xi Chen

activity

20232026

collaborators

Showing cs.DSShow all

4 papers · 1 filter

cs.DS2025

Model-agnostic distribution recovery in high dimension via Fourier measurements

Xi Chen, Anindya De, Yizhi Huang +3

We study the problem of reconstructing an unknown probability distribution to high accuracy, given noisy information about its low-degree Fourier coefficients. Prior results for th…

cs.DS2024

Trace reconstruction from local statistical queries

Xi Chen, Anindya De, Chin Ho Lee +1

The goal of trace reconstruction is to reconstruct an unknown $n$ -bit string $x$ given only independent random traces of $x$ , where a random trace of $x$ is obtained by passing $x$ …

cs.DS2024

Testing Sumsets is Hard

Xi Chen, Shivam Nadimpalli, Tim Randolph +2

A subset $S$ of the Boolean hypercube $F_{2}^{n}$ is a sumset if $S = {a + b : a, b \in A}$ for some $A \subseteq F_{2}^{n}$ . Sumsets are central objects of study in add…

cs.DS2023

Subset Sum in Time $2^{n /2} / p o l y (n)$

Xi Chen, Yaonan Jin, Tim Randolph +1

A major goal in the area of exact exponential algorithms is to give an algorithm for the (worst-case) $n$ -input Subset Sum problem that runs in time $2^{(1/2 - c) n}$ for some const…

Model-agnostic distribution recovery in high dimension via Fourier measurements

Trace reconstruction from local statistical queries

Testing Sumsets is Hard

Subset Sum in Time 2n/2/poly(n)

Subset Sum in Time $2^{n /2} / p o l y (n)$