8 citations · 17 across the 9 of their papers we have counts for
11 papers
Stable and Online Algorithms for Random Matrix Discrepancy
Eren C. Kızıldağ, Shuangping Li
We study the average-case matrix discrepancy problem: given independent normalized Gaussian orthogonal ensemble matrices and a fixed margin , find…
Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs
Abhishek Dhawan, Nhi U. Dinh, Eren C. Kızıldağ +2
We study the algorithmic tractability of finding large independent sets in dense random hypergraphs. In the sparse regime, much of the natural algorithms can be formulated within e…
Sharp Online Hardness for Large Balanced Independent Sets
Abhishek Dhawan, Eren C. Kızıldağ, Neeladri Maitra
We study the algorithmic problem of finding large -balanced independent sets in dense random bipartite graphs; an independent set is -balanced if a proportion of its vert…
Optimal Hardness of Online Algorithms for Large Independent Sets
David Gamarnik, Eren C. Kızıldağ, Lutz Warnke
We study the algorithmic problem of finding a large independent set in the Erd{ö}s-Rényi random graph . For constant and , the largest independent set has si…
Information-Theoretic Guarantees for Recovering Low-Rank Tensors from Symmetric Rank-One Measurements
Eren C. Kızıldağ
In this paper, we investigate the sample complexity of recovering tensors with low symmetric rank from symmetric rank-one measurements. This setting is particularly motivated by th…
Planted Random Number Partitioning Problem
Eren C. Kızıldağ
We consider the random number partitioning problem (\texttt{NPP}): given a list of numbers, find a partition with a small objective valu…
Sharp Thresholds for the Overlap Gap Property: Ising -Spin Glass and Random -SAT
Eren C. Kızıldağ
The Ising -spin glass and random -SAT are two canonical examples of disordered systems that play a central role in understanding the link between geometric features of optimi…
Geometric Barriers for Stable and Online Algorithms for Discrepancy Minimization
David Gamarnik, Eren C. Kızıldağ, Will Perkins +1
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…
Algorithms and Barriers in the Symmetric Binary Perceptron Model
David Gamarnik, Eren C. Kızıldağ, Will Perkins +1
The symmetric binary perceptron () exhibits a dramatic statistical-to-computational gap: the densities at which known efficient algorithms find solutions are far belo…
Neural Networks and Polynomial Regression. Demystifying the Overparametrization Phenomena
Matt Emschwiller, David Gamarnik, Eren C. Kızıldağ +1
In the context of neural network models, overparametrization refers to the phenomena whereby these models appear to generalize well on the unseen data, even though the number of pa…
Stationary Points of Shallow Neural Networks with Quadratic Activation Function
David Gamarnik, Eren C. Kızıldağ, Ilias Zadik
We consider the teacher-student setting of learning shallow neural networks with quadratic activations and planted weight matrix , where is the wi…