Alfredo Braunstein

/home /code /teaching /research /rand

Research

I have many interests related to math, physics and computing. The main one can be broadly defined as the Statistical Physics of computation. More in particular, I normally get excited about inference and optimization problems, game theory, out-of-equilibrium dynamics and communication theory.

Topics

Colleagues from Torino

Alireza Alemi, Fabrizio Altarelli, Luca Dall’Asta, Carlo Baldassi, Indaco Biazzo, Jacopo Bindi, Claudio Borile, Carla Bosia, Christoph Feinauer, Alessandro Ingrosso, Farbod Kayhan, Anna Paola Muntoni, Andrea Pagnani, Luca Saglietti, Marco Zamparo, Riccardo Zecchina

Publications (bibtex)

  1. Saldida, J, Muntoni, A P, Martino, D de, Hubmann, G, Niebel, B, Schmidt, A M, Braunstein, A, Milias-Argeitis, A, and Heinemann, M, 2020, “Unbiased metabolic flux inference through combined thermodynamic and 13C flux analysis” bioRxiv 2020.06.29.177063, https://www.biorxiv.org/content/10.1101/2020.06.29.177063v1.
  2. Ortega, E, Braunstein, A, and Lage-Castellanos, A, 2020, “Contamination source detection in water distribution networks using belief propagation” Stochastic Environmental Research and Risk Assessment 34(3) 493–511, https://doi.org/10.1007/s00477-020-01788-y.
  3. Braunstein, A, Muntoni, A P, Pagnani, A, and Pieropan, M, 2020, “Compressed sensing reconstruction using expectation propagation” Journal of Physics A: Mathematical and Theoretical 53(18) 184001, https://doi.org/10.1088%2F1751-8121%2Fab3065.
  4. Braunstein, A, Dall’Asta, L, and Ingrosso, A, 2020, “Casualità, causalità e Machine Learning nel contenimento epidemico” Ithaca: viaggio nella scienza XVI 12, http://ithaca.unisalento.it/nr-16_2020/articolo_IIp_13.pdf.
  5. Braunstein, A, Catania, G, Dall’Asta, L, and Muntoni, A P, 2020, “A Density Consistency approach to the inverse Ising problem” arXiv:2010.13746 [cond-mat], http://arxiv.org/abs/2010.13746.
  6. Baker, A, Biazzo, I, Braunstein, A, Catania, G, Dall’Asta, L, Ingrosso, A, Krzakala, F, Mazza, F, Mézard, M, Muntoni, A P, Refinetti, M, Mannelli, S S, and Zdeborová, L, 2020, “Epidemic mitigation by statistical inference from contact tracing data” arXiv:2009.09422 [cond-mat, q-bio], http://arxiv.org/abs/2009.09422.
  7. Braunstein, A, Ingrosso, A, and Muntoni, A P, 2019, “Network reconstruction from infection cascades” Journal of The Royal Society Interface 16(151) 20180844, https://royalsocietypublishing.org/doi/full/10.1098/rsif.2018.0844.
  8. Braunstein, A, Catania, G, and Dall’Asta, L, 2019, “Loop Corrections in Spin Models through Density Consistency” Physical Review Letters 123(2) 020604, https://link.aps.org/doi/10.1103/PhysRevLett.123.020604.
  9. Muntoni, A P, Rojas, R D H, Braunstein, A, Pagnani, A, and Pérez Castillo, I, 2019, “Nonconvex image reconstruction via expectation propagation” Physical Review E 100(3) 032134, https://link.aps.org/doi/10.1103/PhysRevE.100.032134.
  10. Braunstein, A and Muntoni, A P, 2018, “The cavity approach for Steiner trees packing problems” Journal of Statistical Mechanics: Theory and Experiment 2018(12) 123401, https://doi.org/10.1088%2F1742-5468%2Faaeb3f.
  11. Bindi, J, Braunstein, A, and Dall’Asta, L, 2017, “Predicting epidemic evolution on contact networks from partial observations” PLOS ONE 12(4) e0176376, http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0176376.
  12. Braunstein, A, Muntoni, A P, and Pagnani, A, 2017, “An analytic approximation of the feasible space of metabolic networks” Nature Communications 8 14915, http://www.nature.com/ncomms/2017/170406/ncomms14915/full/ncomms14915.html.
  13. Braunstein, A, Lage-Castellanos, A, and Ortega, E, 2017, “Contamination source inference in water distribution networks” arXiv:1712.00486 [physics], http://arxiv.org/abs/1712.00486.
  14. Braunstein, A, Lage-Castellanos, A, and Ortega, E, 2017, “INFERENCIA DEL ORIGEN DE CONTAMINACION EN REDES HIDRICAS” Revista Cubana de Física 34(2) 100–108, https://go.gale.com/ps/i.do?p=IFME&sw=w&issn=02539268&v=2.1&it=r&id=GALE%7CA599660082&sid=googleScholar&linkaccess=abs.
  15. Braunstein, A, Dall’Asta, L, Semerjian, G, and Zdeborová, L, 2016, “Network dismantling” Proceedings of the National Academy of Sciences 201605083, http://www.pnas.org/content/early/2016/10/18/1605083113.
  16. Braunstein, A, Dall’Asta, L, Semerjian, G, and Zdeborová, L, 2016, “The large deviations of the whitening process in random constraint satisfaction problems” Journal of Statistical Mechanics: Theory and Experiment 2016(5) 053401, http://stacks.iop.org/1742-5468/2016/i=5/a=053401.
  17. Braunstein, A and Ingrosso, A, 2016, “Inference of causality in epidemics on temporal contact networks” Scientific Reports 6 27538, http://www.nature.com/articles/srep27538.
  18. Braunstein, A and Muntoni, A, 2016, “Practical optimization of Steiner trees via the cavity method” Journal of Statistical Mechanics: Theory and Experiment 2016(7) 073302, http://stacks.iop.org/1742-5468/2016/i=7/a=073302.
  19. Altarelli, F, Braunstein, A, and Dall’Asta, L, 2015, “Statics and Dynamics of Selfish Interactions in Distributed Service Systems” PLoS ONE 10(7) e0119286, http://dx.doi.org/10.1371/journal.pone.0119286.
  20. Baldassi, C and Braunstein, A, 2015, “A Max-Sum algorithm for training discrete neural networks” J. Stat. Mech. 2015(8) P08008, http://iopscience.iop.org/1742-5468/2015/8/P08008.
  21. Baldassi, C, Braunstein, A, Ramezanpour, A, and Zecchina, R, 2015, “Statistical Physics and Network Optimization Problems,” in Mathematical Foundations of Complex Networked Information Systems Eds F Fagnani, S M Fosson, and C Ravazzi Lecture Notes in Mathematics (Springer International Publishing), pp 27–49, http://link.springer.com/chapter/10.1007/978-3-319-16967-5_2.
  22. Altarelli, F, Braunstein, A, Dall’Asta, L, De Bacco, C, and Franz, S, 2015, “The Edge-Disjoint Path Problem on Random Graphs by Message-Passing” PLoS ONE 10(12) e0145222, http://dx.doi.org/10.1371/journal.pone.0145222.
  23. Altarelli, F, Braunstein, A, Dall’Asta, L, Lage-Castellanos, A, and Zecchina, R, 2014, “Bayesian Inference of Epidemics on Networks via Belief Propagation” Phys. Rev. Lett. 112(11) 118701, http://link.aps.org/doi/10.1103/PhysRevLett.112.118701.
  24. Altarelli, F, Braunstein, A, Dall’Asta, L, Wakeling, J R, and Zecchina, R, 2014, “Containing Epidemic Outbreaks by Message-Passing Techniques” Phys. Rev. X 4(2) 021024, http://link.aps.org/doi/10.1103/PhysRevX.4.021024.
  25. Altarelli, F, Braunstein, A, Dall’Asta, L, Ingrosso, A, and Zecchina, R, 2014, “The patient-zero problem with noisy observations” Journal of Statistical Mechanics: Theory and Experiment 2014(10) P10016, http://iopscience.iop.org/1742-5468/2014/10/P10016.
  26. Altarelli, F, Braunstein, A, Dall’Asta, L, and Zecchina, R, 2013, “Large deviations of cascade processes on graphs” Phys. Rev. E 87(6) 062115, http://link.aps.org/doi/10.1103/PhysRevE.87.062115.
  27. Altarelli, F, Braunstein, A, Dall’Asta, L, and Zecchina, R, 2013, “Optimizing spread dynamics on graphs by message passing” J. Stat. Mech. 2013(09) P09011, http://iopscience.iop.org/1742-5468/2013/09/P09011.
  28. Leonardi, E, Dall’Asta, L, Chiasserini, C F, Giaccone, P, Braunstein, A, Zecchina, R, and Altarelli, F, 2013, “Stochastic Optimization of Service Provision with Selfish Users,” in (IEEE / Institute of Electrical and Electronics Engineers Incorporated:445 Hoes Lane:Piscataway, NJ 08854, Budapest (Hungary), http://porto.polito.it/2506220/.
  29. Baldassi, C, Braunstein, A, and Zecchina, R, 2013, “Theory and learning protocols for the material tempotron model” J. Stat. Mech. 2013(12) P12013, http://iopscience.iop.org/1742-5468/2013/12/P12013.
  30. Molinelli, E J, Korkut, A, Wang, W, Miller, M L, Gauthier, N P, Jing, X, Kaushik, P, He, Q, Mills, G, Solit, D B, Pratilas, C A, Weigt, M, Braunstein, A, Pagnani, A, Zecchina, R, and Sander, C, 2013, “Perturbation Biology: Inferring Signaling Networks in Cellular Systems” PLoS Comput Biol 9(12) e1003290, http://dx.doi.org/10.1371/journal.pcbi.1003290.
  31. Alemi-Neissi, A, Baldassi, C, Braunstein, A, Pagnani, A, Zecchina, R, and Zoccolan, D, 2012, “Information theoretic and machine learning approaches to quantify non-linear visual feature interaction underlying visual object recognition” BMC Neuroscience 13 1–2, http://dx.doi.org/10.1186/1471-2202-13-S1-P2.
  32. Biazzo, I, Braunstein, A, and Zecchina, R, 2012, “Performance of a cavity-method-based algorithm for the prize-collecting Steiner tree problem on graphs” Phys. Rev. E 86 026706, http://link.aps.org/doi/10.1103/PhysRevE.86.026706.
  33. Tuncbag, N, Braunstein, A, Pagnani, A, Huang, S-S C, Chayes, J, Borgs, C, Zecchina, R, and Fraenkel, E, 2012, “Simultaneous Reconstruction of Multiple Signaling Pathways via the Prize-Collecting Steiner Forest Problem,” in Research in Computational Molecular Biology Ed B Chor Lecture Notes in Computer Science (Springer Berlin Heidelberg), pp 287–301, http://dx.doi.org/10.1007/978-3-642-29627-7_31.
  34. Braunstein, A, Kayhan, F, and Zecchina, R, 2011, “Efficient data compression from statistical physics of codes over finite fields” Phys. Rev. E 84(5) 051111, http://link.aps.org/doi/10.1103/PhysRevE.84.051111.
  35. Bailly-Bechet, M, Borgs, C, Braunstein, A, Chayes, J, Dagkessamanskaia, A, François, J-M, and Zecchina, R, 2011, “Finding undetected protein associations in cell signaling by belief propagation” PNAS 108(2) 882–887, http://www.pnas.org/content/108/2/882.
  36. Braunstein, A, Ramezanpour, A, Zecchina, R, and Zhang, P, 2011, “Inference and learning in sparse systems with multiple states” Phys. Rev. E 83(5) 056114, http://link.aps.org/doi/10.1103/PhysRevE.83.056114.
  37. Altarelli, F, Braunstein, A, Ramezanpour, A, and Zecchina, R, 2011, “Stochastic Matching Problem” Phys. Rev. Lett. 106(19) 190601, http://link.aps.org/doi/10.1103/PhysRevLett.106.190601.
  38. Altarelli, F, Braunstein, A, Ramezanpour, A, and Zecchina, R, 2011, “Stochastic optimization by message passing” J. Stat. Mech. 2011(11) P11009, http://iopscience.iop.org/1742-5468/2011/11/P11009.
  39. Bradde, S, Braunstein, A, Mahmoudi, H, Tria, F, Weigt, M, and Zecchina, R, 2010, “Aligning graphs and finding substructures by a cavity approach” EPL 89(3) 37009, http://iopscience.iop.org/0295-5075/89/3/37009.
  40. Bailly-Bechet, M, Braunstein, A, Pagnani, A, Weigt, M, and Zecchina, R, 2010, “Inference of sparse combinatorial-control networks from gene-expression data: a message passing approach” BMC Bioinformatics 11(1) 355, http://www.biomedcentral.com/1471-2105/11/355/abstract.
  41. Bailly-Bechet, M, Braunstein, A, and Zecchina, R, 2009, “A Prize-Collecting Steiner Tree Approach for Transduction Network Inference,” in Computational Methods in Systems Biology Eds P Degano and R Gorrieri Lecture Notes in Computer Science (Springer Berlin Heidelberg), pp 83–95, http://link.springer.com/chapter/10.1007/978-3-642-03845-7_6.
  42. Bailly-Bechet, M, Bradde, S, Braunstein, A, Flaxman, A, Foini, L, and Zecchina, R, 2009, “Clustering with shallow trees” Journal of Statistical Mechanics: Theory and Experiment 17pp, http://www.iop.org/EJ/abstract/1742-5468/2009/12/P12010.
  43. Braunstein, A, Kayhan, F, and Zecchina, R, 2009, “Efficient LDPC Codes over GF(q) for Lossy Data Compression,” in IEEE International Symposium on Information Theory, 2009. ISIT 2009 (Seul, Korea), http://arxiv.org/abs/0901.4467.
  44. Altarelli, F, Braunstein, A, Realpe-Gomez, J, and Zecchina, R, 2009, “Statistical mechanics of budget-constrained auctions” J. Stat. Mech. 2009(07) P07002, http://iopscience.iop.org/1742-5468/2009/07/P07002.
  45. Bayati, M, Braunstein, A, and Zecchina, R, 2008, “A rigorous analysis of the cavity equations for the minimum spanning tree” Journal of Mathematical Physics 49(12) 125206, http://link.aip.org/link/?JMP/49/125206/1.
  46. Braunstein, A, Mulet, R, and Pagnani, A, 2008, “Estimating the size of the solution space of metabolic networks” BMC Bioinformatics 9(1) 240, http://www.biomedcentral.com/1471-2105/9/240/abstract.
  47. Braunstein, A, Pagnani, A, Weigt, M, and Zecchina, R, 2008, “Gene-network inference by message passing” J. Phys.: Conf. Ser. 95(1) 012016, http://iopscience.iop.org/1742-6596/95/1/012016.
  48. Braunstein, A, Pagnani, A, Weigt, M, and Zecchina, R, 2008, “Inference algorithms for gene networks: a statistical mechanics analysis” J. Stat. Mech. 2008(12) P12001, http://iopscience.iop.org/1742-5468/2008/12/P12001.
  49. Bayati, M, Borgs, C, Braunstein, A, Chayes, J, Ramezanpour, A, and Zecchina, R, 2008, “Statistical Mechanics of Steiner Trees” Phys. Rev. Lett. 101(3) 037208, http://link.aps.org/doi/10.1103/PhysRevLett.101.037208.
  50. Braunstein, A, Mulet, R, and Pagnani, A, 2008, “The space of feasible solutions in metabolic networks” J. Phys.: Conf. Ser. 95(1) 012017, http://iopscience.iop.org/1742-6596/95/1/012017.
  51. Baldassi, C, Braunstein, A, Brunel, N, and Zecchina, R, 2007, “Efficient supervised learning in networks with binary synapses” BMC Neuroscience 8(Suppl 2) S13.
  52. Baldassi, C, Braunstein, A, Brunel, N, and Zecchina, R, 2007, “Efficient supervised learning in networks with binary synapses” PNAS 104(26) 11079–11084, http://www.pnas.org/content/104/26/11079.
  53. Braunstein, A, Kayhan, F, Montorsi, G, and Zecchina, R, 2007, “Encoding for the Blackwell Channel with Reinforced Belief Propagation,” in IEEE International Symposium on Information Theory (ISIT07), pp 1891–1895.
  54. Braunstein, A and Zecchina, R, 2006, “Learning by Message Passing in Networks of Discrete Synapses” Phys. Rev. Lett. 96(3) 030201, http://link.aps.org/doi/10.1103/PhysRevLett.96.030201.
  55. Braunstein, A, Mézard, M, Weigt, M, and Zecchina, R, 2005, “Constraint satisfaction by survey propagation,” in Advances in Neural Information Processing Systems Eds A Percus, G Istrate, and C Moore Computational Complexity and Statistical Physics (Oxford University Press), p 424, http://arxiv.org/abs/cond-mat/0212451.
  56. Battaglia, D, Braunstein, A, Chavas, J, and Zecchina, R, 2005, “Exact Probing of Glassy States by Survey Propagation,” in Prog. Theor. Phys. Suppl., pp 330–337.
  57. Battaglia, D, Braunstein, A, Chavas, J, and Zecchina, R, 2005, “Source coding by efficient selection of ground-state clusters” Phys. Rev. E 72(1) 015103, http://link.aps.org/doi/10.1103/PhysRevE.72.015103.
  58. Braunstein, A, Mézard, M, and Zecchina, R, 2005, “Survey Propagation: an algorithm for satisfiability” Random Structures Algorithms 27 201–226, http://arxiv.org/abs/cs/0212002.
  59. Braunstein, A and Zecchina, R, 2004, “Survey and Belief Propagation on Random K-SAT,” in Theory and Applications of Satisfiability Testing Eds E Giunchiglia and A Tacchella Lecture Notes in Computer Science (Springer Berlin Heidelberg), pp 519–528, http://link.springer.com/chapter/10.1007/978-3-540-24605-3_38.
  60. Braunstein, A and Zecchina, R, 2004, “Survey propagation as local equilibrium equations” J. Stat. Mech. 2004(06) P06007, http://iopscience.iop.org/1742-5468/2004/06/P06007.
  61. Braunstein, A, Mulet, R, Pagnani, A, Weigt, M, and Zecchina, R, 2003, “Polynomial iterative algorithms for coloring and analyzing random graphs” Phys. Rev. E 68(3) 036702, http://link.aps.org/doi/10.1103/PhysRevE.68.036702.
  62. Braunstein, A, Leone, M, Ricci-Tersenghi, F, and Zecchina, R, 2002, “Complexity transitions in global algorithms for sparse linear systems over finite fields” J. Phys. A: Math. Gen. 35(35) 7559, http://iopscience.iop.org/0305-4470/35/35/301.

My manuscripts on arxiv.

Alfredo Braunstein
Politecnico di Torino - DISAT
Human Genetics Foundation

www.polito.it/cmp
name.surname at polito dot it
LinkedIn