Xue Chen

activity

20152021

most citedActive Regression via Linear-Sample Sparsification

21 citations · 36 across the 10 of their papers we have counts for

collaborators

Showing 2015Show all

2 papers · 1 filter

cs.DS2015

Parameterized Algorithms for Constraint Satisfaction Problems Above Average with Global Cardinality Constraints

Xue Chen, Yuan Zhou

Given a constraint satisfaction problem (CSP) on $n$ variables, $x_{1}, x_{2}, \dots, x_{n} \in {\pm 1}$ , and $m$ constraints, a global cardinality constraint has the form of $\sum_{i…

cs.CC2015

Integrality Gaps and Approximation Algorithms for Dispersers and Bipartite Expanders

Xue Chen

We study the problem of approximating the quality of a disperser. A bipartite graph $G$ on $([N], [M])$ is a $(ρN, (1 - δ) M)$ -disperser if for any subset $S \subseteq [N]$ of size $ρN$ ,…