Andrea Montanari

According to our database1, Andrea Montanari authored at least 171 papers between 2001 and 2020.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Awards

IEEE Fellow

IEEE Fellow 2018, "For applications of statistical physics to coding theory".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

On csauthors.net:

Bibliography

2020
Underspecification Presents Challenges for Credibility in Modern Machine Learning.
CoRR, 2020

The Lasso with general Gaussian designs with applications to hypothesis testing.
CoRR, 2020

The Interpolation Phase Transition in Neural Networks: Memorization and Generalization under Lazy Training.
CoRR, 2020

When Do Neural Networks Outperform Kernel Methods?
CoRR, 2020

The estimation error of general first order methods.
Proceedings of the Conference on Learning Theory, 2020

2019
Fundamental Limits of Weak Recovery with Applications to Phase Retrieval.
Found. Comput. Math., 2019

Limitations of Lazy Training of Two-layers Neural Networks.
CoRR, 2019

Linearized two-layers neural networks in high dimension.
CoRR, 2019

On the computational tractability of statistical estimation on amenable graphs.
CoRR, 2019

Surprises in High-Dimensional Ridgeless Least Squares Interpolation.
CoRR, 2019

Analysis of a Two-Layer Neural Network via Displacement Convexity.
CoRR, 2019

The threshold for SDP-refutation of random regular NAE-3SAT.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Limitations of Lazy Training of Two-layers Neural Network.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

An Instability in Variational Inference for Topic Models.
Proceedings of the 36th International Conference on Machine Learning, 2019

Optimization of the Sherrington-Kirkpatrick Hamiltonian.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit.
Proceedings of the Conference on Learning Theory, 2019

On the Connection Between Learning Two-Layer Neural Networks and Tensor Decomposition.
Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2019

2018
A Statistical Model for Motifs Detection.
IEEE Trans. Inf. Theory, 2018

Generating Random Networks Without Short Cycles.
Oper. Res., 2018

Adapting to Unknown Noise Distribution in Matrix Denoising.
CoRR, 2018

A Mean Field View of the Landscape of Two-Layers Neural Networks.
CoRR, 2018

On the Connection Between Learning Two-Layers Neural Networks and Tensor Decomposition.
CoRR, 2018

Contextual Stochastic Block Models.
Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

2017
On the Limitation of Spectral Methods: From the Gaussian Hidden Clique Problem to Rank One Perturbations of Gaussian Tensors.
IEEE Trans. Inf. Theory, 2017

Learning Combinations of Sigmoids Through Gradient Estimation.
CoRR, 2017

State Evolution for Approximate Message Passing with Non-Separable Functions.
CoRR, 2017

Non-negative Matrix Factorization via Archetypal Analysis.
CoRR, 2017

Group Synchronization on Grids.
CoRR, 2017

How well do local algorithms solve semidefinite programs?
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Inference in Graphical Models via Semidefinite Programming Hierarchies.
Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Universality of the elastic net error.
Proceedings of the 2017 IEEE International Symposium on Information Theory, 2017

Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality.
Proceedings of the 30th Conference on Learning Theory, 2017

2016
Non-Negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics.
IEEE Trans. Inf. Theory, 2016

Sparse PCA via Covariance Thresholding.
J. Mach. Learn. Res., 2016

Effective compression maps for torus-based cryptography.
Des. Codes Cryptogr., 2016

Spectral algorithms for tensor completion.
CoRR, 2016

Performance of a community detection algorithm based on semidefinite programming.
CoRR, 2016

Online Rules for Control of False Discovery Rate and False Discovery Exceedance.
CoRR, 2016

Semidefinite programs on sparse random graphs and their application to community detection.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Asymptotic mutual information for the binary stochastic block model.
Proceedings of the IEEE International Symposium on Information Theory, 2016

2015
Conditional Random Fields, Planted Constraint Satisfaction, and Entropy Concentration.
Theory Comput., 2015

Bargaining dynamics in exchange networks.
J. Econ. Theory, 2015

Finding Hidden Cliques of Size √(N/e) in Nearly Linear Time.
Found. Comput. Math., 2015

Semidefinite Programs on Sparse Random Graphs.
CoRR, 2015

Finding One Community in a Sparse Graph.
CoRR, 2015

Phase Transitions in Semidefinite Relaxations.
CoRR, 2015

On Online Control of False Discovery Rate.
CoRR, 2015

