̽��ϵ��

Notice of the Final Oral Examination for the Degree of Master of Science

Topic

Gadget Size Optimization in Disperser Properties: Foundations for Lifting Theorems

Department of Computer Science

Date & location

• Thursday, April 16, 2026

• 3:00 P.M.

• Virtual Defence

Reviewers

Supervisory Committee

• Dr. Sajin Koroth, Department of Computer Science, ̽��ϵ�� (Supervisor)

• Dr. Bruce Kapron, Department of Computer Science, UVic (Member)

• Dr. Natasha Morrison, Department of Mathematics and Statistics, UVic (Non-Unit Member) 

External Examiner

• Dr. Valentine Kabanets, Computing Sciences, Simon Fraser University 

Chair of Oral Examination

• Dr. Timothy Iles, School of Pacific and Asian Studies, UVic

   

Abstract

Lifting theorems translate query lower bounds into communication lower bounds via composition with a small gadget. This thesis advances that program by analyz ing the disperser behavior of the index gadget Indn m under entropy deficiency ∆, in relation to a conjecture of Lovett et al. We prove full production—i.e., Indn m(X,Y) ={0,1}n—in several regimes. In the non-excluding setting we show that m = ˜ Ω(2∆ logn) suffices; in particular, for constant ∆ this pins down the true threshold up to constants at m = Θ(logn), matching the known counterexample below logn and establishing truth above it. In a projection-aware variant, we prove that when m ≥ n there exists a set I ⊆ [n] with |I| = O(∆) such that the projection of the image to Ic is the full cube. Finally, on the balanced ground set Hn
m (half-weight memories), we break the logarithmic barrier and obtain full production already at m = ˜ Ω(2∆), independent of n. As a communication-complexity consequence, we derive Ω(logm) lower bounds for composed functions f ◦Indn m; in particular, for constant-query f this yields lifting lower bounds with gadgets as small as polylogn.
Methodologically, the proofs introduce a reusable extremal toolkit: size-preserving downward-closure transforms on pointers and memories, binary signature maps that recenter mass onto tractable Hamming layers, and an extremal maximization prin ciple showing that binary-lex initial segments optimize all weight-monotone objectives over downward-closed families. Together these ideas circumvent limitations of concentration-only arguments and open a path toward polylogarithmic gadgets in fully general settings, with prospective applications to circuit and proof complexity
as well as to other gadgets and restricted ground sets. The thesis concludes with a weighted extremal conjecture for projections and directions to tighten the projection bounds beyond the current m ≥ n barrier.