default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDAndrea Montanari
Person information
- affiliation: Stanford University, CA, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[j41]Andrea Montanari, Subhabrata Sen:
A Friendly Tutorial on Mean-Field Spin Glass Techniques for Non-Physicists. Found. Trends Mach. Learn. 17(1): 1-173 (2024)- [c94]Germain Kolossov, Andrea Montanari, Pulkit Tandon:
Towards a statistical theory of data selection under weak supervision. ICLR 2024 - [c93]Andrea Montanari, Alexandra Marele, Francesco Franco, Francesco Poggi, Luca Bedogni:
Wearable Device Positioning for Activity Recognition and Monitoring. ISCC 2024: 1-6 - [c92]Katherine L. Mentzer
, Andrea Montanari:
Scaling Training Data with Lossy Image Compression. KDD 2024: 2212-2223 - [i139]Ayush Jain, Andrea Montanari, Eren Sasoglu:
Scaling laws for learning with real and surrogate data. CoRR abs/2402.04376 (2024) - [i138]Andrea Montanari, Eliran Subag:
On Smale's 17th problem over the reals. CoRR abs/2405.01735 (2024) - [i137]Andrea Montanari, Kangjie Zhou:
Which exceptional low-dimensional projections of a Gaussian point cloud can be found in polynomial time? CoRR abs/2406.02970 (2024) - [i136]Katherine L. Mentzer, Andrea Montanari:
Scaling Training Data with Lossy Image Compression. CoRR abs/2407.17954 (2024) - [i135]Kabir Aladin Verchand, Andrea Montanari:
High-dimensional logistic regression with missing data: Imputation, regularization, and universality. CoRR abs/2410.01093 (2024) - 2023
- [j40]Ahmed El Alaoui, Andrea Montanari, Mark Sellke:
Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree. Random Struct. Algorithms 63(3): 689-715 (2023) - [c91]Andrea Montanari, Eric Weiner:
Compressing Tabular Data via Latent Variable Estimation. ICML 2023: 25174-25208 - [i134]Andrea Montanari, Eric Weiner:
Compressing Tabular Data via Latent Variable Estimation. CoRR abs/2302.09780 (2023) - [i133]Raphaël Berthier, Andrea Montanari, Kangjie Zhou:
Learning time-scales in two-layers neural networks. CoRR abs/2303.00055 (2023) - [i132]Andrea Montanari:
Sampling, Diffusions, and Stochastic Localization. CoRR abs/2305.10690 (2023) - [i131]Theodor Misiakiewicz, Andrea Montanari:
Six Lectures on Linearized Neural Networks. CoRR abs/2308.13431 (2023) - [i130]Germain Kolossov, Andrea Montanari, Pulkit Tandon:
Towards a statistical theory of data selection under weak supervision. CoRR abs/2309.14563 (2023) - 2022
- [j39]Alexander D'Amour, Katherine A. Heller, Dan Moldovan, Ben Adlam, Babak Alipanahi, Alex Beutel, Christina Chen, Jonathan Deaton, Jacob Eisenstein, Matthew D. Hoffman, Farhad Hormozdiari, Neil Houlsby, Shaobo Hou, Ghassen Jerfel, Alan Karthikesalingam, Mario Lucic, Yi-An Ma, Cory Y. McLean, Diana Mincu, Akinori Mitani, Andrea Montanari, Zachary Nado, Vivek Natarajan, Christopher Nielson, Thomas F. Osborne, Rajiv Raman, Kim Ramasamy, Rory Sayres, Jessica Schrouff, Martin Seneviratne, Shannon Sequeira, Harini Suresh, Victor Veitch, Max Vladymyrov, Xuezhi Wang, Kellie Webster, Steve Yadlowsky, Taedong Yun, Xiaohua Zhai, D. Sculley:
Underspecification Presents Challenges for Credibility in Modern Machine Learning. J. Mach. Learn. Res. 23: 226:1-226:61 (2022) - [j38]Ahmed El Alaoui, Andrea Montanari:
An Information-Theoretic View of Stochastic Localization. IEEE Trans. Inf. Theory 68(11): 7423-7426 (2022) - [c90]Andrea Montanari, Basil Saeed:
Universality of empirical risk minimization. COLT 2022: 4310-4312 - [c89]Kangjie Zhou, Andrea Montanari:
High-Dimensional Projection Pursuit: Outer Bounds and Applications to Interpolation in Neural Networks. COLT 2022: 5525-5527 - [c88]Ahmed El Alaoui, Andrea Montanari, Mark Sellke:
Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization. FOCS 2022: 323-334 - [i129]Andrea Montanari, Basil Saeed:
Universality of empirical risk minimization. CoRR abs/2202.08832 (2022) - [i128]Ahmed El Alaoui, Andrea Montanari, Mark Sellke:
Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization. CoRR abs/2203.05093 (2022) - [i127]Andrea Montanari, Yuchen Wu:
Adversarial Examples in Random Neural Networks with General Activations. CoRR abs/2203.17209 (2022) - [i126]Andrea Montanari, Kangjie Zhou:
Overparametrized linear dimensionality reductions: From projection pursuit to two-layer neural networks. CoRR abs/2206.06526 (2022) - 2021
- [j37]Peter L. Bartlett, Andrea Montanari, Alexander Rakhlin:
Deep learning: a statistical viewpoint. Acta Numer. 30: 87-201 (2021) - [c87]Song Mei, Theodor Misiakiewicz, Andrea Montanari:
Learning with invariances in random features and kernel models. COLT 2021: 3351-3418 - [c86]Yuchen Wu, Jakab Tardos, MohammadHossein Bateni, André Linhares, Filipe Miguel Gonçalves de Almeida, Andrea Montanari, Ashkan Norouzi-Fard:
Streaming Belief Propagation for Community Detection. NeurIPS 2021: 26976-26988 - [i125]Song Mei, Theodor Misiakiewicz, Andrea Montanari:
Learning with invariances in random features and kernel models. CoRR abs/2102.13219 (2021) - [i124]Peter L. Bartlett, Andrea Montanari, Alexander Rakhlin:
Deep learning: a statistical viewpoint. CoRR abs/2103.09177 (2021) - [i123]Michael Celentano, Theodor Misiakiewicz, Andrea Montanari:
Minimum complexity interpolation in random features models. CoRR abs/2103.15996 (2021) - [i122]Yuchen Wu, MohammadHossein Bateni, André Linhares, Filipe Miguel Gonçalves de Almeida, Andrea Montanari, Ashkan Norouzi-Fard, Jakab Tardos:
Streaming Belief Propagation for Community Detection. CoRR abs/2106.04805 (2021) - [i121]Ahmed El Alaoui, Andrea Montanari:
An Information-Theoretic View of Stochastic Localization. CoRR abs/2109.00709 (2021) - [i120]Andrea Montanari, Yiqiao Zhong, Kangjie Zhou:
Tractability from overparametrization: The example of the negative perceptron. CoRR abs/2110.15824 (2021) - [i119]Ahmed El Alaoui, Andrea Montanari, Mark Sellke:
Local algorithms for Maximum Cut and Minimum Bisection on locally treelike regular graphs of large degree. CoRR abs/2111.06813 (2021) - 2020
- [c85]Michael Celentano, Andrea Montanari, Yuchen Wu:
The estimation error of general first order methods. COLT 2020: 1078-1141 - [c84]Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, Andrea Montanari:
When Do Neural Networks Outperform Kernel Methods? NeurIPS 2020 - [i118]Michael Celentano, Andrea Montanari, Yuchen Wu:
The estimation error of general first order methods. CoRR abs/2002.12903 (2020) - [i117]Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, Andrea Montanari:
When Do Neural Networks Outperform Kernel Methods? CoRR abs/2006.13409 (2020) - [i116]Andrea Montanari, Yiqiao Zhong:
The Interpolation Phase Transition in Neural Networks: Memorization and Generalization under Lazy Training. CoRR abs/2007.12826 (2020) - [i115]Michael Celentano, Andrea Montanari, Yuting Wei:
The Lasso with general Gaussian designs with applications to hypothesis testing. CoRR abs/2007.13716 (2020) - [i114]Alexander D'Amour, Katherine A. Heller, Dan Moldovan, Ben Adlam, Babak Alipanahi, Alex Beutel, Christina Chen, Jonathan Deaton, Jacob Eisenstein, Matthew D. Hoffman, Farhad Hormozdiari, Neil Houlsby, Shaobo Hou, Ghassen Jerfel, Alan Karthikesalingam, Mario Lucic, Yi-An Ma, Cory Y. McLean, Diana Mincu, Akinori Mitani, Andrea Montanari, Zachary Nado, Vivek Natarajan, Christopher Nielson, Thomas F. Osborne, Rajiv Raman, Kim Ramasamy, Rory Sayres, Jessica Schrouff, Martin Seneviratne, Shannon Sequeira, Harini Suresh, Victor Veitch, Max Vladymyrov, Xuezhi Wang, Kellie Webster, Steve Yadlowsky, Taedong Yun, Xiaohua Zhai, D. Sculley:
Underspecification Presents Challenges for Credibility in Modern Machine Learning. CoRR abs/2011.03395 (2020)
2010 – 2019
- 2019
- [j36]Marco Mondelli, Andrea Montanari:
Fundamental Limits of Weak Recovery with Applications to Phase Retrieval. Found. Comput. Math. 19(3): 703-773 (2019) - [c83]Marco Mondelli, Andrea Montanari:
On the Connection Between Learning Two-Layer Neural Networks and Tensor Decomposition. AISTATS 2019: 1051-1060 - [c82]Song Mei, Theodor Misiakiewicz, Andrea Montanari:
Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit. COLT 2019: 2388-2464 - [c81]Andrea Montanari:
Optimization of the Sherrington-Kirkpatrick Hamiltonian. FOCS 2019: 1417-1433 - [c80]Behrooz Ghorbani, Hamid Javadi, Andrea Montanari:
An Instability in Variational Inference for Topic Models. ICML 2019: 2221-2231 - [c79]Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, Andrea Montanari:
Limitations of Lazy Training of Two-layers Neural Network. NeurIPS 2019: 9108-9118 - [c78]Yash Deshpande, Andrea Montanari, Ryan O'Donnell, Tselil Schramm, Subhabrata Sen:
The threshold for SDP-refutation of random regular NAE-3SAT. SODA 2019: 2305-2321 - [i113]Adel Javanmard, Marco Mondelli, Andrea Montanari:
Analysis of a Two-Layer Neural Network via Displacement Convexity. CoRR abs/1901.01375 (2019) - [i112]Song Mei, Theodor Misiakiewicz, Andrea Montanari:
Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit. CoRR abs/1902.06015 (2019) - [i111]Trevor Hastie, Andrea Montanari, Saharon Rosset, Ryan J. Tibshirani:
Surprises in High-Dimensional Ridgeless Least Squares Interpolation. CoRR abs/1903.08560 (2019) - [i110]Ahmed El Alaoui, Andrea Montanari:
On the computational tractability of statistical estimation on amenable graphs. CoRR abs/1904.03313 (2019) - [i109]Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, Andrea Montanari:
Linearized two-layers neural networks in high dimension. CoRR abs/1904.12191 (2019) - [i108]Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, Andrea Montanari:
Limitations of Lazy Training of Two-layers Neural Networks. CoRR abs/1906.08899 (2019) - 2018
- [j35]Mohsen Bayati, Andrea Montanari, Amin Saberi:
Generating Random Networks Without Short Cycles. Oper. Res. 66(5): 1227-1246 (2018) - [j34]Hamid Javadi, Andrea Montanari:
A Statistical Model for Motifs Detection. IEEE Trans. Inf. Theory 64(12): 7594-7612 (2018) - [c77]Marco Mondelli, Andrea Montanari:
Fundamental Limits of Weak Recovery with Applications to Phase Retrieval. COLT 2018: 1445-1450 - [c76]Yash Deshpande, Subhabrata Sen, Andrea Montanari, Elchanan Mossel:
Contextual Stochastic Block Models. NeurIPS 2018: 8590-8602 - [i107]Marco Mondelli, Andrea Montanari:
On the Connection Between Learning Two-Layers Neural Networks and Tensor Decomposition. CoRR abs/1802.07301 (2018) - [i106]Yash Deshpande, Andrea Montanari, Ryan O'Donnell, Tselil Schramm, Subhabrata Sen:
The threshold for SDP-refutation of random regular NAE-3SAT. CoRR abs/1804.05230 (2018) - [i105]Song Mei, Andrea Montanari, Phan-Minh Nguyen:
A Mean Field View of the Landscape of Two-Layers Neural Networks. CoRR abs/1804.06561 (2018) - [i104]Yash Deshpande, Andrea Montanari, Elchanan Mossel, Subhabrata Sen:
Contextual Stochastic Block Models. CoRR abs/1807.09596 (2018) - [i103]Andrea Montanari, Feng Ruan, Jun Yan:
Adapting to Unknown Noise Distribution in Matrix Denoising. CoRR abs/1810.02954 (2018) - 2017
- [j33]Andrea Montanari, Daniel Reichman, Ofer Zeitouni:
On the Limitation of Spectral Methods: From the Gaussian Hidden Clique Problem to Rank One Perturbations of Gaussian Tensors. IEEE Trans. Inf. Theory 63(3): 1572-1579 (2017) - [c75]Song Mei, Theodor Misiakiewicz, Andrea Montanari, Roberto Imbuzeiro Oliveira:
Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality. COLT 2017: 1476-1515 - [c74]Andrea Montanari, Phan-Minh Nguyen:
Universality of the elastic net error. ISIT 2017: 2338-2342 - [c73]Murat A. Erdogdu, Yash Deshpande, Andrea Montanari:
Inference in Graphical Models via Semidefinite Programming Hierarchies. NIPS 2017: 417-425 - [c72]Zhou Fan, Andrea Montanari:
How well do local algorithms solve semidefinite programs? STOC 2017: 604-614 - [i102]Hamid Javadi, Andrea Montanari:
Non-negative Matrix Factorization via Archetypal Analysis. CoRR abs/1705.02994 (2017) - [i101]Emmanuel Abbe, Laurent Massoulié, Andrea Montanari, Allan Sly, Nikhil Srivastava:
Group Synchronization on Grids. CoRR abs/1706.08561 (2017) - [i100]Raphaël Berthier, Andrea Montanari, Phan-Minh Nguyen:
State Evolution for Approximate Message Passing with Non-Separable Functions. CoRR abs/1708.03950 (2017) - [i99]Marco Mondelli, Andrea Montanari:
Fundamental Limits of Weak Recovery with Applications to Phase Retrieval. CoRR abs/1708.05932 (2017) - [i98]Stratis Ioannidis, Andrea Montanari:
Learning Combinations of Sigmoids Through Gradient Estimation. CoRR abs/1708.06678 (2017) - [i97]Murat A. Erdogdu, Yash Deshpande, Andrea Montanari:
Inference in Graphical Models via Semidefinite Programming Hierarchies. CoRR abs/1709.06525 (2017) - 2016
- [j32]Andrea Montanari:
Effective compression maps for torus-based cryptography. Des. Codes Cryptogr. 79(1): 1-17 (2016) - [j31]Yash Deshpande, Andrea Montanari:
Sparse PCA via Covariance Thresholding. J. Mach. Learn. Res. 17: 141:1-141:41 (2016) - [j30]Andrea Montanari, Emile Richard:
Non-Negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics. IEEE Trans. Inf. Theory 62(3): 1458-1484 (2016) - [c71]Yash Deshpande, Emmanuel Abbe, Andrea Montanari:
Asymptotic mutual information for the binary stochastic block model. ISIT 2016: 185-189 - [c70]Andrea Montanari, Subhabrata Sen:
Semidefinite programs on sparse random graphs and their application to community detection. STOC 2016: 814-827 - [i96]Adel Javanmard, Andrea Montanari:
Online Rules for Control of False Discovery Rate and False Discovery Exceedance. CoRR abs/1603.09000 (2016) - [i95]Adel Javanmard, Andrea Montanari, Federico Ricci-Tersenghi:
Performance of a community detection algorithm based on semidefinite programming. CoRR abs/1603.09045 (2016) - [i94]Zhou Fan, Andrea Montanari:
How Well Do Local Algorithms Solve Semidefinite Programs? CoRR abs/1610.05350 (2016) - [i93]Andrea Montanari, Nike Sun:
Spectral algorithms for tensor completion. CoRR abs/1612.07866 (2016) - 2015
- [j29]Yash Deshpande, Andrea Montanari:
Finding Hidden Cliques of Size √(N/e) in Nearly Linear Time. Found. Comput. Math. 15(4): 1069-1128 (2015) - [j28]Mohsen Bayati, Christian Borgs, Jennifer T. Chayes, Yash Kanoria, Andrea Montanari:
Bargaining dynamics in exchange networks. J. Econ. Theory 156: 417-454 (2015) - [j27]Emmanuel Abbe, Andrea Montanari:
Conditional Random Fields, Planted Constraint Satisfaction, and Entropy Concentration. Theory Comput. 11: 413-443 (2015) - [c69]Murat A. Erdogdu, Nadia Fawaz, Andrea Montanari:
Privacy-Utility Trade-Off for Time-Series with Application to Smart-Meter Data. AAAI Workshop: Computational Sustainability 2015 - [c68]Mohsen Bayati, Sonia Bhaskar, Andrea Montanari:
A Low-Cost Method for Multiple Disease Prediction. AMIA 2015 - [c67]Yash Deshpande, Andrea Montanari:
Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems. COLT 2015: 523-562 - [c66]Andrea Montanari, Daniel Reichman, Ofer Zeitouni:
On the Limitation of Spectral Methods: From the Gaussian Hidden Clique Problem to Rank-One Perturbations of Gaussian Tensors. NIPS 2015: 217-225 - [c65]Murat A. Erdogdu, Andrea Montanari:
Convergence rates of sub-sampled Newton methods. NIPS 2015: 3052-3060 - [i92]Andrea Montanari:
Finding One Community in a Sparse Graph. CoRR abs/1502.05680 (2015) - [i91]Adel Javanmard, Andrea Montanari:
On Online Control of False Discovery Rate. CoRR abs/1502.06197 (2015) - [i90]Yash Deshpande, Andrea Montanari:
Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems. CoRR abs/1502.06590 (2015) - [i89]Amir Dembo, Andrea Montanari, Subhabrata Sen:
Extremal Cuts of Sparse Random Graphs. CoRR abs/1503.03923 (2015) - [i88]Andrea Montanari, Subhabrata Sen:
Semidefinite Programs on Sparse Random Graphs. CoRR abs/1504.05910 (2015) - [i87]Jeffrey G. Andrews, Alexandros G. Dimakis, Lara Dolecek, Michelle Effros, Muriel Médard, Olgica Milenkovic, Andrea Montanari, Sriram Vishwanath, Edmund M. Yeh, Randall Berry, Ken R. Duffy, Soheil Feizi, Saul Kato, Manolis Kellis, Stuart Licht, Jon Sorenson, Lav R. Varshney, Haris Vikalo:
A Perspective on Future Research Directions in Information Theory. CoRR abs/1507.05941 (2015) - [i86]Yash Deshpande, Emmanuel Abbe, Andrea Montanari:
Asymptotic Mutual Information for the Two-Groups Stochastic Block Model. CoRR abs/1507.08685 (2015) - [i85]Hamid Haj Seyed Javadi, Andrea Montanari:
The Hidden Subgraph Problem. CoRR abs/1511.05254 (2015) - [i84]Adel Javanmard, Andrea Montanari, Federico Ricci-Tersenghi:
Phase Transitions in Semidefinite Relaxations. CoRR abs/1511.08769 (2015) - 2014
- [j26]Adel Javanmard, Andrea Montanari:
Confidence intervals and hypothesis testing for high-dimensional regression. J. Mach. Learn. Res. 15(1): 2869-2909 (2014) - [j25]Emmanuel Abbe, Andrea Montanari:
On the concentration of the number of solutions of random satisfiability formulas. Random Struct. Algorithms 45(3): 362-382 (2014) - [j24]Adel Javanmard, Andrea Montanari:
Hypothesis Testing in High-Dimensional Regression Under the Gaussian Random Design Model: Asymptotic Theory. IEEE Trans. Inf. Theory 60(10): 6522-6554 (2014) - [j23]Morteza Ibrahimi, Andrea Montanari, George S. Moore:
Accelerated Time-of-Flight Mass Spectrometry. IEEE Trans. Signal Process. 62(15): 3784-3798 (2014) - [c64]Yuekai Sun, Stratis Ioannidis, Andrea Montanari:
Learning Mixtures of Linear Classifiers. ICML 2014: 721-729 - [c63]Yash Deshpande, Andrea Montanari:
Information-theoretically optimal sparse PCA. ISIT 2014: 2197-2201 - [c62]Yash Deshpande, Andrea Montanari:
Sparse PCA via Covariance Thresholding. NIPS 2014: 334-342 - [c61]Yash Deshpande, Andrea Montanari, Emile Richard:
Cone-Constrained Principal Component Analysis. NIPS 2014: 2717-2725 - [c60]Emile Richard, Andrea Montanari:
A statistical model for tensor PCA. NIPS 2014: 2897-2905 - [c59]Stratis Ioannidis, Andrea Montanari, Udi Weinsberg, Smriti Bhagat, Nadia Fawaz, Nina Taft:
Privacy tradeoffs in predictive analytics. SIGMETRICS 2014: 57-69 - [i83]Yash Deshpande, Andrea Montanari:
Information-theoretically Optimal Sparse PCA. CoRR abs/1402.2238 (2014) - [i82]Stratis Ioannidis, Andrea Montanari, Udi Weinsberg, Smriti Bhagat, Nadia Fawaz, Nina Taft:
Privacy Tradeoffs in Predictive Analytics. CoRR abs/1403.8084 (2014) - [i81]Andrea Montanari, Emile Richard:
Non-negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics. CoRR abs/1406.4775 (2014) - [i80]Amy Zhang, Nadia Fawaz, Stratis Ioannidis, Andrea Montanari:
Guess Who Rated This Movie: Identifying Users Through Subspace Clustering. CoRR abs/1408.2055 (2014) - [i79]Andrea Montanari:
Computational Implications of Reducing Data to Sufficient Statistics. CoRR abs/1409.3821 (2014) - [i78]Eric W. Tramel, Santhosh Kumar, Andrei Giurgiu, Andrea Montanari:
Statistical Estimation: From Denoising to Sparse Regression and Hidden Cliques. CoRR abs/1409.5557 (2014) - [i77]Andrea Montanari, Emile Richard:
A statistical model for tensor PCA. CoRR abs/1411.1076 (2014) - [i76]Andrea Montanari, Daniel Reichman, Ofer Zeitouni:
On the limitation of spectral methods: From the Gaussian hidden clique problem to rank one perturbations of Gaussian tensors. CoRR abs/1411.6149 (2014) - 2013
- [j22]Adel Javanmard, Andrea Montanari:
Localization from Incomplete Noisy Distance Measurements. Found. Comput. Math. 13(3): 297-345 (2013) - [j21]Andrea Montanari, Rüdiger L. Urbanke:
Iterative Coding for Network Coding. IEEE Trans. Inf. Theory 59(3): 1563-1572 (2013) - [j20]David L. Donoho, Iain M. Johnstone, Andrea Montanari:
Accurate Prediction of Phase Transitions in Compressed Sensing via a Connection to Minimax Denoising. IEEE Trans. Inf. Theory 59(6): 3396-3433 (2013) - [j19]Yashodhan Kanoria, Andrea Montanari:
Optimal Coding for the Binary Deletion Channel With Small Deletion Probability. IEEE Trans. Inf. Theory 59(