The Hidden Subgraph Problem.
CoRR, 2015

Asymptotic Mutual Information for the Two-Groups Stochastic Block Model.
CoRR, 2015

Extremal Cuts of Sparse Random Graphs.
CoRR, 2015

A Perspective on Future Research Directions in Information Theory.
CoRR, 2015

Convergence rates of sub-sampled Newton methods.
Proceedings of the Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, 2015

Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems.
Proceedings of The 28th Conference on Learning Theory, 2015

A Low-Cost Method for Multiple Disease Prediction.
Proceedings of the AMIA 2015, 2015

Privacy-Utility Trade-Off for Time-Series with Application to Smart-Meter Data.
Proceedings of the Computational Sustainability, 2015

2014
Accelerated Time-of-Flight Mass Spectrometry.
IEEE Trans. Signal Process., 2014

Hypothesis Testing in High-Dimensional Regression Under the Gaussian Random Design Model: Asymptotic Theory.
IEEE Trans. Inf. Theory, 2014

On the concentration of the number of solutions of random satisfiability formulas.
Random Struct. Algorithms, 2014

Confidence intervals and hypothesis testing for high-dimensional regression.
J. Mach. Learn. Res., 2014

Statistical Estimation: From Denoising to Sparse Regression and Hidden Cliques.
CoRR, 2014

Computational Implications of Reducing Data to Sufficient Statistics.
CoRR, 2014

Privacy tradeoffs in predictive analytics.
Proceedings of the ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, 2014

A statistical model for tensor PCA.
Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014

Cone-Constrained Principal Component Analysis.
Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014

Information-theoretically optimal sparse PCA.
Proceedings of the 2014 IEEE International Symposium on Information Theory, Honolulu, HI, USA, June 29, 2014

Learning Mixtures of Linear Classifiers.
Proceedings of the 31th International Conference on Machine Learning, 2014

2013
Iterative Coding for Network Coding.
IEEE Trans. Inf. Theory, 2013

Optimal Coding for the Binary Deletion Channel With Small Deletion Probability.
IEEE Trans. Inf. Theory, 2013

Information-Theoretically Optimal Compressed Sensing via Spatial Coupling and Approximate Message Passing.
IEEE Trans. Inf. Theory, 2013

Accurate Prediction of Phase Transitions in Compressed Sensing via a Connection to Minimax Denoising.
IEEE Trans. Inf. Theory, 2013

Localization from Incomplete Noisy Distance Measurements.
Found. Comput. Math., 2013

Conditional Random Fields, Planted Satisfaction, and Entropy Concentration
CoRR, 2013

Finding Hidden Cliques of Size \sqrt{N/e} in Nearly Linear Time
CoRR, 2013

The Phase Transition of Matrix Recovery from Gaussian Measurements Matches the Minimax MSE of Matrix Denoising
CoRR, 2013

High Dimensional Robust M-Estimation: Asymptotic Variance via Approximate Message Passing.
CoRR, 2013

Model Selection for High-Dimensional Regression under the Generalized Irrepresentability Condition.
Proceedings of the Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013

Confidence Intervals and Hypothesis Testing for High-Dimensional Statistical Models.
Proceedings of the Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013

Estimating LASSO Risk and Noise Level.
Proceedings of the Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013

Nearly optimal sample size in hypothesis testing for high-dimensional regression.
Proceedings of the 51st Annual Allerton Conference on Communication, 2013

The mutual information of a class of graphical channels.
Proceedings of the 51st Annual Allerton Conference on Communication, 2013

2012
Lossy Compression of Discrete Sources via the Viterbi Algorithm.
IEEE Trans. Inf. Theory, 2012

The LASSO Risk for Gaussian Matrices.
IEEE Trans. Inf. Theory, 2012

State Evolution for General Approximate Message Passing Algorithms, with Applications to Spatial Coupling
CoRR, 2012

Universality in Polytope Phase Transitions and Message Passing Algorithms
CoRR, 2012

Identifying Users From Their Rating Patterns
CoRR, 2012

Guess Who Rated This Movie: Identifying Users Through Subspace Clustering.
Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence, 2012

The set of solutions of random XORSAT formulae.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Subsampling at information theoretically optimal rates.
Proceedings of the 2012 IEEE International Symposium on Information Theory, 2012

Universality in polytope phase transitions and iterative algorithms.
Proceedings of the 2012 IEEE International Symposium on Information Theory, 2012

