Performance of Gaussian Boson Sampling on Planted Bipartite Clique Detection
Performance of Gaussian Boson Sampling on Planted Bipartite Clique Detection
Date: December 15, 2025
Speaker:
Inria
Gaussian Boson sampling is a comparatively easy-to-engineer quantum computing approach. It has been considered notably to solve graph estimation problems such as detection of dense subgraphs. In this talk we report our findings on the limitations of Gaussian Boson sampling for achieving quantum advantage on the so-called planted biclique detection problem.
Laurent Massoulié is a research scientist at Inria, scientific director of the Paris Inria Centre and professor at the Applied Maths Centre of Ecole Polytechnique. His research interests are in machine learning, probabilistic modelling and algorithms for networks. He has held research scientist positions at: France Telecom, Microsoft Research, Thomson-Technicolor, where he headed the Paris Research Lab. He obtained best paper awards at IEEE INFOCOM 1999, ACM SIGMETRICS 2005, ACM CoNEXT 2007, NeurIPS 2018, NeurIPS 2021, was elected "Technicolor Fellow" in 2011, received the "Grand Prix Scientifique" of the Del Duca Foundation delivered by the French Academy of Science in 2017, is a Fellow of the "Prairie" Institute and received the ACM Sigmetrics achievement award in 2023.
Date: December 1, 2025
Speaker:
Northwestern University
In parallel-server systems with a single stream of arrivals, Join-the-Shortest-Queue (JSQ) is one of the most popular routing algorithms due to its simplicity and strong performance properties: it is well known that routing with JSQ is throughput and heavy-traffic optimal, regardless of whether the servers are homogeneous or not. Further, JSQ is optimal and does not need any information about the servers' rates. In this work, we study a JSQ system with Markov-modulated arrival and service rates. Specifically, we provide sufficient conditions on the Markov-modulated arrival and service rates to ensure state space collapse, and compute the heavy-traffic distribution of queue lengths. We establish the distribution of queue lengths using a novel hybrid methodology that combines the Transform Method for queue-lengths analysis, and Poisson Equation of the Markov-modulating chain.
Daniela is an Assistant Professor in the Operations department at the Kellogg School of Management at Northwestern University. She received her Ph.D. in Operations Research at Georgia Tech in December 2021, and was supervised by Prof. Siva Theja Maguluri. Before joining Kellogg, she spent 1.5 years as an Assistant professor of Mathematics at William & Mary. Her research interests are performance analysis of Stochastic Processing Networks and applied probability.
Date: November 24, 2025
Speaker:
Georgia Institute of Technology
Some widely-used machine learning algorithms have demonstrated great empirical success, yet often lacking rigorous theoretical justification. In our work, we studied two such algorithms: momentum stochastic gradient descent, and natural policy gradient with the reuse of historical trajectories. By continuous-time approximation of the algorithmic iterations and analysis of the resulting ODEs and SDEs, we investigated theoretical convergence properties of these algorithms, offering insights and justification for their empirical behaviors. Our analysis also inspired new improvements to these existing algorithms.
Enlu Zhou is a Fouts Family Professor in the H. Milton Stewart School of Industrial and Systems Engineering at Georgia Tech. She received the B.S. degree with highest honors in electrical engineering from Zhejiang University, China, and the Ph.D. degree in electrical engineering from the University of Maryland, College Park. Prior to joining Georgia Tech, she was an assistant professor in the Industrial & Enterprise Systems Engineering Department at the University of Illinois Urbana-Champaign. She is a recipient of the Best Theoretical Paper award at the Winter Simulation Conference, AFOSR Young Investigator award, NSF CAREER award, and INFORMS Outstanding Simulation Publication Award. She has been on the editorial board of Journal of Simulation, IEEE Transactions on Automatic Control, Operations Research, and SIAM Journal on Optimization. She is currently a co-Editor-in-Chief for Journal of Simulation. She is the President of the INFORMS Simulation Society from 2024 to 2026. Her research interests lie in theory, methods, and applications of simulation, stochastic optimization, and stochastic control.
Date: November 17, 2025
Speaker:
Universitat Pompeu Fabra
Large networks that change dynamically over time are ubiquitous in various areas, such as social networks and epidemiology. These networks are often modeled by random dynamics, which, despite being relatively simple, give a quite accurate macroscopic description of real networks. "Network archaeology" is an area of combinatorial statistics in which one studies statistical problems of inferring the past properties of such growing networks based on present-day observations. In this talk, we review some simple models and recent results.
Gabor Lugosi is an ICREA research professor at the Department of Economics, Pompeu Fabra University, Barcelona. His main research interests include the theory of machine learning, combinatorial statistics, inequalities in probability, random graphs and random structures, and information theory.
Date: November 10, 2025
Speaker:
Stanford University
Modern service systems are increasingly adopting new modalities enabled by emerging technologies, such as AI-assisted services, to better balance quality and efficiency. Motivated by this trend, we study dynamic service mode control in a single-server queue with two switchable modes, each with a distinct service rate and an unknown reward distribution. The objective is to maximize the long-run average of expected cumulative rewards minus holding costs achievable under non-anticipating, state-dependent policies. To address the problem, we first establish the optimality of a threshold policy under full information of the problem primitives. When reward distributions are unknown but samples are observable, we propose an online learning algorithm that uses Upper Confidence Bound (UCB) estimates of the unknown parameters to adaptively learn the optimal threshold. Our algorithm achieves statistically near-optimal regret of and demonstrates strong numerical performance. Additionally, when additional partial information about the optimal policy is available ex ante (specifically, a non-trivial lower bound on the optimal threshold), we show that an episodic greedy policy achieves constant regret by leveraging a free-exploration property intrinsic to this special setting. Methodologically, we develop a novel regret decomposition and regenerative cycle-based analysis, offering general tools for learning-based queueing control. Lastly, we conduct a healthcare case study on AI-assisted patient messaging demonstrating the practical utility of our approach.
Yue Hu is an Assistant Professor of Operations, Information & Technology at Stanford Graduate School of Business. Her research lies at the intersection of healthcare operations management and applied probability. With particular focus on scheduling, staffing, and patient-flow management in healthcare delivery systems, she studies how to leverage predictive analytics to guide operational strategies and innovations. In addition to solving practically relevant problems, she conducts research in developing new methodologies for the approximation and control of stochastic systems. Hu’s research has been recognized in a number of competitions, including as the finalist of the 2022 INFORMS Doing Good with Good OR Competition, winner of the 2020 INFORMS APS Best Student Paper Award, finalist of the 2019 INFORMS IBM Best Student Paper Award, and honorable mention in the 2017 INFORMS Undergraduate Operations Research Prize. Hu received her PhD from the Decision, Risk and Operations Division at the Graduate School of Business, Columbia University. Prior to pursuing her PhD, she received a BS from the Department of Industrial Engineering and Management Sciences at Northwestern University.
Date: November 3, 2025
Speaker:
ENSAE
Prophet inequalities is a standard stopping time question where a decision maker observes sequentially random variables and decides when to stop, in the hope of maximizing the value of the selected variable. There is an extensive literature on the subject, proving some "optimality" of different procedures in the worst-case scenario. We claim, and prove, that those results can be strikingly improved when considering non-pathological distributions. This is illustrated in two directions: by introducing a parameter that characterizes the complexity of an instance or by looking at some slightly weaker benchmarks that strongly impact the performances of the oracle that knows in advance all the realized values.
Vianney Perchet is a professor at the Centre de recherche en économie et statistique (CREST) at the ENSAE since october 2019. Mainly focusing on the interplay between machine learning and game theory, his research themes are at the intersection of mathematics, computer science, and economics. The spectrum of his interest ranges from pure theory (say, optimal rates of convergence of algorithms) to pure applications (modeling user behavior, optimisation of recommender systems, etc.) He is also part-time distinguished researcher in the Criteo AI Lab, in Paris, working on efficient exploration in recommender systems.
Date: October 20, 2025
Speaker:
University of Warwick
The talk introduces two new classes of ultra-sharp bounds in queueing systems. The first is specific to the G/G/1 queue, with possibly correlated inter-arrivals; the main result is an exact expression for the distribution of the delay in terms of a series, whose terms are subject to elementary integration. Remarkably, the first few terms are sufficient to render ultra-sharp bounds improving upon state-of-the-art bounds by orders of magnitude. The second new class of bounds is specific to a tandem queueing network with general (i.e., not necessarily Poisson) arrivals and light-tailed service times. Besides showing for the first time that the end-to-end delay distribution is subject to a polynomial-exponential structure, explicit bounds computed in some special cases are shown to improve upon state-of-the-art results by many orders of magnitude.
Florin Ciucu is a Professor in the CS Department at the University of Warwick. His research interests are in the stochastic analysis of communication networks and the non-asymptotic analysis of stochastic bandits. He co-chaired ACM Sigmetrics 2024 and served on the Technical Program Committees of several other top conferences; currently he is on the Editorial Boards of the Performance Evaluation Journal and IEEE Transactions on Networking. Florin is a recipient of the ACM Sigmetrics 2005 Best Student Paper Award and IFIP Performance 2014 Best Paper Award.
Date: September 29, 2025
Speaker:
Duke University
Motivated by mass emergencies such as pandemics and earthquakes that result in a large number of patients requiring critical services, we study a feature-based scheduling problem with N patients waiting to be served by a decision maker. The decision maker knows each patient's features and waiting cost, but does not know how the expected service time depends on the patient features. After a patient is served, the decision maker observes the realized service time and determines which patient to serve next. We prove that the decision maker's expected regret, i.e., the difference between the expected total waiting cost of the decision maker and that of a clairvoyant who knows the patients' expected service times, is at least of order N^{3/2}. We then design a learn-then-commit policy and an uncertainty ellipsoid policy to dynamically learn the expected service times, and prove that the expected regrets of these two policies are of order N^{5/3} log^{1/2} N and N^{3/2} log^{3/2} N, respectively. Finally, we conduct simulation experiments and a case study based on real-world data from Duke University Hospital to demonstrate the practical value of our policies relative to commonly used approaches. (Paper available at SSRN: https://ssrn.com/abstract=4852356)
Bora Keskin is an Associate Professor of Operations Management at Duke University’s Fuqua School of Business. His research focuses on data-driven decision making under uncertainty, with applications in dynamic pricing, revenue management, platform operations, and supply chain innovation. His recent work explores how emerging technologies—such as blockchain, IoT, and AI—are reshaping the future of operations. Bora received his Ph.D. from Stanford University. His work has been recognized with several awards, including the Lanchester Prize (2019) and the MSOM Young Scholar Prize (2024). Prior to joining Duke in 2015, he worked as a consultant at McKinsey & Company and served on the faculty of the University of Chicago Booth School of Business. At Fuqua, Bora teaches the MBA elective Value Chain Innovation in Business Processes, which emphasizes technological change and data-driven practices. He also teaches a Ph.D. course on revenue management and pricing. Outside Duke, he serves as an Associate Editor for Management Science and Operations Research, and as a Senior Editor for Production and Operations Management.