Papers and Preprints

In published work I use my full first name, Dmitriy. Peer-reviewed publications are marked [in green] while preprints and other materials are marked [in blue].


Computational lower bounds for multi-frequency group synchronization
Anastasia Kireeva, Afonso S. Bandeira, Dmitriy Kunisky

Tensor cumulants for statistical inference on invariant distributions
Dmitriy Kunisky, Cristopher Moore, Alexander S. Wein
[FOCS 2024, to appear] [arXiv:2404.18735]

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
Dmitriy Kunisky, Xifan Yu
[FOCS 2024, to appear] [arXiv:2404.17012]

Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing
Dmitriy Kunisky
[arXiv:2403.07862] [Video (40 min)]


Fitting an ellipsoid to random points: predictions using the replica method
Antoine Maillard, Dmitriy Kunisky
[IEEE Transactions on Information Theory, to appear] [arXiv:2310.01169]

Optimality of Glauber dynamics for general-purpose Ising model sampling and free energy approximation
Dmitriy Kunisky
[SODA 2024] [arXiv:2307.12581] [Slides]

Online algorithms and lower bounds for average-case matrix discrepancy
Dmitriy Kunisky, Peiyuan Zhang

Spectral pseudorandomness and the road to improved clique number bounds for Paley graphs
Dmitriy Kunisky
[Experimental Mathematics, pending] [arXiv:2303.16475] [Slides] [Video (60 min)]

Generic MANOVA limit theorems for products of projections
Dmitriy Kunisky
[arXiv:2301.09543] [Slides]


On the concentration of Gaussian Cayley matrices
Afonso S. Bandeira, Dmitriy Kunisky, Dustin G. Mixon, Xinmeng Zeng
[Applied and Computational Harmonic Analysis (ACHA), pending] [arXiv:2212.00066]

A degree 4 sum-of-squares lower bound for the clique number of the Paley graph
Dmitriy Kunisky, Xifan Yu
[CCC 2023] [arXiv:2211.02713] [Slides] [Video (35 min)]

The spectrum of the Grigoriev-Laurent pseudomoments
Dmitriy Kunisky, Cristopher Moore
[SIAM J. Discrete Mathematics (SIDMA) 38, No. 1, 2024] [arXiv:2203.05693] [Slides]

Dual bounds for the positive definite functions approach to mutually unbiased bases
Afonso S. Bandeira, Nikolaus Doppelbauer, Dmitriy Kunisky
[Sampling Theory, Signal Processing, and Data Analysis 20, No. 18, 2022] [arXiv:2202.13259] [Supplementary Materials] [Video (50 min)]


The discrepancy of unsatisfiable matrices and a lower bound for the Komlós conjecture constant
Dmitriy Kunisky
[SIAM J. Discrete Mathematics (SIDMA) 37, No. 2, 2023] [arXiv:2111.02974]

Strong recovery of geometric planted matchings
Dmitriy Kunisky, Jonathan Niles-Weed
[SODA 2022] [arXiv:2107.05567] [Video (30 min)]


Average-case integrality gap for non-negative principal component analysis
Afonso S. Bandeira, Dmitriy Kunisky, Alexander S. Wein
[MSML 2021] [arXiv:2012.02243] [Slides] [Video (15 min)]

Hypothesis testing with low-degree polynomials in the Morris class of exponential families
Dmitriy Kunisky
[COLT 2021] [arXiv:2011.03693] [Videos] [Poster]

Positivity-preserving extensions of sum-of-squares pseudomoments over the hypercube
Dmitriy Kunisky
[arXiv:2009.07269] [Video (30 min)]

Spectral planting and the hardness of refuting cuts, colorability, and communities in random graphs
Afonso S. Bandeira, Jess Banks, Dmitriy Kunisky, Cristopher Moore, Alexander S. Wein
[COLT 2021] [arXiv:2008.12237] [Videos (by Jess Banks)]

Linear programming and community detection
Alberto Del Pia, Aida Khajavirad, Dmitriy Kunisky
[Mathematics of Operations Research, 2022] [arXiv:2006.03213]

The average-case time complexity of certifying the restricted isometry property
Yunzi Ding, Dmitriy Kunisky, Alexander S. Wein, Afonso S. Bandeira
[IEEE Transactions on Information Theory, 2021] [arXiv:2005.11270]


A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian
Dmitriy Kunisky, Afonso S. Bandeira
[Mathematical Programming 190, No. 1, 2021] [arXiv:1907.11686]

Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
Dmitriy Kunisky, Alexander S. Wein, Afonso S. Bandeira
[ISAAC 2019] [arXiv:1907.11636] [Slides]

Subexponential-time algorithms for sparse PCA
Yunzi Ding, Dmitriy Kunisky, Alexander S. Wein, Afonso S. Bandeira
[Foundations of Computational Mathematics, 2023] [arXiv:1907.11635]

Mapping political communities: a statistical analysis of lobbying networks in legislative politics
In Song Kim, Dmitriy Kunisky
[Political Analysis 29, No. 3, 2021] [Replication Materials]

Computational hardness of certifying bounds on constrained PCA problems
Afonso S. Bandeira, Dmitriy Kunisky, Alexander S. Wein
[ITCS 2020] [arXiv:1902.07324] [Slides]

Connections between sum-of-squares optimization and structured tight frames
Afonso S. Bandeira, Dmitriy Kunisky
[SPIE Wavelets and Sparsity 2019] [Slides]

Sum-of-squares optimization and the sparsity structure of equiangular tight frames
Afonso S. Bandeira, Dmitriy Kunisky
[SampTA 2019] [arXiv:1901.10697] [Slides]


A Gramian description of the degree 4 generalized elliptope
Afonso S. Bandeira, Dmitriy Kunisky
[arXiv:1812.11583] [Supplementary Materials] [Poster]
Best Poster Award at 2018 Princeton Day of Optimization

Hysteresis control of epithelial-mesenchymal transition dynamics conveys a distinct program with enhanced metastatic ability
Toni Celià-Terrassa, Caleb Bastian, Daniel D. Liu, Brian Ell, Nicole M. Aiello, Yong Wei, Jose Zamalloa, Andres M. Blanco, Xiang Hang, Dmitriy Kunisky, Wenyang Li, Elizabeth D. Williams, Herschel Rabitz, Yibin Kang
[Nature Communications 9, No. 1, 2018]

Other Writing

Spectral barriers in certification problems
Dmitriy Kunisky (PhD thesis)
[PDF] [Slides]

The theft and the honest toil: applications of large cardinal axioms to the theory of measurable selection
Dmitriy Kunisky (Undergraduate Senior Thesis, 2014)
Note: If you are curious about this topic, my advisor John Burgess later wrote the paper Measurable Selections: A Bridge Between Large Cardinals and Scientific Applications? (2021) that talks about my work and related developments much more clearly than I could muster in my thesis.

Discrete applications of Brownian motion
Dmitriy Kunisky (Undergraduate Junior Paper, 2013)