Linear bandits in high dimension and recommendation systems.
Proceedings of the 50th Annual Allerton Conference on Communication, 2012

Graphical models concepts in compressed sensing.
Proceedings of the Compressed Sensing, 2012

2011
Applications of the Lindeberg Principle in Communications and Statistical Learning.
IEEE Trans. Inf. Theory, 2011

The Noise-Sensitivity Phase Transition in Compressed Sensing.
IEEE Trans. Inf. Theory, 2011

The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing.
IEEE Trans. Inf. Theory, 2011

Reconstruction and Clustering in Random Constraint Satisfaction Problems.
SIAM J. Discret. Math., 2011

Factor models on locally tree-like graphs
CoRR, 2011

On the trade-off between complexity and correlation decay in structural learning algorithms
CoRR, 2011

Optimal coding for the deletion channel with small deletion probability
CoRR, 2011

Compressed Sensing over ℓ<sub>p</sub>-balls: Minimax Mean Square Error
CoRR, 2011

Fast Convergence of Natural Bargaining Dynamics in Exchange Networks.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Gossip PCA.
Proceedings of the SIGMETRICS 2011, 2011

Compressed Sensing over ℓ<sup>p</sup>-balls: Minimax mean square error.
Proceedings of the 2011 IEEE International Symposium on Information Theory Proceedings, 2011

Information theoretic limits on learning stochastic differential equations.
Proceedings of the 2011 IEEE International Symposium on Information Theory Proceedings, 2011

Subexponential convergence for information aggregation on regular trees.
Proceedings of the 50th IEEE Conference on Decision and Control and European Control Conference, 2011

Distributed storage for intermittent energy sources: Control design and performance limits.
Proceedings of the 49th Annual Allerton Conference on Communication, 2011

Robust max-product belief propagation.
Proceedings of the Conference Record of the Forty Fifth Asilomar Conference on Signals, 2011

2010
Matrix completion from a few entries.
IEEE Trans. Inf. Theory, 2010

The spread of innovations in social networks.
Proc. Natl. Acad. Sci. USA, 2010

Matrix Completion from Noisy Entries.
J. Mach. Learn. Res., 2010

Graphical Models Concepts in Compressed Sensing
CoRR, 2010

Message passing algorithms: a success looking for theoreticians.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Learning Networks of Stochastic Differential Equations.
Proceedings of the Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010. Proceedings of a meeting held 6-9 December 2010, 2010

The LASSO risk: asymptotic results and real world examples.
Proceedings of the Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010. Proceedings of a meeting held 6-9 December 2010, 2010

An empirical scaling law for polar codes.
Proceedings of the IEEE International Symposium on Information Theory, 2010

Regularization for matrix completion.
Proceedings of the IEEE International Symposium on Information Theory, 2010

On the deletion channel with small deletion probability.
Proceedings of the IEEE International Symposium on Information Theory, 2010

Tight Thresholds for Cuckoo Hashing via XORSAT.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Statistical static timing analysis using Markov chain Monte Carlo.
Proceedings of the Design, Automation and Test in Europe, 2010

Analysis of approximate message passing algorithm.
Proceedings of the 44th Annual Conference on Information Sciences and Systems, 2010

2009
The generalized area theorem and some of its consequences.
IEEE Trans. Inf. Theory, 2009

Finite-Length Scaling for Iteratively Decoded LDPC Ensembles.
IEEE Trans. Inf. Theory, 2009

Convergence to equilibrium in local interaction games.
SIGecom Exch., 2009

Message Passing Algorithms for Compressed Sensing: II. Analysis and Validation
CoRR, 2009

Message Passing Algorithms for Compressed Sensing: I. Motivation and Construction
CoRR, 2009

A Natural Dynamics for Bargaining on Exchange Networks
CoRR, 2009

Low-rank Matrix Completion with Noisy Observations: a Quantitative Comparison
CoRR, 2009

Message Passing Algorithms for Compressed Sensing
CoRR, 2009

Which graphical models are difficult to learn?
CoRR, 2009

Generating random graphs with large girth.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Which graphical models are difficult to learn?
Proceedings of the Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009. Proceedings of a meeting held 7-10 December 2009, 2009

An iterative scheme for near optimal and universal lossy compression.
Proceedings of the 2009 IEEE Information Theory Workshop, 2009

