Sam McGuire

Department of Computer Science & Engineering
University of California, San Diego

Office: CSE 4230
Hi! I'm a PhD student in the theory group at UCSD working with Russell Impagliazzo and Shachar Lovett. Previously, I received my BS at UMass Amherst, where I worked with Neil Immerman. I am interested in core topics in computational complexity, including circuit complexity and communication complexity, as well as topics related to average-case complexity, such as random optimization problems. More generally, I like probability, combinatorics and randomness in computation.

Outside of academics, I am, for example, a musician, a Boston Celtics fan and a twin. My pronouns are he/him or they/them. I value honesty, transparency and clarity in communication in both personal and scientific contexts. If you think I'm bad at this, (or have some other feedback or comment you'd like to make anonymously) feel free to let me know. In the version of the past where large groups of people ate lunch in the same room, Max Hopkins and I co-organized the weekly UCSD CS theory lunch.

Papers. Sorted in decreasing chronological order. Authors listed alphabetically, per TCS tradition.
  1. Log-rank and lifting for AND-functions. Alexander Knop, Shachar Lovett, SM, Weiqiang Yuan. To appear, STOC 2021. [pdf]
    Let $f: \{0,1\}^n \to \{0, 1\}$ be a boolean function, and let $f_\land (x, y) = f(x \land y)$ denote the AND-function of $f$, where $x \land y$ denotes bit-wise AND. We study the deterministic communication complexity of $f_\land$ and show that, up to a $\log n$ factor, it is bounded by a polynomial in the logarithm of the real rank of the communication matrix of $f_\land$. This comes within a $\log n$ factor of establishing the log-rank conjecturefor 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 $\mathbb{F}_2$-degree. Our techniques can also be used to prove (within a $\log n$ factor) a lifting theorem for AND-functions, stating that the deterministic communication complexity of $f_\land$ is polynomially-related to the AND-decision tree complexity of $f$.

    The results rely on a new structural result regarding boolean functions $f:\{0, 1\}^n \to \{0, 1\}$ with a sparse polynomial representation, which may be of independent interest. We show that if the polynomial computing $f$ has few monomials then the set system of the monomials has a small hitting set, of size poly-logarithmic in its sparsity. We also establish extensions of this result to multi-linear polynomials $f:\{0,1\}^n \to \mathbb{R}$ with a larger range.

  2. Comparing computational entropies below majority (or: When is the dense model theorem false?) Russell Impagliazzo, SM. ITCS 2021. [pdf] [talk]
    Computational pseudorandomness studies the extent to which a random variable $\mathbf{Z}$ looks like the uniform distribution according to a class of tests $\mathcal{F}$. Computational entropy generalizes computational pseudorandomness by studying the extent which a random variable looks like a high entropy distribution. There are different formal definitions of computational entropy with different advantages for different applications. Because of this, it is of interest to understand when these definitions are equivalent.

    We consider three notions of computational entropy which are known to be equivalent when the test class $\mathcal{F}$ is closed under taking majorities. This equivalence constitutes (essentially) the so-called dense model theorem of Green and Tao (and later made explicit by Tao-Zeigler, Reingold et al., and Gowers). The dense model theorem plays a key role in Green and Tao's proof that the primes contain arbitrarily long arithmetic progressions and has since been connected to a surprisingly wide range of topics in mathematics and computer science, including cryptography, computational complexity, combinatorics and machine learning. We show that, in different situations where $\mathcal{F}$ is not closed under majority, this equivalence fails. This in turn provides the first examples to appear in the literature in which the dense model theorem is false.

  3. Model Checking Sparse Structures in Dynamic Descriptive Complexity Theory. SM. Undergraduate thesis. [pdf]
    Dynamic descriptive complexity seeks to characterize the complexity of queries in terms of the logical language required to express update programs that maintain them. It is a natural notion in the study of relational databases: the database is subject to change and the total re-computation of a query may not be feasible due to both the rate of change, the static complexity of the query, or simply the size of the database in question.

    Here, we present a $\text{Dyn-QF}$ algorithm for model-checking $\text{FO}$ properties on bounded-degree structures. The main technical tool is an algorithm for maintaining the neighborhoods of elements in bounded-degree structures, which can be then be applied to perform model checking on particular logics admitting local normal forms. As applications of the methodology, we show algorithms for maintaining the number of witnesses to a first-order property and model checking the counting logic $\text{FOCN}(\textbf{P})$ recently introduced by Kuske and Schweikardt. This in turn establishes $\text{Dyn-QF}$ algorithms for simulating $\text{FO}(COUNT)$ properties on bounded-degree structures, making partial progress towards the conjecture that $\text{FO}(COUNT) \subseteq \text{Dyn-FO}$, originally made by Patnaik and Immerman in the '90s.

Teaching. I have had the good fortune of TAing the following classes over my career thus far:

On exactitude in science. Jorge Luis Borges.

...In that Empire, the Art of Cartography attained such Perfection that the map of a single Province occupied the entirety of a City, and the map of the Empire, the entirety of a Province. In time, those Unconscionable Maps no longer satisfied, and the Cartographers Guilds struck a Map of the Empire whose size was that of the Empire, and which coincided point for point with it. The following Generations, who were not so fond of the Study of Cartography as their Forebears had been, saw that that vast Map was Useless, and not without some Pitilessness was it, that they delivered it up to the Inclemencies of Sun and Winters. In the Deserts of the West, still today, there are Tattered Ruins of that Map, inhabited by Animals and Beggars; in all the Land there is no other Relic of the Disciplines of Geography.

- Suarez Miranda, Viajes devarones prudentes, Libro IV, Cap. XLV, Lerida, 1658