@phdthesis{10.7907/Z9J67DXZ, author = {Lu, Daodi}, title = {Quasiparabolic Subgroups of Coxeter Groups and Their Hecke Algebra Module Structures}, school = {California Institute of Technology}, year = {2017}, doi = {10.7907/Z9J67DXZ}, url = {https://resolver.caltech.edu/CaltechTHESIS:11042016-133007537}, abstract = {It is well known that the R-polynomial can be defined for the Hecke algebra of Coxeter groups, and the Kazhdan-Lusztig theory can be developed to understand the representations of Hecke algebra. There is also a generalization for the existence of R-polynomial and Kazhdan-Lusztig theory for the Hecke algebra module of standard parabolic subgroups of Coxeter groups. In recent work of Rains and Vazirani, a generalization of standard parabolic subgroups, called quasiparabolic subgroups, are introduced, and the corresponding Hecke algebra module is well-defined. However, the existence of the analogous involution (Kazhdan-Lusztig bar operator) on the Hecke algebra module of quasiparabolic subgroups is unknown in general. Assuming the existence of the bar-operator, the corresponding R-polynomials and Kazhdan-Lusztig polynomials can be constructed. We prove the existence of the bar operator for the corresponding Hecke algebra modules of quasiparabolic subgroups in finite classical Coxeter groups with a case-by-case verification (Chapter 4). As preparation, we classify all quasiparabolic subgroups of finite classical Coxeter groups. The approach is to first find all rotation subgroups of finite classical Coxeter groups (Chapter 2). Then we exclude the non-quasiparabolic subgroups and confirm the quasiparabolic subgroups (Chapter 3).}, address = {1200 East California Boulevard, Pasadena, California 91125}, advisor = {Rains, Eric M.}, } @phdthesis{10.7907/Z92N507D, author = {Sinha, Gaurav}, title = {Blackbox Reconstruction of Depth Three Circuits with Top Fan-In Two}, school = {California Institute of Technology}, year = {2016}, doi = {10.7907/Z92N507D}, url = {https://resolver.caltech.edu/CaltechTHESIS:06082016-032155301}, abstract = {
Reconstruction of arithmetic circuits has been heavily studied in the past few years and has connections to proving lower bounds and deterministic identity testing. In this thesis we present a polynomial time randomized algorithm for reconstructing ΣΠΣ(2) circuits over characteristic zero fields F i.e. depth−3 circuits with fan-in 2 at the top addition gate and having coefficients from a field of characteristic zero.
The algorithm needs only a black-box query access to the polynomial f ∈ F[x1,…,xn] of degree d, computable by a ΣΠΣ(2) circuit C. In addition, we assume that the “simple rank” of this polynomial (essential number of variables after removing the g.c.d. of the two multiplication gates) is bigger than a fixed constant. Our algorithm runs in time polynomial in n and d and with high probability returns an equivalent ΣΠΣ(2) circuit.
The problem of reconstructing ΣΠΣ(2) circuits over finite fields was first proposed by Shpilka [27]. The generalization to ΣΠΣ(k) circuits, k = O(1) (over finite fields) was addressed by Karnin and Shpilka in [18]. The techniques in these previous involve iterating over all objects of certain kinds over the ambient field and thus the running time depends on the size of the field F. Their reconstruction algorithm uses lower bounds on the lengths of linear locally decodable codes with 2 queries.
In our setting, such ideas immediately pose a problem and we need new techniques.
Our main techniques are based on the use of quantitative Sylvester Gallai theorems from the work of Barak et.al. [3] to find a small collection of “nice” subspaces to project onto. The heart of this work lies in subtle applications of the quantitative Sylvester Gallai theorems to prove why projections w.r.t. the “nice” subspaces can be ”glued”. We also use Brill’s equations from [9] to construct a small set of candidate linear forms (containing linear forms from both gates). Another important technique which comes very handy is the polynomial time randomized algorithm for factoring multivariate polynomials given by Kaltofen [17].
}, address = {1200 East California Boulevard, Pasadena, California 91125}, advisor = {Rains, Eric M.}, } @phdthesis{10.7907/KMK9-6493, author = {Huang, Jingjing}, title = {Determinantal Hypersurface from a Geometric Perspective}, school = {California Institute of Technology}, year = {2013}, doi = {10.7907/KMK9-6493}, url = {https://resolver.caltech.edu/CaltechTHESIS:05022013-153358975}, abstract = {In this paper, we give a geometric interpretation of determinantal forms, both in the case of general matrices and symmetric matrices. We will prove irreducibility of the determinantal singular loci and state its dimension. We also provide detailed description of the singular locus for small dimensions.}, address = {1200 East California Boulevard, Pasadena, California 91125}, advisor = {Rains, Eric M.}, } @phdthesis{10.7907/MMZG-5G61, author = {Betea, Dan Dumitru}, title = {Elliptic Combinatorics and Markov Processes}, school = {California Institute of Technology}, year = {2012}, doi = {10.7907/MMZG-5G61}, url = {https://resolver.caltech.edu/CaltechTHESIS:05312012-201348939}, abstract = {We present combinatorial and probabilistic interpretations of recent results in the theory of elliptic special functions (due to, among many others, Frenkel, Turaev, Spiridonov, and Zhedanov in the case of univariate functions, and Rains in the multivariate case). We focus on elliptically distributed random lozenge tilings of the hexagon which we analyze from several perspectives. We compute the N-point function for the associated process, and show the process as a whole is determinantal with correlation kernel given by elliptic biorthogonal functions. We furthermore compute transition probabilities for the Markov processes involved and show they come from the multivariate elliptic difference operators of Rains. Properties of difference operators yield an efficient sampling algorithm for such random lozenge tilings. Simulations of said algorithm lead to new arctic circle behavior. Finally we introduce elliptic Schur processes on bounded partitions analogous to the Schur process of Reshetikhin and Okounkov ( and to the Macdonald processes of Vuletic, Borodin, and Corwin). These give a somewhat different (and faster) sampling algorithm from these elliptic distributions, but in principle should encompass more than just tilings of a hexagon.}, address = {1200 East California Boulevard, Pasadena, California 91125}, advisor = {Rains, Eric M.}, } @phdthesis{10.7907/682S-3125, author = {Venkateswaran, Vidya}, title = {Vanishing Results for Hall-Littlewood Polynomials}, school = {California Institute of Technology}, year = {2012}, doi = {10.7907/682S-3125}, url = {https://resolver.caltech.edu/CaltechTHESIS:06082012-201004802}, abstract = {It is well-known that if one integrates a Schur function indexed by a partition λ over the symplectic (resp. orthogonal) group, the integral vanishes unless all parts of λ have even multiplicity (resp. all parts of λ are even). In a recent work of Rains and Vazirani, Macdonald polynomial generalizations of these identities and several others were developed and proved using Hecke algebra techniques. However at q=0 (the Hall-Littlewood level), these approaches do not directly work; this obstruction was the motivation for this thesis. We investigate three related projects in chapters 2-4 (the first chapter consists of an introduction to the thesis). In the second chapter, we develop a combinatorial technique for proving the results of Rains and Vazirani at q=0. This approach allows us to generalize some of those results in interesting ways and leads us to a finite-dimensional analog of a recent result of Warnaar, involving the Rogers-Szego polynomials. In the third chapter, we provide a new construction for Koornwinder polynomials at q=0, allowing these polynomials to be viewed as Hall-Littlewood polynomials of type BC. This is a first step in building the analogy between the Macdonald and Koornwinder families at the q=0 limit. We use this construction in conjunction with the combinatorial technique of the previous chapter to prove some vanishing results of Rains and Vazirani for Koornwinder polynomials at q=0. In the fourth chapter, we provide an interpretation for vanishing results for Hall-Littlewood polynomials using p-adic representation theory; it is an analog of the Schur case. This p-adic approach allows us to generalize our original vanishing results. In particular, we exhibit a t-analog of a classical vanishing result for Schur functions due to Littlewood and Weyl; our vanishing condition is in terms of Hall polynomials and Littlewood-Richardson coefficients.}, address = {1200 East California Boulevard, Pasadena, California 91125}, advisor = {Rains, Eric M.}, }