Bohdan Kivva

I am a PhD student in the joint Mathematics & Computer Science PhD program at University of Chicago (2016 - Present)

I am extremely lucky to be advised by Prof. László Babai and co-advised by Prof. Aaron Potechin. You can find a draft of my thesis here.

I am broadly interested in Theoretical computer science, Combinatorics and Learning Theory.

I have been doing research in essentially four different directions: symmetry vs regularity, tensor completion and decomposition problems, causal discovery, and matrix rigidity.

Below you can find the list of my publications in inverse chronological order. You can also see the publications organised by topic with a brief summary for each paper.

Remember Yuliia Zdanovska (2000-2022, Kharkiv) (text by László Babai)

Preprints and Publications

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

    arXiv:2110.13861 (Oct 2021, 51 pages)

  2. "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)

  3. "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)

  4. "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, 202 (2021). 68:1--68:18   [pdf]   arXiv:2103.05631

  5. "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]

  6. "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)

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

  8. "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

  9. "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

  10. "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)

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

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

Conference and seminar talks

  1. ``46th International Symposium on Mathematical Foundations of Computer Science'' (MFCS'21),

    Online, August 2021

  2. 36th Computational Complexity Conference (CCC'21),

    Online, July 2021   (video)

  3. The Canadian Discrete and Algorithmic Mathematics Conference (CanaDAM) 2021, "Coherent configurations with few fibers" minisymposium (invited speaker),

    Online, May 2021   (video)

  4. The Canadian Discrete and Algorithmic Mathematics Conference (CanaDAM) 2019 conference, "Graph symmetry" minisymposium (invited speaker),

    Vancouver, Canada, May 2019

  5. "Symmetry breaking in discrete structures" BIRS workshop (invited speaker),

    Oaxaca, Mexico, September 2018   (video 1)   (video 2)

  6. "Symmetry vs Regularity" conference (invited speaker),

    Pilsen, Czech Republic, July 2018

  7. Combinatorics and Theoretical Computer Science seminar,

    University of Chicago, Chicago, IL, USA, April 2018

Teaching

  • Instructor in Math 15200 "Calculus II", Fall 2021

  • Instructor in Math 15200 "Calculus II", Fall 2020

  • Instructor in Math 15300 "Calculus III", Winter 2020

  • Instructor in Math 15200 "Calculus II", Fall 2019

  • Instructor in Math 13300 "Elem Functions and Calculus III", Spring 2019

  • Instructor in Math 13200 "Elem Functions and Calculus II", Winter 2019

  • Instructor in Math 13100 "Elem Functions and Calculus I", Fall 2018

  • TA in Math 16300 "Honours Calculus III", Spring 2018 (taught by Prof. Fefferman)

  • TA in Math 25500 "Basic Algebra-2", Winter 2018 (taught by Prof. Stehnova)

  • TA in Math 25400 "Basic Algebra-1", Fall 2018 (taught by Prof. Stehnova)