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:20260404T041839Z
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://stable.researchseminars.org/talk/BIRS-21w5108/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Charilaos Efthymiou (University of Warwick)
DTSTART:20210809T141500Z
DTEND:20210809T144000Z
DTSTAMP:20260404T041839Z
UID:BIRS-21w5108/2
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/BIRS-
 21w5108/2/">On sampling symmetric Gibbs distributions on sparse random (hy
 per)graphs with contiguity</a>\nby Charilaos Efthymiou (University of Warw
 ick) as part of BIRS workshop: Random Graphs and Statistical Inference: Ne
 w Methods and Applications\n\n\nAbstract\nIn this paper\, we present  a po
 lynomial time  algorithm for approximate  sampling from  symmetric Gibbs d
 istributions on the sparse random graph and hypergraph. The examples  incl
 ude (but   are not restricted to)  some  important distributions on  spin-
 systems and spin-glasses.  We consider  the $q$ state antiferromagnetic  P
 otts model for $q\\geq 2$\, including the (hyper)graph colourings. We  als
 o consider  the uniform distribution over the  Not-All-Equal solutions of 
 a  random $k$-SAT instance.  Finally\,  we consider sampling from   the {\
 \em spin-glass}  distribution called the $k$-spin model.  The $k$-spin mod
 el is essentially a diluted version of the well-known Sherrington-Kirkpatr
 ick model.  To our knowledge\, this is the first rigorously analysed effic
 ient algorithm for spin-glasses which operates in a non trivial range of t
 he parameters of the distribution.\n\nWe make a major progress regarding t
 he impressive predictions of physicists relating phase-transitions of   Gi
 bbs distributions with the efficiency of the corresponding  sampling algor
 ithms. We present\, what we believe to be\, an elegant  sampling algorithm
  for  symmetric Gibbs  distributions.  Our algorithm is  unique in its app
 roach and does not belong to any  of the well-known families of sampling a
 lgorithms.  We derive this algorithm by investigating the power and the li
 mits of the the approach  that was introduced in [Efthymiou: SODA 2012].\n
 \nFor the cases we consider here\, our algorithm  outperforms by far all  
 other sampling algorithms  in terms of  the permitted range of the paramet
 ers of the  Gibbs distributions.  For the graph case\,  we show that our a
 lgorithm operates in a range of the parameters that coincides  with the (i
 n many cases conjectured) tree-uniqueness  region\,  parametrised w.r.t. t
 he {\\em expected degree} of the graph.  For the hypergraph case\, where u
 niqueness is less restrictive for algorithmic purposes\,  it operates beyo
 nd\nthe  uniqueness region.\n\nFor a  symmetric Gibbs distribution $\\mu$ 
  on the random (hyper)graph whose parameters are within an  appropriate  r
 ange\, our sampling  algorithm has the following  properties: with probabi
 lity $1-o(1)$ over the instances of the input  (hyper)graph\,  it   genera
 tes  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 insig
 ht to the  problem by  exploiting  phenomena of\nthe Gibbs distributions t
 hat were not previously used by sampling  algorithms.  Our approach allows
  us to  utilise  the notion of {\\em contiguity} between Gibbs distributio
 ns and the so-called  {\\em teacher-student model}\,  with the later distr
 ibution also known in  various contexts as the {\\em planted model}.   Thi
 s  brings together  tools and\nnotions from sampling  and statistical infe
 rence algorithms.\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5108/2/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Fiona Skerman (Uppsala University)
DTSTART:20210809T144500Z
DTEND:20210809T151000Z
DTSTAMP:20260404T041839Z
UID:BIRS-21w5108/3
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/BIRS-
 21w5108/3/">Modularity and edge-sampling</a>\nby Fiona Skerman (Uppsala Un
 iversity) as part of BIRS workshop: Random Graphs and Statistical Inferenc
 e: New Methods and Applications\n\n\nAbstract\nWe analyse when community s
 tructure 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 algo
 rithms for community detection. For a given graph G\, each partition of th
 e vertices has a modularity score\, with higher values indicating that the
  partition better captures community structure in G. The (max) modularity 
 q*(G) of the graph G is defined to be the maximum over all vertex partitio
 ns of the modularity score\, and satisfies 0≤q*(G)≤1.\n\nIn a natural 
 model where we suppose edges in an underlying graph G appear independently
  with some probability in our observed graph G' we describe how high a sam
 pling probability we need to infer the modularity of the underlying graph 
 from the modularity of the observed graph. \n\nJoint work with Colin McDia
 rmid.\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5108/3/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alan Frieze (Carnegie Mellon University\, USA)
