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

Inference of rankings planted in random tournaments
Dmitriy Kunisky, Daniel A. Spielman, Xifan Yu
[arXiv:2407.16597]

Computational lower bounds for multi-frequency group synchronization
Anastasia Kireeva, Afonso S. Bandeira, Dmitriy Kunisky
[arXiv:2406.03424]

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]

Average-case matrix discrepancy: asymptotics and online algorithms
Dmitriy Kunisky, Peiyuan Zhang
[arXiv:2307.10055]
Note: The first version of this paper was called "Online algorithms and lower bounds for average-case matrix discrepancy," which we revised after broadening the scope of the results in an update.

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)
[PDF]
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)
[PDF]