# Xiaodong Sun

Welcome! I received my Ph.D. from the
Department of Mathematics,
Rutgers, The State University of New Jersey.
My thesis advisor was
Prof. Michael Saks.
## Research Insterests

Discrete Mathematics, Theory of Computing, Algorithms with
applications to Computer Networks.
## Papers

### Journal Publications

- C. D. Correa, I. Marsic, and X. Sun

Exact and Heuristic Algorithms for Dynamic Tree Simplification,
*Mathematical Modelling and Algorithms (JMMA)*,
**4**(4), 2005, pages 331-353.
- Y. Shavitt, X. Sun, A. Wool, and B. Yener

Computing the Unmeasured: An Algebraic Approach to Internet Mapping,
*the IEEE Journal on Selected Areas in Communications*
**22**(1), 2004, pages 67-78.
- P. Beame, M. Saks, X. Sun, and E. Vee

Time-space tradeoff lower bounds for
randomized computation of decision problems,
*Journal of the ACM* **50**(2), 2003, pages 154-195.
- S. Davis, W. Duke, and X. Sun

Probabilistic Galois theory of reciprocal polynomials
*Exposition. Math.* **16**(3), 1998, pages 263-270.
- Xiaodong Sun, Shi-Kun Wang, and Ke Wu

Classification of six-vertex-type solutions of the colored Yang-Baxter
equation .
*Journal of Mathematical Physics*, **36** (1995) No. 10, 6043--6063.
- Xiaodong Sun and Shi-Kun Wang

de Rham complexes of q-analog of general linear group GLq(N)
.
*Journal of Mathematical Physics*, **35** (1994) No.5, 2657--2686.
- Xiaodong Sun and Shi-Kun Wang

Yang-Baxter matrix and *-calculi on quantum groups of A-series .
*Journal of Physics A. Mathematical and General*,
**26** (1993), No. 6, L293--L297.
- Xiaodong Sun and Shi-Kun Wang

Bicovariant differential calculus on the two-parameter quantum group
GLp,q(2) .
*Journal of Mathematical Physics*, **33** (1992) No.10, 3313--3329.

### Refereed Conference Publications

- A. Chakrabarti, S. Khot, and X. Sun

Near-Optimal Lower Bounds on the Multi-Party Communication Complexity
of Set Disjointness, Proc. 18th IEEE Conference on
Computational Complexity
(CCC) 2003,
pages 107--117.
- M. Saks, X. Sun

Space lower bounds for distance approximation
in the data stream model,
Proc. 34th Annual ACM Symposium on Theory of Computing
(STOC) 2002,
pages 360--369.

- Y. Shavitt, X. Sun, A. Wool, and B. Yener

Computing the Unmeasured: An Algebraic Approach to Internet Mapping,
Proc. IEEE Infocom --- The Conference on Computer Communications, 2001,
pages 1646--1654.

Preprint version available as DIMACS Technical Report 2000-15.
- P. Beame, M. Saks, X. Sun, and E. Vee

Super-linear Time-space Tradeoff Lower Bounds for Randomized Computation,
Proc. 41st IEEE Symp. on Foundations of Computer Science
(FOCS) 2000,
pages 169--179.

Preprint version available at ECCC.
(Postscript file)

### Thesis and Technical Reports

Last modified: April 23, 2004.