DTSTART:20210809T153000Z
DTEND:20210809T155500Z
DTSTAMP:20260404T041839Z
UID:BIRS-21w5108/4
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/BIRS-
 21w5108/4/">Spanners in randomly weighted graphs</a>\nby Alan Frieze (Carn
 egie Mellon University\, USA) as part of BIRS workshop: Random Graphs and 
 Statistical Inference: New Methods and Applications\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5108/4/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Subhabrata Sen (Harvard)
DTSTART:20210809T160000Z
DTEND:20210809T162500Z
DTSTAMP:20260404T041839Z
UID:BIRS-21w5108/5
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/BIRS-
 21w5108/5/">Large deviations for dense random graphs: beyond mean-field</a
 >\nby Subhabrata Sen (Harvard) as part of BIRS workshop: Random Graphs and
  Statistical Inference: New Methods and Applications\n\n\nAbstract\nIn a s
 eminal paper\, Chatterjee and Varadhan derived an LDP for the dense\nErd˝
 os-R´enyi random graph\, viewed as a random graphon. This directly provid
 es LDPs for continuous functionals such as subgraph counts\, spectral norm
 s\,\netc. In contrast\, very little is understood about this problem if th
 e underlying\nrandom graph is inhomogeneous or constrained.\nIn this talk\
 , we will explore large deviations for dense random graphs\, beyond the 
 “mean-field” setting. In particular\, we will study large deviations f
 or\nuniform random graphs with given degrees\, and a family of dense block
  model\nrandom graphs. We will establish the LDP in each case\, and identi
 fy the rate\nfunction. In the block model setting\, we will use this LDP t
 o study the upper\ntail problem for homomorphism densities of regular sub-
 graphs. Our results\nestablish that this problem exhibits a symmetry/symme
 try-breaking transition\,\nsimilar to one observed for Erd˝os-R´enyi ran
 dom graphs.\nBased on joint works with Christian Borgs\, Jennifer Chayes\,
  Souvik Dhara\,\nJulia Gaudio and Samantha Petti\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5108/5/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Po-Ling Loh (University of Cambridge)
DTSTART:20210810T130000Z
DTEND:20210810T135000Z
DTSTAMP:20260404T041839Z
UID:BIRS-21w5108/6
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/BIRS-
 21w5108/6/">Optimal rates for community estimation in the weighted stochas
 tic block model</a>\nby Po-Ling Loh (University of Cambridge) as part of B
 IRS workshop: Random Graphs and Statistical Inference: New Methods and App
 lications\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5108/6/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Anna Paola Muntoni (Politecnico di Torino)
DTSTART:20210810T141500Z
DTEND:20210810T144000Z
DTSTAMP:20260404T041839Z
UID:BIRS-21w5108/7
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/BIRS-
 21w5108/7/">Epidemic mitigation by statistical inference from contact trac
 ing data</a>\nby Anna Paola Muntoni (Politecnico di Torino) as part of BIR
 S workshop: Random Graphs and Statistical Inference: New Methods and Appli
 cations\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5108/7/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Markus Heydenreich (LMU Munich)
DTSTART:20210810T144500Z
DTEND:20210810T151000Z
DTSTAMP:20260404T041839Z
UID:BIRS-21w5108/8
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/BIRS-
 21w5108/8/">Distances in Scale-free percolation</a>\nby Markus Heydenreich
  (LMU Munich) as part of BIRS workshop: Random Graphs and Statistical Infe
 rence: New Methods and Applications\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5108/8/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jean Ravelomanana (Goethe University Frankfurt)
DTSTART:20210810T153000Z
DTEND:20210810T155500Z
DTSTAMP:20260404T041839Z
UID:BIRS-21w5108/9
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/BIRS-
 21w5108/9/">The Sparse Parity Matrix</a>\nby Jean Ravelomanana (Goethe Uni
 versity Frankfurt) as part of BIRS workshop: Random Graphs and Statistical
  Inference: New Methods and Applications\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5108/9/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mark Sellke (Stanford)
