Sam McGuire

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

Office: CSE 4230

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 communication complexity, pseudorandomness, average-case complexity and combinatorics.

I co-organize the weekly UCSD CS theory lunch with Max Hopkins.

  1. Russell Impagliazzo, Sam McGuire. Computational lowers bounds on dense model theorems. In submission. [pdf (soon...)]
    We show lower bounds on two different types of dense model theorems. When the dense model theorem says that "dense subsets of pseudorandom sets have dense models", we show that this turns out to be false $\text{AC}^0$. We can also frame this result as saying the commonly-used information theoretic lemma that most bits of a dense subsets of the uniform distribution on $\{0, 1\}^n$ are unbiased is false when we replace 'uniform distribution' with 'distribution pseudorandom for $\text{AC}^0$'.

    When the dense model theorem says that "pseudodense subsets have dense models", we show that any proof of this fact can be used to solve a variant of the coin problem, which can further be used to approximate majority. We then show that this is tight in the sense that we give a proof of the dense model theorem that uses solutions to the coin problem instead of majority.

    A few other observations related to pseudoentropy, hardcore lemmas and boosting are made along the way.
  2. Sam McGuire. Model Checking Sparse Structures in Dynamic Descriptive Complexity Theory. 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.