BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Allan Sly (Princeton)
DTSTART:20210809T130500Z
DTEND:20210809T135500Z
DTSTAMP:20260422T185352Z
UID:BIRS-21w5108/1
DESCRIPTION:by Allan Sly (Princeton) as part of BIRS workshop: Random Grap
 hs and Statistical Inference: New Methods and Applications\n\nAbstract: TB
 A\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5108/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Charilaos Efthymiou (University of Warwick)
DTSTART:20210809T141500Z
DTEND:20210809T144000Z
DTSTAMP:20260422T185352Z
UID:BIRS-21w5108/2
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5108
 /2/">On sampling symmetric Gibbs distributions on sparse random (hyper)gra
 phs with contiguity</a>\nby Charilaos Efthymiou (University of Warwick) as
  part of BIRS workshop: Random Graphs and Statistical Inference: New Metho
 ds and Applications\n\n\nAbstract\nIn this paper\, we present  a polynomia
 l time  algorithm for approximate  sampling from  symmetric Gibbs distribu
 tions on the sparse random graph and hypergraph. The examples  include (bu
 t   are not restricted to)  some  important distributions on  spin-systems
  and spin-glasses.  We consider  the $q$ state antiferromagnetic  Potts mo
 del for $q\\geq 2$\, including the (hyper)graph colourings. We  also consi
 der  the uniform distribution over the  Not-All-Equal solutions of a  rand
 om $k$-SAT instance.  Finally\,  we consider sampling from   the {\\em spi
 n-glass}  distribution called the $k$-spin model.  The $k$-spin model is e
 ssentially a diluted version of the well-known Sherrington-Kirkpatrick mod
 el.  To our knowledge\, this is the first rigorously analysed efficient al
 gorithm for spin-glasses which operates in a non trivial range of the para
 meters of the distribution.\n\nWe make a major progress regarding the impr
 essive predictions of physicists relating phase-transitions of   Gibbs dis
 tributions with the efficiency of the corresponding  sampling algorithms. 
 We present\, what we believe to be\, an elegant  sampling algorithm for  s
 ymmetric Gibbs  distributions.  Our algorithm is  unique in its approach a
 nd does not belong to any  of the well-known families of sampling algorith
 ms.  We derive this algorithm by investigating the power and the limits of
  the the approach  that was introduced in [Efthymiou: SODA 2012].\n\nFor t
 he cases we consider here\, our algorithm  outperforms by far all  other s
 ampling algorithms  in terms of  the permitted range of the parameters of 
 the  Gibbs distributions.  For the graph case\,  we show that our algorith
 m operates in a range of the parameters that coincides  with the (in many 
 cases conjectured) tree-uniqueness  region\,  parametrised w.r.t. the {\\e
 m expected degree} of the graph.  For the hypergraph case\, where uniquene
 ss is less restrictive for algorithmic purposes\,  it operates beyond\nthe
   uniqueness region.\n\nFor a  symmetric Gibbs distribution $\\mu$  on the
  random (hyper)graph whose parameters are within an  appropriate  range\, 
 our sampling  algorithm has the following  properties: with probability $1
 -o(1)$ over the instances of the input  (hyper)graph\,  it   generates  a 
 configuration which is distributed within total variation distance $n^{-\\
 Omega(1)}$  from $\\mu$. The time complexity is $O((n\\log n)^2)$\, where 
   $n$ is the size of the input (hyper)graph.\n\nWe give a new insight to t
 he  problem by  exploiting  phenomena of\nthe Gibbs distributions that wer
 e not previously used by sampling  algorithms.  Our approach allows us to 
  utilise  the notion of {\\em contiguity} between Gibbs distributions and 
 the so-called  {\\em teacher-student model}\,  with the later distribution
  also known in  various contexts as the {\\em planted model}.   This  brin
 gs together  tools and\nnotions from sampling  and statistical inference a
 lgorithms.\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5108/2/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Fiona Skerman (Uppsala University)
DTSTART:20210809T144500Z
DTEND:20210809T151000Z
DTSTAMP:20260422T185352Z
UID:BIRS-21w5108/3
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5108
 /3/">Modularity and edge-sampling</a>\nby Fiona Skerman (Uppsala Universit
 y) as part of BIRS workshop: Random Graphs and Statistical Inference: New 
 Methods and Applications\n\n\nAbstract\nWe analyse when community structur
 e of an underlying graph can be determined from an observed subset of the 
 graph. \n\nModularity is a function on graphs which is used in algorithms 
 for community detection. For a given graph G\, each partition of the verti
 ces has a modularity score\, with higher values indicating that the partit
 ion better captures community structure in G. The (max) modularity q*(G) o
 f the graph G is defined to be the maximum over all vertex partitions of t
 he modularity score\, and satisfies 0≤q*(G)≤1.\n\nIn a natural model w
 here we suppose edges in an underlying graph G appear independently with s
 ome probability in our observed graph G' we describe how high a sampling p
 robability we need to infer the modularity of the underlying graph from th
 e modularity of the observed graph. \n\nJoint work with Colin McDiarmid.\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5108/3/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alan Frieze (Carnegie Mellon University\, USA)
