List of publications by topic

Symmetry vs Regularity, Coherent Configurations, Distance-Regular Graphs [Combinatorics]

  1. "On the automorphism groups of rank-4 primitive coherent configurations"

    arXiv:2110.13861 (Oct 2021, 51 pages)

    Brief summary
    In the wake of Cameron's classification of large primitive permutation groups Babai made the conjecture that PCCs other than the so-called "Cameron schemes" have restricted groups of symmetries. This paper confirms a version of this conjecture for rank-4 primitive coherent configurations (PCCs).
    The minimal degree of a permutation group $G$ is the minimum number of points not fixed by non-identity elements of $G$. Lower bounds on the minimal degree have strong structural consequences on $G$. In 2014 Babai proved that the automorphism group of rank-3 PCCs with $n$ vertices has minimal degree $\geq n/8$, with known exceptions. He conjectured that the automorphism of any non-Cameron PCC has linear minimal degree. This conjecture can be viewed as a combinatorial relaxation of the Liebeck-Saxl classification of primitive permutation groups with sublinear minimal degree established through the Classification of Finite Simple Groups.
    In this paper we prove Babai's conjecture for PCCs of rank 4, i.e., we show that the authomorphism group of every PCC, other than Johnson or Hamming scheme, has linear minimal degree.

  2. "Robustness of the Johnson schemes under fusion and extension" joint with László Babai (2021, in preparation)

    Brief summary
    In this paper we prove that if a Johnson scheme is "nicely embedded" into a homogeneous coherent configuration X on 99% of vertices of X, then X is a Johnson scheme itself. This result simplifies the claim of the Split-or-Johnson Lemma, the key combinatorial lemma of Babai's breakthrough Graph Isomorphism test (2015). The Split-or-Johnson lemma claims that in the quasipolynomial cost one can either find a canonical coloring of X that breaks its symmetry significantly, or one can find a canonically "nicely embedded'' Johnson scheme on 99% of the vertices of X. Our result can also be seen as a generalization of the the Kaluzhnin-Klin theorem (1972) on fusion of Johnson schemes.

  3. "A characterization of Johnson and Hamming graphs and proof of Babai's conjecture"

    J. Comb. Theory, Ser. B, 151 (2021), pp. 339-374   [pdf]   arXiv:1912.11427

    Brief summary
    One of the central results in the representation theory of distance-regular graphs classifies distance-regular graphs with $\mu\geq 2$ and second largest eigenvalue $\theta_1 = b_1-1$. In this paper we give a classification under the (weaker) approximate eigenvalue constraint $\theta_1\geq (1-\varepsilon)b_1$ for the class of geometric distance-regular graphs. As an application, we confirm Babai's conjecture on the minimal degree of the automorphism group of distance-regular graphs.

  4. "On the spectral gap and the automorphism group of distance-regular graphs"

    J. Comb. Theory, Ser B, 149 (2021), pp. 161-197   [pdf]   arXiv:1912.10571

    Brief summary
    We prove that a distance-regular graph with a dominant distance is a spectral expander. The key ingredient of the proof is a new inequality on the intersection numbers. We use the spectral gap bound to study the structure of the automorphism group.
    The minimal degree of a permutation group $G$ is the minimum number of points not fixed by non-identity elements of $G$. Lower bounds on the minimal degree have strong structural consequences on $G$. In 2014 Babai proved that the automorphism group of a strongly regular graph with $n$ vertices has minimal degree $\geq cn$, with known exceptions. Strongly regular graphs correspond to distance-regular graphs of diameter 2. Babai conjectured that Hamming and Johnson graphs are the only primitive distance-regular graphs of diameter $d\geq 3$ whose automorphism group has sublinear minimal degree. We confirm this conjecture for non-geometric primitive distance-regular graphs of bounded diameter. We also show if the primitivity assumption is removed, then only one additional family of exceptions arises, the cocktail-party graphs. We settle the geometric case in a companion paper.

  5. "On the automorphism groups of distance-regular graphs and rank-4 primitive coherent configurations"

    arXiv:1802.06959 (Feb 2018, 70 pages; This is an early version of what became two papers: #3, #11. Reorganization is motivated by results in #4)

Tensor Completion and Decomposition problems [Theoretical CS, Learning theory]

  1. "Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 SOS" joint with Aaron Potechin

    arXiv:2011.09416 (Nov 2020, 135 pages)

    Brief summary
    In this paper we show that simple semidefinite programs inspired by degree $4$ SOS can exactly solve the tensor nuclear norm, tensor decomposition, and tensor completion problems on tensors with random asymmetric components. More precisely, for tensor nuclear norm and tensor decomposition, we show that w.h.p. these semidefinite programs can exactly find the nuclear norm and components of an $(n\times n\times n)$-tensor $\mathcal{T}$ with $m\leq n^{3/2}/polylog(n)$ random asymmetric components. Unlike most of the previous algorithms, our algorithm provides a certificate for the decomposition, does not require knowledge about the number of components in the decomposition and does not make any assumptions on the sizes of the coefficients in the decomposition. As a byproduct, we show that w.h.p. the nuclear norm decomposition exactly coincides with the minimum rank decomposition for tensors with $m\leq n^{3/2}/polylog(n)$ random asymmetric components.
    For tensor completion, we show that w.h.p. the semidefinite program, introduced by Potechin & Steurer (2017) for tensors with orthogonal components, can exactly recover an $(n\times n\times n)$-tensor $\mathcal{T}$ with $m$ random asymmetric components from only $n^{3/2}m polylog(n)$ randomly observed entries. For non-orthogonal tensors this improves the dependence on $m$ of the number of entries needed for exact recovery over all previously known algorithms and provides the first theoretical guarantees for exact tensor completion in the overcomplete regime.

Causal Discovery [Learning Theory, Causality]

  1. "Learning latent causal graphs via mixture oracles" Bohdan Kivva, Goutham Rajendran, Pradeep Ravikumar and Bryon Aragam

    To appear at NeurIPS'21.   arXiv:2106.15563 (Jun 2021, 37 pages)

    Brief summary
    We study the problem of reconstructing a causal graphical model from data in the presence of latent variables. The main problem of interest is recovering the causal structure over the latent variables while allowing for general, potentially nonlinear dependencies. In many practical problems, the dependence between raw observations (e.g. pixels in an image) is much less relevant than the dependence between certain high-level, latent features (e.g. concepts or objects), and this is the setting of interest. We provide conditions under which both the latent representations and the underlying latent causal model are identifiable by a reduction to a mixture oracle. These results highlight an intriguing connection between the well-studied problem of learning the order of a mixture model and the problem of learning the bipartite structure between observables and unobservables. The proof is constructive, and leads to several algorithms for explicitly reconstructing the full graphical model. We discuss efficient algorithms and provide experiments illustrating the algorithms in practice.

  2. "Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families" Goutham Rajendran, Bohdan Kivva, Ming Gao and Bryon Aragam.

    To appear at NeurIPS'21.   arXiv:2110.04719 (Oct 2021, 36 pages)

    Brief summary
    Greedy algorithms have long been a workhorse for learning graphical models, and more broadly for learning statistical models with sparse structure. In the context of learning directed acyclic graphs, greedy algorithms are popular despite their worst-case exponential runtime. In practice, however, they are very efficient. We provide new insight into this phenomenon by studying a general greedy score-based algorithm for learning DAGs. Unlike edge-greedy algorithms such as the popular GES and hill-climbing algorithms, our approach is vertex-greedy and requires at most a polynomial number of score evaluations. We then show how recent polynomial-time algorithms for learning DAG models are a special case of this algorithm, thereby illustrating how these order-based algorithms can be rigourously interpreted as score-based algorithms. This observation suggests new score functions and optimality conditions based on the duality between Bregman divergences and exponential families, which we explore in detail. Explicit sample and computational complexity bounds are derived. Finally, we provide extensive experiments suggesting that this algorithm indeed optimizes the score in a variety of settings.

Matrix Rigidity [Theoretical CS, Combinatorics]

  1. "Improved upper bounds for the rigidity of Kronecker products"

    In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS'21), Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, volume 202, 2021. 68:1--68:18   [pdf]   arXiv:2103.05631 (Mar 2021)

    Brief summary
    The rigidity of a matrix $A$ for target rank $r$ is the minimum number of entries of A that need to be changed in order to obtain a matrix of rank at most $r$. At MFCS'77, Valiant introduced matrix rigidity as a tool to prove circuit lower bounds for linear functions and since then this notion received much attention and found applications in other areas of complexity theory. The problem of constructing an explicit family of matrices that are sufficiently rigid for Valiant’s reduction (Valiant-rigid) still remains open. Moreover, since 2017 most of the long-studied candidates have been shown not to be Valiant-rigid.
    Some of those former candidates for rigidity are Kronecker products of small matrices. In a recent paper (STOC'21), Alman gave a general non-rigidity result for such matrices: he showed that if an $n\times n$ matrix $A$ (over any field) is a Kronecker product of $d\times d$ matrices $M_1, M_2, \ldots, M_k$ (so $n= d^k$) ($d\geq 2$) then changing only $n^{1+\varepsilon}$ entries of $A$ one can reduce its rank to $\leq n^{1-\gamma}$, where $1/\gamma$ is roughly $2^d/\varepsilon^2$.
    In this note we improve this result in two directions. First, we do not require the matrices $M_i$ to have equal size. Second, we reduce $1/\gamma$ from exponential in $d$ to roughly $d^{3/2}/\varepsilon^2$ (where $d$ is the maximum size of the matrices $M_i$), and to nearly linear (roughly $d/\varepsilon^2$) for matrices $M_i$ of sizes within a constant factor of each other. As an application of our results we significantly expand the class of Hadamard matrices that are known not to be Valiant-rigid; these now include the Kronecker products of Paley-Hadamard matrices and Hadamard matrices of bounded size.

  2. "Matrix rigidity depends on the target field" joint with László Babai.

    In 36th Computational Complexity Conf. (CCC’21). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 200 (2021), pp. 41:1-41:26   [pdf]

    Brief summary
    The rigidity of a matrix $A$ for target rank $r$ is the minimum number of entries of $A$ that need to be changed in order to obtain a matrix of rank at most $r$ (Valiant, 1977).
    We study the dependence of rigidity on the target field. We consider especially two natural regimes: when one is allowed to make changes only from the field of definition of the matrix ("strict rigidity"), and when the changes are allowed to be in an arbitrary extension field ("absolute rigidity"). We demonstrate, apparently for the first time, a separation between these two concepts. We establish a gap of a factor of $3/2-o(1)$ between strict and absolute rigidities.
    The question seems especially timely because of recent results by Dvir and Liu (Theory of Computing, 2020) where important families of matrices, previously expected to be rigid, are shown not to be absolutely rigid, while their strict rigidity remains open. Our lower-bound method combines elementary arguments from algebraic geometry with "untouched minors" arguments.
    Finally, we point out that more families of long-time rigidity candidates fall as a consequence of the results of Dvir and Liu. These include the incidence matrices of projective planes over finite fields, proposed by Valiant as candidates for rigidity over $\mathbb{F}_2$.

Automaton groups, Non-residually finite groups [Group Theory, Combinatorics]

  1. "Automaton groups and complete square complexes" joint with Ievgen Bondarenko

    accepted to the journal "Groups, Geometry, and Dynamics",   arXiv:1707.00215 (Jul 2017, 29 pages)

    Brief summary
    The first example of a non-residually finite group in the classes of finitely presented small-cancelation groups, automatic groups, and CAT(0) groups was constructed by Wise as the fundamental group of a complete square complex (CSC for short) with twelve squares. At the same time, Janzen and Wise proved that CSCs with at most three squares, five or seven squares have residually finite fundamental group. The smallest open cases were CSCs with four squares and directed complete VH complexes with six squares. We prove that the CSC with four squares studied by Janzen and Wise has a non-residually finite fundamental group. In particular, this gives a non-residually finite CAT(0) group isometric to $F_2\times F_2$. For the class of complete directed VH complexes, we prove that there are exactly two complexes with six squares having a non-residually finite fundamental group. In particular, this positively answers to a question of Wise on whether the main example from his PhD thesis is non-residually finite. As a by-product, we get finitely presented torsion-free simple groups which decompose into an amalgamated free product of free groups $F_7*_{F_{49}}F_7$.
    Our approach relies on the connection between square complexes and automata discovered by Glasner and Mozes, where complete VH complexes with one vertex correspond to bireversible automata. We prove that the square complex associated to a bireversible automaton with two states or over the binary alphabet generating an infinite automaton group has a non-residually finite fundamental group. We describe automaton groups associated to CSCs with four squares and get two simple automaton representations of the free group $F_2$ and the first automaton representation of the free product $C_3*C_3$.