EKEren C. Kızıldağ

Eren C. Kızıldağ

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Eren C. Kızıldağ has a total of 4 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Planted Random Number Partitioning Problem

    by Eren C. Kızıldağ

    We consider the random number partitioning problem (\texttt{NPP}): given a list $X\sim \mathcal{N}(0,I_n)$ of numbers, find a partition $σ\in\{-1,1\}^n$ with a small objective value $H(σ)=\frac{1}{\sqrt{n}}\left|\langle σ,X\rangle\right|$. The \texttt{NPP} is widely studied in computer science; it is also closely related to the design of randomized controlled trials. In this paper, we propose a planted version of the \texttt{NPP}: fix a $σ^*$ and generate $X\sim \mathcal{N}(0,I_n)$ conditional on $H(σ^*)\le 3^{-n}$. The \texttt{NPP} and its planted counterpart are statistically distinguishable as the smallest objective value under the former is $Θ(\sqrt{n}2^{-n})$ w.h.p. Our first focus is on the values of $H(σ)$. We show that, perhaps surprisingly, planting does not induce partitions with an objective value substantially smaller than $2^{-n}$: $\min_{σ\ne \pm σ^*}H(σ) = \widetildeΘ(2^{-n})$ w.h.p. Furthermore, we completely characterize the smallest $H(σ)$ achieved at any fixed distance from $σ^*$. Our second focus is on the algorithmic problem of efficiently finding a partition $σ$, not necessarily equal to $\pmσ^*$, with a small $H(σ)$. We show that planted \texttt{NPP} exhibits an intricate geometrical property known as the multi Overlap Gap Property ($m$-OGP) for values $2^{-Θ(n)}$. We then leverage the $m$-OGP to show that stable algorithms satisfying a certain anti-concentration property fail to find a $σ$ with $H(σ)=2^{-Θ(n)}$. Our results are the first instance of the $m$-OGP being established and leveraged to rule out stable algorithms for a planted model. More importantly, they show that the $m$-OGP framework can also apply to planted models, if the algorithmic goal is to return a solution with a small objective value.

  • Open Access

    Shattering in the Ising Pure $p$-Spin Model

    by David Gamarnik, Aukosh Jagannath, Eren C. Kızıldağ

    We study the Ising pure $p$-spin model for large $p$. We investigate the landscape of the Hamiltonian of this model. We show that for any $γ>0$ and any large enough $p$, the model exhibits an intricate geometrical property known as the multi Overlap Gap Property above the energy value $γ\sqrt{2\ln 2}$. We then show that for any inverse temperature $\sqrt{\ln 2}<β<\sqrt{2\ln 2}$ and any large $p$, the model exhibits shattering: w.h.p. as $n\to\infty$, there exists exponentially many well-separated clusters such that (a) each cluster has exponentially small Gibbs mass, and (b) the clusters collectively contain all but a vanishing fraction of Gibbs mass. Moreover, these clusters consist of configurations with energy near $β$. Range of temperatures for which shattering occurs is within the replica symmetric region. To the best of our knowledge, this is the first shattering result regarding the Ising $p$-spin models. Our proof is elementary, and in particular based on simple applications of the first and the second moment methods.


  • Open Access

    Geometric Barriers for Stable and Online Algorithms for Discrepancy Minimization

    by David Gamarnik, Eren C. Kızıldağ, Will Perkins, Changji Xu

    For many computational problems involving randomness, intricate geometric features of the solution space have been used to rigorously rule out powerful classes of algorithms. This is often accomplished through the lens of the multi Overlap Gap Property ($m$-OGP), a rigorous barrier against algorithms exhibiting input stability. In this paper, we focus on the algorithmic tractability of two models: (i) discrepancy minimization, and (ii) the symmetric binary perceptron (\texttt{SBP}), a random constraint satisfaction problem as well as a toy model of a single-layer neural network. Our first focus is on the limits of online algorithms. By establishing and leveraging a novel geometrical barrier, we obtain sharp hardness guarantees against online algorithms for both the \texttt{SBP} and discrepancy minimization. Our results match the best known algorithmic guarantees, up to constant factors. Our second focus is on efficiently finding a constant discrepancy solution, given a random matrix $\mathcal{M}\in\mathbb{R}^{M\times n}$. In a smooth setting, where the entries of $\mathcal{M}$ are i.i.d. standard normal, we establish the presence of $m$-OGP for $n=Θ(M\log M)$. Consequently, we rule out the class of stable algorithms at this value. These results give the first rigorous evidence towards a conjecture of Altschuler and Niles-Weed~\cite[Conjecture~1]{altschuler2021discrepancy}. Our methods use the intricate geometry of the solution space to prove tight hardness results for online algorithms. The barrier we establish is a novel variant of the $m$-OGP. Furthermore, it regards $m$-tuples of solutions with respect to correlated instances, with growing values of $m$, $m=ω(1)$. Importantly, our results rule out online algorithms succeeding even with an exponentially small probability.