DTSTART:20210809T153000Z
DTEND:20210809T155500Z
DTSTAMP:20260422T185352Z
UID:BIRS-21w5108/4
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5108
 /4/">Spanners in randomly weighted graphs</a>\nby Alan Frieze (Carnegie Me
 llon University\, USA) as part of BIRS workshop: Random Graphs and Statist
 ical Inference: New Methods and Applications\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5108/4/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Subhabrata Sen (Harvard)
DTSTART:20210809T160000Z
DTEND:20210809T162500Z
DTSTAMP:20260422T185352Z
UID:BIRS-21w5108/5
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5108
 /5/">Large deviations for dense random graphs: beyond mean-field</a>\nby S
 ubhabrata Sen (Harvard) as part of BIRS workshop: Random Graphs and Statis
 tical Inference: New Methods and Applications\n\n\nAbstract\nIn a seminal 
 paper\, Chatterjee and Varadhan derived an LDP for the dense\nErd˝os-R´e
 nyi random graph\, viewed as a random graphon. This directly provides LDPs
  for continuous functionals such as subgraph counts\, spectral norms\,\net
 c. In contrast\, very little is understood about this problem if the under
 lying\nrandom graph is inhomogeneous or constrained.\nIn this talk\, we wi
 ll explore large deviations for dense random graphs\, beyond the “mean-f
 ield” setting. In particular\, we will study large deviations for\nunifo
 rm random graphs with given degrees\, and a family of dense block model\nr
 andom graphs. We will establish the LDP in each case\, and identify the ra
 te\nfunction. In the block model setting\, we will use this LDP to study t
 he upper\ntail problem for homomorphism densities of regular sub-graphs. O
 ur results\nestablish that this problem exhibits a symmetry/symmetry-break
 ing transition\,\nsimilar to one observed for Erd˝os-R´enyi random graph
 s.\nBased on joint works with Christian Borgs\, Jennifer Chayes\, Souvik D
 hara\,\nJulia Gaudio and Samantha Petti\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5108/5/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Po-Ling Loh (University of Cambridge)
DTSTART:20210810T130000Z
DTEND:20210810T135000Z
DTSTAMP:20260422T185352Z
UID:BIRS-21w5108/6
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5108
 /6/">Optimal rates for community estimation in the weighted stochastic blo
 ck model</a>\nby Po-Ling Loh (University of Cambridge) as part of BIRS wor
 kshop: Random Graphs and Statistical Inference: New Methods and Applicatio
 ns\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5108/6/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Anna Paola Muntoni (Politecnico di Torino)
DTSTART:20210810T141500Z
DTEND:20210810T144000Z
DTSTAMP:20260422T185352Z
UID:BIRS-21w5108/7
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5108
 /7/">Epidemic mitigation by statistical inference from contact tracing dat
 a</a>\nby Anna Paola Muntoni (Politecnico di Torino) as part of BIRS works
 hop: Random Graphs and Statistical Inference: New Methods and Applications
 \n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5108/7/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Markus Heydenreich (LMU Munich)
DTSTART:20210810T144500Z
DTEND:20210810T151000Z
DTSTAMP:20260422T185352Z
UID:BIRS-21w5108/8
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5108
 /8/">Distances in Scale-free percolation</a>\nby Markus Heydenreich (LMU M
 unich) as part of BIRS workshop: Random Graphs and Statistical Inference: 
 New Methods and Applications\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5108/8/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jean Ravelomanana (Goethe University Frankfurt)
DTSTART:20210810T153000Z
DTEND:20210810T155500Z
DTSTAMP:20260422T185352Z
UID:BIRS-21w5108/9
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5108
 /9/">The Sparse Parity Matrix</a>\nby Jean Ravelomanana (Goethe University
  Frankfurt) as part of BIRS workshop: Random Graphs and Statistical Infere
 nce: New Methods and Applications\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5108/9/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mark Sellke (Stanford)
DTSTART:20210810T160000Z
DTEND:20210810T162500Z
DTSTAMP:20260422T185352Z
UID:BIRS-21w5108/10
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5108
 /10/">Algorithmic pure states for the negative spherical perceptron</a>\nb
 y Mark Sellke (Stanford) as part of BIRS workshop: Random Graphs and Stati
 stical Inference: New Methods and Applications\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5108/10/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jean Barbier (ICTP)
