Gamarnik, David
- Limits of local algorithms over sparse random graphs
2013/04/05 by Gamarnik, David, Sudan, Madhu · 17 citations
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #Distributed #FOS: Computer and information sciences #FOS: Mathematics #Parallel #Probability (math.PR) #and Cluster Computing (cs.DC)
- The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
2020/04/20 by Edward Farhi, Farhi, Edward, David Gamarnik +3 · 12 citations
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum Physics (quant-ph)
- The Overlap Gap Property and Approximate Message Passing Algorithms for\n p-spin models
2019/11/15 by David Gamarnik, Aukosh Jagannath, Gamarnik, David +1 · 7 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #FOS: Mathematics #FOS: Physical sciences #Markov Chains and Monte Carlo Methods #Mathematical Physics (math-ph) #Probability (math.PR) #Random Matrices and Applications #Statistical Mechanics (cond-mat.stat-mech)
- The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
2020/05/18 by Edward Farhi, Farhi, Edward, David Gamarnik +3 · 7 citations
Computer Science · #Complexity and Algorithms in Graphs #Optimization and Search Problems #Quantum Computing Algorithms and Architecture
- Algorithms and Barriers in the Symmetric Binary Perceptron Model
2022/03/29 by David Gamarnik, Gamarnik, David, Eren C. Kızıldağ +5 · 8 citations
Computer Science · #Rough Sets and Fuzzy Logic #Advanced Algebra and Logic #Neural Networks and Applications
- Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics
2020/04/25 by David Gamarnik, Gamarnik, David, Aukosh Jagannath +3 · 5 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Machine Learning (stat.ML) #Machine Learning and Algorithms #Markov Chains and Monte Carlo Methods #Mathematical Physics (math-ph) #Probability (math.PR)
- Join the Shortest Queue with Many Servers. The Heavy Traffic Asymptotics
2015/02/03 by Patrick Eschenfeldt, Eschenfeldt, Patrick, David Gamarnik +1 · 4 citations
Business, Management and Accounting · Decision Sciences · Engineering · #Advanced Queuing Theory Analysis #Probability and Risk Models #Advanced Wireless Network Optimization
- Finding a Large Submatrix of a Gaussian Random Matrix
2016/02/26 by David Gamarnik, Gamarnik, David, Quan Li +1 · 4 citations
Computer Science · Physics and Astronomy · #Complex Network Analysis Techniques #Data Analysis #Data Management and Algorithms #FOS: Mathematics #FOS: Physical sciences #Probability (math.PR) #Statistical Mechanics (cond-mat.stat-mech) #Statistics Theory (math.ST) #Statistics and Probability (physics.data-an) #Topological and Geometric Data Analysis
- Structure learning of antiferromagnetic Ising models
2014/12/03 by Guy Bresler, Bresler, Guy, David Gamarnik +3 · 3 citations
Computer Science · Mathematics · #Bayesian Modeling and Causal Inference #Machine Learning and Algorithms #Statistical Methods and Inference
- Maximum Weight Independent Sets and Matchings in Sparse Random Graphs. Exact Results using the Local Weak Convergence Method
2003/09/26 by David Gamarnik, Tomasz Nowicki, Gamarnik, David +3 · 2 citations
Mathematics · #05C80 #05C90 #60C05 #60J85 #82B26 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #math.CO #math.PR #msc:05C80 #msc:05C90 #msc:60C05 #msc:60J85 #msc:82B26
- Matrix Completion from O(n) Samples in Linear Time
2017/02/08 by David Gamarnik, Gamarnik, David, Quan Li +3 · 3 citations
Computer Science · Engineering · Medicine · #Data Structures and Algorithms (cs.DS) #Digital Image Processing Techniques #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Medical Imaging Techniques and Applications #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques
- Geometric Barriers for Stable and Online Algorithms for Discrepancy Minimization
2023/02/13 by David Gamarnik, Gamarnik, David, Eren C. Kızıldağ +5 · 5 citations
Computer Science · Engineering · Materials Science · #Advanced Numerical Analysis Techniques #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Digital Image Processing Techniques #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Machine Learning in Materials Science #Mathematical Physics (math-ph) #Probability (math.PR)
- Shattering in the Ising Pure p-Spin Model
2023/07/14 by David Gamarnik, Aukosh Jagannath, Gamarnik, David +3 · 5 citations
Mathematics · Physics and Astronomy · #FOS: Mathematics #FOS: Physical sciences #Markov Chains and Monte Carlo Methods #Mathematical Physics (math-ph) #Probability (math.PR) #Stochastic processes and statistical mechanics #Theoretical and Computational Physics
- The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property
2019/04/15 by Gamarnik, David, Zadik, Ilias · 2 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Probability (math.PR) #Statistics Theory (math.ST)
- High-Dimensional Regression with Binary Coefficients. Estimating Squared\n Error and a Phase Transition
2017/01/16 by David Gamarnik, Ilias Zadik, Gamarnik, David +1 · 2 citations
Mathematics · Computer Science · #Statistical Methods and Inference #Geochemistry and Geologic Mapping #Markov Chains and Monte Carlo Methods
- Hardness of sampling solutions from the Symmetric Binary Perceptron
2024/07/23 by A. El Alaoui, Alaoui, Ahmed El, David Gamarnik +1 · 5 citations
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Face and Expression Recognition #Neural Networks and Applications #Probability (math.PR)
- Algorithmic Obstructions in the Random Number Partitioning Problem
2021/03/02 by Gamarnik, David, Kızıldağ, Eren C. · 3 citations
#FOS: Mathematics #FOS: Physical sciences #Mathematical Physics (math-ph) #Probability (math.PR) #Statistics Theory (math.ST)
- Slow Mixing of Quantum Gibbs Samplers
2024/11/06 by David Gamarnik, Bobak T. Kiani, Gamarnik, David +3 · 6 citations
Physics and Astronomy · #Advanced Thermodynamics and Statistical Mechanics #Cold Atom Physics and Bose-Einstein Condensates #FOS: Mathematics #FOS: Physical sciences #Mathematical Physics (math-ph) #Probability (math.PR) #Quantum Physics (quant-ph) #Spectroscopy and Quantum Chemical Studies
- The diameter of a long range percolation graph
2001/12/04 by Don Coppersmith, David Gamarnik, Coppersmith, Don +3 · 1 citation
Mathematics · Physics and Astronomy · #60C05 #60K35 #82B26 #82B43 #Combinatorics (math.CO) #FOS: Mathematics #FOS: Physical sciences #Markov Chains and Monte Carlo Methods #Mathematical Physics (math-ph) #Probability (math.PR) #Random Matrices and Applications #Stochastic processes and statistical mechanics #math-ph #math.CO #math.MP #math.PR #msc:60C05 #msc:60K35 #msc:82B26 #msc:82B43
- Random MAX SAT, Random MAX CUT, and Their Phase Transitions
2003/06/02 by Don Coppersmith, David Gamarnik, Coppersmith, Don +5 · 1 citation
Computer Science · #05C80 #05C90 #60C05 #60J85 #82B26 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Constraint Satisfaction and Optimization #FOS: Mathematics #Probability (math.PR)
- A Deterministic Approximation Algorithm for Computing a Permanent of a 0,1 matrix
2007/02/02 by Gamarnik, David, Katz, Dmitriy · 1 citation
#05A16 #05C30 #68Q17 #68Q25 #Combinatorics (math.CO) #FOS: Mathematics
- Stationary Points of Shallow Neural Networks with Quadratic Activation\n Function
2019/12/03 by David Gamarnik, Gamarnik, David, Eren C. Kızıldağ +3 · 3 citations
Computer Science · Engineering · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and ELM #Neural Networks and Applications #Optimization and Control (math.OC) #Probability (math.PR) #Sparse and Compressive Sensing Techniques #Statistics Theory (math.ST) #Stochastic Gradient Optimization Techniques
- Maximally-stable Local Optima in Random Graphs and Spin Glasses: Phase Transitions and Universality
2023/05/05 by Yatin Dandi, Dandi, Yatin, David Gamarnik +3 · 2 citations
Mathematics · Physics and Astronomy · #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #FOS: Physical sciences #Markov Chains and Monte Carlo Methods #Mathematical Physics (math-ph) #Probability (math.PR) #Theoretical and Computational Physics
- Learning graphical models from the Glauber dynamics
2014/10/28 by Bresler, Guy, Gamarnik, David, Shah, Devavrat · 1 citation
#Computation (stat.CO) #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML)
- Explicit construction of RIP matrices is Ramsey-hard
2018/05/29 by Gamarnik, David · 1 citation
#Computation (stat.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Probability (math.PR)
- Bounds on the ground state energy of quantum p-spin Hamiltonians
2024/04/03 by Eric R. Anschuetz, David Gamarnik, Anschuetz, Eric R. +3 · 2 citations
Physics and Astronomy · Computer Science · Mathematics · #Theoretical and Computational Physics #Topological and Geometric Data Analysis #Markov Chains and Monte Carlo Methods
- Correlation Decay and the Absence of Zeros Property of Partition Functions
2020/11/10 by David Gamarnik, Gamarnik, David · 1 citation
Mathematics · #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Mathematical Dynamics and Fractals #Probability (math.PR) #Stochastic processes and statistical mechanics
- Circuit Lower Bounds for the p-Spin Optimization Problem
2021/09/03 by David Gamarnik, Gamarnik, David, Aukosh Jagannath +3 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning and Algorithms #Probability (math.PR)
- Optimal Hardness of Online Algorithms for Large Independent Sets
2025/04/15 by David Gamarnik, Gamarnik, David, Eren C. Kızıldağ +3 · 5 citations
Computer Science · #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Search Problems #Probability (math.PR)
- Decoded Quantum Interferometry Requires Structure
2025/09/18 by Anschuetz, Eric R., Gamarnik, David, Lu, Jonathan Z. · 3 citations
#Data Structures and Algorithms (cs.DS) #Disordered Systems and Neural Networks (cond-mat.dis-nn) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph) #Statistical Mechanics (cond-mat.stat-mech)
- Neural Networks and Polynomial Regression. Demystifying the Overparametrization Phenomena
2020/03/23 by Matt Emschwiller, Emschwiller, Matt, David Gamarnik +5 · 2 citations
Mathematics · Computer Science · #Tensor decomposition and applications #Machine Learning and Data Classification #Stochastic Gradient Optimization Techniques
- Sequential Dynamics in Ising Spin Glasses
2025/06/11 by Yatin Dandi, Dandi, Yatin, David Gamarnik +5 · 4 citations
Computer Science · Physics and Astronomy · #Disordered Systems and Neural Networks (cond-mat.dis-nn) #FOS: Mathematics #FOS: Physical sciences #Mathematical Physics (math-ph) #Probability (math.PR) #Quantum Computing Algorithms and Architecture #Quantum many-body systems #Theoretical and Computational Physics
- Cliques, Chromatic Number, and Independent Sets in the Semi-random Process
2023/03/23 by David Gamarnik, Gamarnik, David, Mihyun Kang +3 · 1 citation
Decision Sciences · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Applications #Limits and Structures in Graph Theory #Probability (math.PR) #Stochastic processes and statistical mechanics