Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data. A simulation from public publication records: the people listed were not invited and did not agree to review.
? Tutorial for this page

Sam McGuire

dblp:276/6621 · DBLP profile ↗
← Back
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

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 5 heaviest of 5, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Computational complexity › boolean function complexity
and-functions
0.512021
Log-rank and lifting for AND-functions · STOC 2021
Computational complexity
communication complexity
0.512021
Log-rank and lifting for AND-functions · STOC 2021
Computational complexity › query complexity
decision tree complexity
0.512021
Log-rank and lifting for AND-functions · STOC 2021
Computational complexity › query complexity
lifting theorems
0.512021
Log-rank and lifting for AND-functions · STOC 2021
Computational complexity › communication complexity › deterministic communication complexity
log-rank conjecture
0.512021
Log-rank and lifting for AND-functions · STOC 2021

Methods — techniques the papers use, named apart from their topics

rank-based analysis · 0.5lifting · 0.5
YearPublicationVenuePosition
2021 Comparing Computational Entropies Below Majority (Or: When Is the Dense Model Theorem False?)
Russell Impagliazzo, Sam McGuire
ITCS2
2021 Log-rank and lifting for AND-functions
abstract
Let 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
STOC3