DTSTART:20210810T160000Z
DTEND:20210810T162500Z
DTSTAMP:20260404T041839Z
UID:BIRS-21w5108/10
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/BIRS-
 21w5108/10/">Algorithmic pure states for the negative spherical perceptron
 </a>\nby Mark Sellke (Stanford) as part of BIRS workshop: Random Graphs an
 d Statistical Inference: New Methods and Applications\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5108/10/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jean Barbier (ICTP)
DTSTART:20210811T150000Z
DTEND:20210811T155000Z
DTSTAMP:20260404T041839Z
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://stable.researchseminars.org/talk/BIRS-21w5108/11/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Cecilia Holmgren (Uppsala University)
DTSTART:20210811T161000Z
DTEND:20210811T163500Z
DTSTAMP:20260404T041839Z
UID:BIRS-21w5108/12
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/BIRS-
 21w5108/12/">The asymptotic distribution of cluster sizes for supercritica
 l percolation on random split trees</a>\nby Cecilia Holmgren (Uppsala Univ
 ersity) as part of BIRS workshop: Random Graphs and Statistical Inference:
  New Methods and Applications\n\n\nAbstract\nWe consider the model of rand
 om trees introduced by\n Devroye (1998)\, the so-called random split trees
 . The model\n encompasses many important randomized algorithms and data\n 
 structures. We then perform supercritical Bernoulli\n bond-percolation on 
 those trees and obtain the asymptotic\n distribution for the sizes of the 
 largest clusters.\nJoint work with Gabriel Berzunza\,\n University of Live
 rpool\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5108/12/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Joshua Erde (TU Graz)
DTSTART:20210811T164000Z
DTEND:20210811T170500Z
DTSTAMP:20260404T041839Z
UID:BIRS-21w5108/13
DESCRIPTION:Title: <a href="https://stable.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 
 Statistical Inference: New Methods and Applications\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5108/13/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ilias Zadik (New York University)
DTSTART:20210811T172000Z
DTEND:20210811T174500Z
DTSTAMP:20260404T041839Z
UID:BIRS-21w5108/14
DESCRIPTION:Title: <a href="https://stable.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
  Applications\n\n\nAbstract\nIn this talk\, we discuss the prototypical in
 ference setting of noiseless phase retrieval under (real) standard Gaussia
 n feature vectors. Albeit a long line of work\, this inference setting exh
 ibits a computational-statistical gap where while  (1+o(1))d samples are s
 ufficient for recovery of the hidden d-dimensional vector\, the best-known
  polynomial-time algorithm achieving recovery (a variant of approximate me
 ssage passing) requires approximately 1.12d samples. In this work\, we pre
 sent a novel polynomial-time algorithm that provably works with access to 
 only d+1 samples\, and therefore closes the computational-statistical gap 
 for this noiseless model. Our proposed successful algorithm is based on a 
 potentially surprising use of the celebrated Lenstra-Lenstra-Lovasz lattic
 e basis reduction algorithm. \n\nThis is joint work with Min Jae Song and 
 Joan Bruna.\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5108/14/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Guangyan Zhou (Beijing Technology and Business University)
DTSTART:20210812T120000Z
DTEND:20210812T122500Z
DTSTAMP:20260404T041839Z
UID:BIRS-21w5108/15
DESCRIPTION:Title: <a href="https://stable.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 Busine
 ss University) as part of BIRS workshop: Random Graphs and Statistical Inf
 erence: New Methods and Applications\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5108/15/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Max Hahn-Klimroth (Goethe University Frankfurt)
