Author name cluster

Theo McKenzie

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

STOC Conference 2024 Conference Paper

Explicit Two-Sided Unique-Neighbor Expanders

Jun-Ting Hsieh
Theo McKenzie
Sidhanth Mohanty
Pedro Paredes 0002

We study the problem of constructing explicit sparse graphs that exhibit strong vertex expansion. Our main result is the first two-sided construction of imbalanced unique-neighbor expanders, meaning bipartite graphs where small sets contained in both the left and right bipartitions exhibit unique-neighbor expansion, along with algebraic properties relevant to constructing quantum codes. Our constructions are obtained from instantiations of the tripartite line product of a large tripartite spectral expander and a sufficiently good constant-sized unique-neighbor expander, a new graph product we defined that generalizes the line product and the routed product of previous well-known works. To analyze the vertex expansion of graphs arising from the tripartite line product, we develop a sharp characterization of subgraphs that can arise in bipartite spectral expanders, generalizing previously known results, which may be of independent interest. By picking appropriate graphs to apply our product to, we give a strongly explicit construction of an infinite family of ( d 1 , d 2 )-biregular graphs ( G n ) n ≥ 1 (for large enough d 1 and d 2 ) where all sets S with fewer than a small constant fraction of vertices have Ω( d 1 · | S |) unique-neighbors (assuming d 1 ≤ d 2 ). Additionally, we can also guarantee that subsets of vertices of size up to exp(Ω(√log| V ( G n )|)) expand losslessly .

Details

STOC Conference 2021 Conference Paper

Support of closed walks and second eigenvalue multiplicity of graphs

Theo McKenzie
Peter Michael Reichstein Rasmussen
Nikhil Srivastava

We show that the multiplicity of the second normalized adjacency matrix eigenvalue of any connected graph of maximum degree Δ is bounded by O ( n Δ 7/5 /log 1/5− o (1) n ) for any Δ, and improve this to O ( n log 1/2 d /log 1/4− o (1) n ) for simple d -regular graphs when d ≥ log 1/4 n . In fact, the same bounds hold for the number of eigenvalues in any interval of width λ 2 /log Δ 1− o (1) n containing the second eigenvalue λ 2 . The main ingredient in the proof is a polynomial (in k ) lower bound on the typical support of a closed random walk of length 2 k in any connected graph, which in turn relies on new lower bounds for the entries of the Perron eigenvector of submatrices of the normalized adjacency matrix.

Details

SODA Conference 2020 Conference Paper

A New Algorithm for the Robust Semi-random Independent Set Problem

Theo McKenzie
Hermish Mehta
Luca Trevisan 0001

We study the independent set problem in a semi-random model proposed by Feige and Kilian. This model selects a graph with a planted independent set of size k and then allows an adversary to modify a large fraction of edges: the subgraph induced by the complement of the independent set can be modified arbitrarily, and the adversary may add (but not delete) edges from the independent set to its complement. In particular, the adversary can create a graph in which the initial planted independent set is not the largest independent set. Feige and Kilian presented a randomized algorithm, which with high probability recovers an independent set of size at least k (which may not be the planted one) when k = an where a is a constant, and the probability of a random edge p > (1 + ϵ) ln n/αn. We give a new deterministic algorithm in the Feige-Kilian model that finds an independent set of size at least. 99 k provided that the planted set has size k = Ω(n 2/3 / p 1/3 ), and finds a list of independent sets, one of which is the planted one provided that k = Ω( n 2/3 / p ). This improves on the algorithm of Feige and Kilian by working for smaller k if p = Ω(1/ n 1/3 ), and improves on an algorithm of Steinhardt by working for slightly smaller k and by working against a stronger adversarial model. The ability to find a good approximation of the largest independent set is new when p < ln n/k.

Details