DTSTART:20210811T150000Z
DTEND:20210811T155000Z
DTSTAMP:20260422T185352Z
UID:BIRS-21w5108/11
DESCRIPTION:by Jean Barbier (ICTP) as part of BIRS workshop: Random Graphs
  and Statistical Inference: New Methods and Applications\n\nAbstract: TBA\
 n
LOCATION:https://researchseminars.org/talk/BIRS-21w5108/11/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Cecilia Holmgren (Uppsala University)
DTSTART:20210811T161000Z
DTEND:20210811T163500Z
DTSTAMP:20260422T185352Z
UID:BIRS-21w5108/12
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5108
 /12/">The asymptotic distribution of cluster sizes for supercritical perco
 lation on random split trees</a>\nby Cecilia Holmgren (Uppsala University)
  as part of BIRS workshop: Random Graphs and Statistical Inference: New Me
 thods and Applications\n\n\nAbstract\nWe consider the model of random tree
 s introduced by\n Devroye (1998)\, the so-called random split trees. The m
 odel\n encompasses many important randomized algorithms and data\n structu
 res. We then perform supercritical Bernoulli\n bond-percolation on those t
 rees and obtain the asymptotic\n distribution for the sizes of the largest
  clusters.\nJoint work with Gabriel Berzunza\,\n University of Liverpool\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5108/12/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Joshua Erde (TU Graz)
DTSTART:20210811T164000Z
DTEND:20210811T170500Z
DTSTAMP:20260422T185352Z
UID:BIRS-21w5108/13
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5108
 /13/">Expansion in the giant component of the percolated hypercube</a>\nby
  Joshua Erde (TU Graz) as part of BIRS workshop: Random Graphs and Statist
 ical Inference: New Methods and Applications\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5108/13/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ilias Zadik (New York University)
DTSTART:20210811T172000Z
DTEND:20210811T174500Z
DTSTAMP:20260422T185352Z
UID:BIRS-21w5108/14
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5108
 /14/">Noiseless phase retrieval: Closing the computational gap via lattice
  basis reduction</a>\nby Ilias Zadik (New York University) as part of BIRS
  workshop: Random Graphs and Statistical Inference: New Methods and Applic
 ations\n\n\nAbstract\nIn this talk\, we discuss the prototypical inference
  setting of noiseless phase retrieval under (real) standard Gaussian featu
 re vectors. Albeit a long line of work\, this inference setting exhibits a
  computational-statistical gap where while  (1+o(1))d samples are sufficie
 nt for recovery of the hidden d-dimensional vector\, the best-known polyno
 mial-time algorithm achieving recovery (a variant of approximate message p
 assing) requires approximately 1.12d samples. In this work\, we present a 
 novel polynomial-time algorithm that provably works with access to only d+
 1 samples\, and therefore closes the computational-statistical gap for thi
 s noiseless model. Our proposed successful algorithm is based on a potenti
 ally surprising use of the celebrated Lenstra-Lenstra-Lovasz lattice basis
  reduction algorithm. \n\nThis is joint work with Min Jae Song and Joan Br
 una.\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5108/14/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Guangyan Zhou (Beijing Technology and Business University)
DTSTART:20210812T120000Z
DTEND:20210812T122500Z
DTSTAMP:20260422T185352Z
UID:BIRS-21w5108/15
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5108
 /15/">Hiding solutions in model RB: Forced instances are almost as hard as
  unforced ones</a>\nby Guangyan Zhou (Beijing Technology and Business Univ
 ersity) as part of BIRS workshop: Random Graphs and Statistical Inference:
  New Methods and Applications\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5108/15/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Max Hahn-Klimroth (Goethe University Frankfurt)
DTSTART:20210812T123000Z
DTEND:20210812T125500Z
DTSTAMP:20260422T185352Z
UID:BIRS-21w5108/16
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5108
 /16/">ALMOST OPTIMAL EFFICIENT DECODING FROM SPARSE POOLED DATA</a>\nby Ma
 x Hahn-Klimroth (Goethe University Frankfurt) as part of BIRS workshop: Ra
 ndom Graphs and Statistical Inference: New Methods and Applications\n\n\nA
 bstract\nIn the pooled data problem\, one tries to recover a signal x ∈{
 0\, 1\, 2\, . . . \,d}^n from a measurement matrix A and the results of jo
 int measurements Ax=y. It is therefore a special case of the famous compre
 ssed sensing problem with a discrete signal and a generalisation of the fr
 equently studied quantitative group testing problem (d=1). The task become
 s explicitly interesting if the signal is sparse (||x||_0=k << n). It is a
  well known fact that there are exponential time constructions to recover 
 x from (A\,y) with no more than O(k) measurements but all known efficient 
 (polynomial time) constructions require at least Ω(k ln(n)) measurements
  and it was believed that closing this gap is hard. We show that this addi
 tional ln(n) factor is actually artificial by providing a randomised effic
 ient construction A_{SC} coming with an efficient decoding algorithm that 
 recovers x from (A_{SC}\,y) with high probability with no more than O(k) m
 easurements. This is based on joint work with Noela Müller.\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5108/16/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Oliver Cooley (Graz University of Technology)
