Demo Data from EDBT 2026 / reviewers in the wild / expert
Chung Hoi Wong
dblp:129/1647
· DBLP profile ↗
1ranked-venue papers
0as first author
0since 2021 · last 2013
—ORCID · none
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 1
Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.
| Theoretical computer science
1 paper |
Computational complexity · 100% |
Topics — the 4 heaviest of 4, each with the papers that count most for it
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Computational complexity
communication complexity |
0.2 | 1 | 2013 | Fourier Sparsity, Spectral Norm, and the Log-Rank Conjecture · FOCS 2013 |
Computational complexity › boolean function analysis
fourier analysis of boolean functions |
0.2 | 1 | 2013 | Fourier Sparsity, Spectral Norm, and the Log-Rank Conjecture · FOCS 2013 |
Computational complexity › communication complexity › deterministic communication complexity
log-rank conjecture |
0.2 | 1 | 2013 | Fourier Sparsity, Spectral Norm, and the Log-Rank Conjecture · FOCS 2013 |
Computational complexity › query complexity › decision tree complexity
parity decision trees |
0.0 | 1 | 2013 | Fourier Sparsity, Spectral Norm, and the Log-Rank Conjecture · FOCS 2013 |
Methods — techniques the papers use, named apart from their topics
polynomial rank · 0.2fourier analysis · 0.2degree-reduction protocol · 0.2
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2013 | Fourier Sparsity, Spectral Norm, and the Log-Rank ConjectureabstractWe study Boolean functions with sparse Fourier spectrum or small spectral norm, and show their applications to the Log-rank Conjecture for XOR functions f(x ⊕ y) - a fairly large class of functions including well studied ones such as Equality and Hamming Distance. The rank of the communication matrix Mffor such functions is exactly the Fourier sparsity of f. Let d = deg2(f) be the F2-degree of f and DCC(f · ⊕) stand for the deterministic communication complexity for f(x ⊕ y). We show that 1) DCC(f · ⊕) = O(2d2/2logd-2 ∥f̂∥1). In particular, the Log-rank conjecture holds for XOR functions with constant F2-degree. 2) DCC(f · ⊕) = O(d∥f̂∥1) = O(√(rank(Mf))). This improves the (trivial) linear bound by nearly a quadratic factor. We obtain our results through a degree-reduction protocol based on a variant of polynomial rank, and actually conjecture that the communication cost of our protocol is at most logO(1)rank(Mf). The above bounds are obtained from different analysis for the number of parity queries required to reduce f's F2-degree. Our bounds also hold for the parity decision tree complexity of f, a measure that is no less than the communication complexity. Along the way we also prove several structural results about Boolean functions with small Fourier sparsity ∥f̂∥0or spectral norm ∥f̂∥1, which could be of independent interest. For functions f with constant F2-degree, we show that: 1) f can be written as the summation of quasi-polynomially many indicator functions of subspaces with ±-signs, improving the previous doubly exponential upper bound by Green and Sanders; 2) being sparse in Fourier domain is polynomially equivalent to having a small parity decision tree complexity; and 3) f depends only on polylog∥f̂∥1linear functions of input variables. For functions f with small spectral norm, we show that: 1) there is an affine subspace of co dimension ∥f̂∥1on which f(x) is a constant, and 2) there is a parity decision ∥f̂∥1log∥f̂∥0for computing f. Hing Yin Tsang, Chung Hoi Wong, Ning Xie 0002, Shengyu Zhang 0002 |
FOCS | 2 |