VLDB 2026 Research / reviewers in the wild / expert
Sam McGuire
dblp:276/6621
· DBLP profile ↗
2ranked-venue papers
0as first author
2since 2021 · last 2021
—ORCID · none
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 2 · 2 since 2021
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2021 | Comparing Computational Entropies Below Majority (Or: When Is the Dense Model Theorem False?)
Russell Impagliazzo, Sam McGuire |
ITCS | 2 |
| 2021 | Log-rank and lifting for AND-functionsabstractLet f: {0, 1}n → {0, 1} be a boolean function, and let f∧(x, y) = f(x ∧ y) denote the AND-function of f, where x ∧ y denotes bit-wise AND. We study the deterministic communication complexity of f∧ and show that, up to a logn factor, it is bounded by a polynomial in the logarithm of the real rank of the communication matrix of f∧. This comes within a logn factor of establishing the log-rank conjecture for AND-functions with no assumptions on f. Our result stands in contrast with previous results on special cases of the log-rank conjecture, which needed significant restrictions on f such as monotonicity or low F2-degree. Our techniques can also be used to prove (within a logn factor) a lifting theorem for AND-functions, stating that the deterministic communication complexity of f∧ is polynomially related to the AND-decision tree complexity of f. Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan 0002 |
STOC | 3 |