An Implementable Scheme for Universal Lossy Compression of Discrete Markov Sources.
Proceedings of the 2009 Data Compression Conference (DCC 2009), 2009

2008
Maxwell Construction: The Hidden Bridge Between Iterative and Maximum a Posteriori Decoding.
IEEE Trans. Inf. Theory, 2008

Estimating random variables from random sparse observations.
Eur. Trans. Telecommun., 2008

Learning Low Rank Matrices from O(n) Entries
CoRR, 2008

Convergence to Equilibrium in Local Interaction Games and Ising Models
CoRR, 2008

Clusters of solutions and replica symmetry breaking in random k-satisfiability
CoRR, 2008

Counter braids: a novel counter architecture for per-flow measurement.
Proceedings of the 2008 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, 2008

Counter Braids.
Proceedings of the 2008 IEEE Information Theory Workshop, 2008

Smooth compression, Gallager bound and nonlinear sparse-graph codes.
Proceedings of the 2008 IEEE International Symposium on Information Theory, 2008

Computing the threshold shift for general channels.
Proceedings of the 2008 IEEE International Symposium on Information Theory, 2008

The slope scaling parameter for general channels, decoders, and ensembles.
Proceedings of the 2008 IEEE International Symposium on Information Theory, 2008

2007
Gibbs states and the set of solutions of random constraint satisfaction problems.
Proc. Natl. Acad. Sci. USA, 2007

How to find good finite-length codes: from art towards science.
Eur. Trans. Telecommun., 2007

Coding for Network Coding
CoRR, 2007

Detailed Network Measurements Using Sparse Graph Counters: The Theory
CoRR, 2007

TP Decoding
CoRR, 2007

Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation
CoRR, 2007

Modern Coding Theory: The Statistical Mechanics and Computer Science Point of View
CoRR, 2007

Counting good truth assignments of random <i>k</i>-SAT formulae.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Asymptotic Rate versus Design Rate.
Proceedings of the IEEE International Symposium on Information Theory, 2007

A Generalization of the Finite-Length Scaling Approach Beyond the BEC.
Proceedings of the IEEE International Symposium on Information Theory, 2007

Reconstruction for Models on Random Graphs.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

2006
Counting good truth assignments of random k-SAT formulae
CoRR, 2006

Analysis of Belief Propagation for Non-Linear Problems: The Example of CDMA (or: How to Prove Tanaka's Formula).
Proceedings of the 2006 IEEE Information Theory Workshop, 2006

Analytic Determination of Scaling Parameters.
Proceedings of the Proceedings 2006 IEEE International Symposium on Information Theory, 2006

Analyzing Search Algorithms with Physical Methods.
Proceedings of the Computational Complexity and Statistical Physics., 2006

2005
Tight Bounds for LDPC and LDGM Codes Under MAP Decoding.
IEEE Trans. Inf. Theory, 2005

Why We Can Not Surpass Capacity: The Matching Condition
CoRR, 2005

Belief Propagation Based Multi--User Detection
CoRR, 2005

Finite-length scaling of irregular LDPC code ensembles.
Proceedings of the IEEE ITSOC Information Theory Workshop 2005 on Coding and Complexity, 2005

Maximum a posteriori decoding and turbo codes for general memoryless channels.
Proceedings of the 2005 IEEE International Symposium on Information Theory, 2005

2004
Life Above Threshold: From List Decoding to Area Theorem and MSE
CoRR, 2004

Finite-Length Scaling and Finite-Length Shift for Low-Density Parity-Check Codes
CoRR, 2004

Tight bounds for LDPC codes under MAP decoding.
Proceedings of the 2004 IEEE International Symposium on Information Theory, 2004

Maxwell's construction: the hidden bridge between maximum-likelihood and iterative decoding.
Proceedings of the 2004 IEEE International Symposium on Information Theory, 2004

Weight distributions of LDPC code ensembles: combinatorics meets statistical physics.
Proceedings of the 2004 IEEE International Symposium on Information Theory, 2004

Further results on finite-length scaling for iteratively decoded LDPC ensembles.
Proceedings of the 2004 IEEE International Symposium on Information Theory, 2004

2003
Approximate analysis of search algorithms with "physical" methods
CoRR, 2003

Instability of one-step replica-symmetry-broken phase in satisfiability problems
CoRR, 2003

2001
Boosting search by rare events
CoRR, 2001


  Loading...