DTSTART:20210812T123000Z
DTEND:20210812T125500Z
DTSTAMP:20260404T041839Z
UID:BIRS-21w5108/16
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/BIRS-
 21w5108/16/">ALMOST OPTIMAL EFFICIENT DECODING FROM SPARSE POOLED DATA</a>
 \nby Max Hahn-Klimroth (Goethe University Frankfurt) as part of BIRS works
 hop: Random Graphs and Statistical Inference: New Methods and Applications
 \n\n\nAbstract\nIn the pooled data problem\, one tries to recover a signal
  x ∈{0\, 1\, 2\, . . . \,d}^n from a measurement matrix A and the result
 s of joint measurements Ax=y. It is therefore a special case of the famous
  compressed sensing problem with a discrete signal and a generalisation of
  the frequently studied quantitative group testing problem (d=1). The task
  becomes explicitly interesting if the signal is sparse (||x||_0=k << n). 
 It is a well known fact that there are exponential time constructions to r
 ecover x from (A\,y) with no more than O(k) measurements but all known eff
 icient (polynomial time) constructions require at least Ω(k ln(n)) measu
 rements and it was believed that closing this gap is hard. We show that th
 is additional ln(n) factor is actually artificial by providing a randomise
 d efficient construction A_{SC} coming with an efficient decoding algorith
 m that recovers x from (A_{SC}\,y) with high probability with no more than
  O(k) measurements. This is based on joint work with Noela Müller.\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5108/16/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Oliver Cooley (Graz University of Technology)
DTSTART:20210812T143000Z
DTEND:20210812T145500Z
DTSTAMP:20260404T041839Z
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://stable.researchseminars.org/talk/BIRS-21w5108/17/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alex Wein (NYU)
DTSTART:20210812T150000Z
DTEND:20210812T152500Z
DTSTAMP:20260404T041839Z
UID:BIRS-21w5108/18
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/BIRS-
 21w5108/18/">Low-Degree Hardness of Maximum Independent Set</a>\nby Alex W
 ein (NYU) as part of BIRS workshop: Random Graphs and Statistical Inferenc
 e: New Methods and Applications\n\n\nAbstract\nIn high-dimensional statist
 ical problems (including planted clique\, sparse PCA\, community detection
 \, etc.)\, the class of "low-degree polynomial algorithms" captures many l
 eading algorithmic paradigms such as spectral methods\, approximate messag
 e passing\, and local algorithms on sparse graphs. As such\, lower bounds 
 against low-degree algorithms constitute concrete evidence for average-cas
 e hardness of statistical problems. This method has been widely successful
  at explaining and predicting statistical-to-computational gaps in these s
 ettings.\n\nWhile prior work has understood the power of low-degree algori
 thms for problems with a "planted" signal\, we consider here the setting o
 f "random optimization problems" (with no planted signal)\, including the 
 problem of finding a large independent set in a sparse random graph\, as w
 ell as the problem of optimizing the Hamiltonian of mean-field spin glass 
 models. Focusing on the independent set problem\, we show that low-degree 
 algorithms can find independent sets of "half-optimal" size (log d/d)n but
  no larger\, which explains the failure of all known poly-time algorithms 
 beyond this threshold. The proof of the lower bound leverages stability pr
 operties of low-degree polynomials along with a variant of the so-called "
 ensemble multi-overlap gap property"\, which is a structural property of t
 he solution space.\n\nBased on arXiv:2004.12063 (joint with David Gamarnik
  and Aukosh Jagannath) and arXiv:2010.06563\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5108/18/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Shuangping Li (Princeton University)
DTSTART:20210812T153000Z
DTEND:20210812T155500Z
DTSTAMP:20260404T041839Z
UID:BIRS-21w5108/19
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/BIRS-
 21w5108/19/">Proof of the Contiguity Conjecture and Lognormal Limit for th
 e Symmetric Perceptron</a>\nby Shuangping Li (Princeton University) as par
 t of BIRS workshop: Random Graphs and Statistical Inference: New Methods a
 nd Applications\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5108/19/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Afonso Bandeira (ETH Zurich)
DTSTART:20210813T130000Z
DTEND:20210813T135000Z
DTSTAMP:20260404T041839Z
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://stable.researchseminars.org/talk/BIRS-21w5108/20/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matthew Aldridge (University of Leeds)
DTSTART:20210813T141500Z
DTEND:20210813T144000Z
DTSTAMP:20260404T041839Z
UID:BIRS-21w5108/21
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/BIRS-
 21w5108/21/">Three random graph designs for group testing</a>\nby Matthew 
 Aldridge (University of Leeds) as part of BIRS workshop: Random Graphs and
  Statistical Inference: New Methods and Applications\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5108/21/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Noela Muelle (TU Eindhoven)
DTSTART:20210813T144500Z
DTEND:20210813T151000Z
DTSTAMP:20260404T041839Z
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://stable.researchseminars.org/talk/BIRS-21w5108/22/
END:VEVENT
END:VCALENDAR