DTSTART:20210812T143000Z
DTEND:20210812T145500Z
DTSTAMP:20260422T185352Z
UID:BIRS-21w5108/17
DESCRIPTION:by Oliver Cooley (Graz University of Technology) as part of BI
 RS workshop: Random Graphs and Statistical Inference: New Methods and Appl
 ications\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5108/17/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alex Wein (NYU)
DTSTART:20210812T150000Z
DTEND:20210812T152500Z
DTSTAMP:20260422T185352Z
UID:BIRS-21w5108/18
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5108
 /18/">Low-Degree Hardness of Maximum Independent Set</a>\nby Alex Wein (NY
 U) as part of BIRS workshop: Random Graphs and Statistical Inference: New 
 Methods and Applications\n\n\nAbstract\nIn high-dimensional statistical pr
 oblems (including planted clique\, sparse PCA\, community detection\, etc.
 )\, the class of "low-degree polynomial algorithms" captures many leading 
 algorithmic paradigms such as spectral methods\, approximate message passi
 ng\, and local algorithms on sparse graphs. As such\, lower bounds against
  low-degree algorithms constitute concrete evidence for average-case hardn
 ess of statistical problems. This method has been widely successful at exp
 laining and predicting statistical-to-computational gaps in these settings
 .\n\nWhile prior work has understood the power of low-degree algorithms fo
 r problems with a "planted" signal\, we consider here the setting of "rand
 om optimization problems" (with no planted signal)\, including the problem
  of finding a large independent set in a sparse random graph\, as well as 
 the problem of optimizing the Hamiltonian of mean-field spin glass models.
  Focusing on the independent set problem\, we show that low-degree algorit
 hms can find independent sets of "half-optimal" size (log d/d)n but no lar
 ger\, which explains the failure of all known poly-time algorithms beyond 
 this threshold. The proof of the lower bound leverages stability propertie
 s of low-degree polynomials along with a variant of the so-called "ensembl
 e multi-overlap gap property"\, which is a structural property of the solu
 tion space.\n\nBased on arXiv:2004.12063 (joint with David Gamarnik and Au
 kosh Jagannath) and arXiv:2010.06563\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5108/18/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Shuangping Li (Princeton University)
DTSTART:20210812T153000Z
DTEND:20210812T155500Z
DTSTAMP:20260422T185352Z
UID:BIRS-21w5108/19
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5108
 /19/">Proof of the Contiguity Conjecture and Lognormal Limit for the Symme
 tric Perceptron</a>\nby Shuangping Li (Princeton University) as part of BI
 RS workshop: Random Graphs and Statistical Inference: New Methods and Appl
 ications\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5108/19/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Afonso Bandeira (ETH Zurich)
DTSTART:20210813T130000Z
DTEND:20210813T135000Z
DTSTAMP:20260422T185352Z
UID:BIRS-21w5108/20
DESCRIPTION:by Afonso Bandeira (ETH Zurich) as part of BIRS workshop: Rand
 om Graphs and Statistical Inference: New Methods and Applications\n\nAbstr
 act: TBA\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5108/20/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matthew Aldridge (University of Leeds)
DTSTART:20210813T141500Z
DTEND:20210813T144000Z
DTSTAMP:20260422T185352Z
UID:BIRS-21w5108/21
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5108
 /21/">Three random graph designs for group testing</a>\nby Matthew Aldridg
 e (University of Leeds) as part of BIRS workshop: Random Graphs and Statis
 tical Inference: New Methods and Applications\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5108/21/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Noela Muelle (TU Eindhoven)
DTSTART:20210813T144500Z
DTEND:20210813T151000Z
DTSTAMP:20260422T185352Z
UID:BIRS-21w5108/22
DESCRIPTION:by Noela Muelle (TU Eindhoven) as part of BIRS workshop: Rando
 m Graphs and Statistical Inference: New Methods and Applications\n\nAbstra
 ct: TBA\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5108/22/
END:VEVENT
END:VCALENDAR