71 citations · 455 across the 36 of their papers we have counts for
11 papers · 1 filter
On the cut dimension of a graph
Troy Lee, Tongyang Li, Miklos Santha +1
Let be a weighted undirected graph with edges. The cut dimension of is the dimension of the span of the characteristic vectors of the minimum cuts of , viewe…
On the complexity of probabilistic trials for hidden satisfiability problems
Itai Arad, Adam Bouland, Daniel Grier +3
What is the minimum amount of information and time needed to solve 2SAT? When the instance is known, it can be solved in polynomial time, but is this also possible without knowing…
Sensitivity Conjecture and Log-rank Conjecture for functions with small alternating numbers
Chengyu Lin, Shengyu Zhang
The Sensitivity Conjecture and the Log-rank Conjecture are among the most important and challenging problems in concrete complexity. Incidentally, the Sensitivity Conjecture is kno…
Fourier Sparsity of GF(2) Polynomials
Hing Yin Tsang, Ning Xie, Shengyu Zhang
We study a conjecture called "linear rank conjecture" recently raised in (Tsang et al., FOCS'13), which asserts that if many linear constraints are required to lower the degree of…
Efficient quantum protocols for XOR functions
Shengyu Zhang
We show that for any Boolean function f on {0,1}^n, the bounded-error quantum communication complexity of XOR functions satisfies that $Q_ε(f\circ \oplus) = O(2^d (…
Fourier sparsity, spectral norm, and the Log-rank conjecture
Hing Yin Tsang, Chung Hoi Wong, Ning Xie +1
We study Boolean functions with sparse Fourier coefficients or small spectral norm, and show their applications to the Log-rank Conjecture for XOR functions f(x\oplus y) --- a fair…