About me
I am an associate professor in the Fuqua School of Business at
Duke University.
I received BE (09) from Tsinghua University, MS (11) from UTAustin, and PhD (14) from UIUC, all in Electrical and Computer Engineering.
I was fortunate to have Prof. Bruce Hajek as my PhD adviser.
My thesis "Statistical inference in networks: fundamental limits and efficient algorithms" is available here.
arXiv preprints
Google scholar page
Research Interests
My research and teaching interests are on the interface of operation research, artificial intelligence, and data analytics.
My work spans data analysis, algorithms design, and performance evaluation in largescale networks and
stochastic systems with applications drawn from business, engineering, and natural sciences.
I am developing a fundamental understanding and powerful methodologies for inferring information from data to enable downstream datadriven decisionmaking at scale. I am also designing new models and algorithms for improving decisionmaking efficiency under uncertainties and various resource constraints and addressing emerging privacy and security issues.
 Network science
 Highdimensional statistics
 Artificial Intelligence
 Security and privacy
 Optimization
 Information theory
 Queueing games
 Mean field theory
 Communications and networking
Grants
NSF CAREER Award, Federated Learning: Statistical Optimality and Provable Security
NSF CIF: Medium: Collaborative Research: Learning in Networks: Performance Limits and Algorithms
NSF BIGDATA: F: Collaborative Research: Mining for Patterns in Graphs and HighDimensional Data: Achieving the Limits
NSF CRII: CIF: Learning Hidden Structures in Networks: Fundamental Limits and Efficient Algorithms
Students
Sophie H. Yu (Assistant Professor, The Wharton School)
Hanjing Zhu (Researcher, Amazon)
Liren Yu (Researcher, Huawei)
Zhiyi Tian (Data Scientist, IQVIA)
Postdocs
Xiaochun Niu
Dana Yang (Assistant Professor, Cornell Statistics and Data Science)
Code
Convexified Modularity Maximization for Community Detection
Degree Profile for Graph Matching
GRAph Matching by Pairwise eigenAlignments (GRAMPA)
Preprints
 I. Keskin, and J. Xu
LearnerPrivate Convex Optimization with Bandit Feedback, March 2024
 L. Lufkin, Y. Wu, and J. Xu
Sharp InformationTheoretic Thresholds for Shuffled Linear Regression
arXiv:2402.09693, Short version appeared in International Symposium on Information Theory, January 2024
[Video Presentation]
 L. Su, M. Xiang, J. Xu, and P. Yang
Federated Learning in the Presence of Adversarial Client Unavailability
arXiv:2305.19971, Feb. 2024
 Y. Wei, J. Xu, and S. H. Yu
Constant regret primaldual policy for multiway dynamic matching, Dec. 2023
[SLIDES]
 C. Mao, Y. Wu, J. Xu, and S. H. Yu
Random graph matching at Otter's threshold via counting chandeliers
Short version appeared in ACM Symposium on Theory of Computing (STOC), June 2023.
[SLIDES]
Book Chapters
Journal Publications
 L. Su, J. Xu, and P. Yang
Global Convergence of Federated Learning for Mixed Regression
To appear in IEEE Transactions on Information Theory, July 2024
[SLIDES]

C. Mao, Y. Wu, J. Xu, and S. H. Yu
Testing network correlation efficiently via counting trees
To appear in The Annals of Statistics, April 2024.
[SLIDES]
 J. Xu and H. Zhu
Overparametrized multilayer
neural networks: uniform concentration of neural tangent kernel and convergence of stochastic gradient descent
To appear in Journal of Machine Learning Research, April 2024
 Z. Tian, J. Xu, and J. Tang
Clustering highdimensional noisy categorical data
To appear in Journal of the American Statistical Association, January 2024
 J. Ding, Y. Wu, J. Xu, D. Yang
The planted matching problem: Sharp threshold and infiniteorder phase transition
Probability Theory and Related Fields, June 2023.
[SLIDES]
 L. Su, J. Xu, and P. Yang
A Nonparametric View of FedAvg and FedProx: Beyond Stationary Points
Journal of Machine Learning Research, May 2023.
[SLIDES]
 J. Xu, K. Xu, D. Yang
LearnerPrivate Online Convex Optimization
IEEE Transactions on Information Theory, January 2023.
 Z. Fan, C. Mao, Y. Wu, J. Xu
Spectral Graph Matching and Regularized Quadratic Relaxations I:
The Gaussian Model
Foundations of Computational Mathematics, June 2022.
[SLIDES]
 Z. Fan, C. Mao, Y. Wu, J. Xu
Spectral Graph Matching and Regularized Quadratic Relaxations II:
ErdősRényi Graphs and Universality
Foundations of Computational Mathematics, June 2022.
 Y. Wu, J. Xu, S. H. Yu
Testing correlation of unlabeled random graphs
The Annals of Applied Probability, 2023
[SLIDES]
 Y. Wu, J. Xu, S. H. Yu
Settling the Sharp Reconstruction Thresholds of Random Graph Matching
IEEE Transactions on Information Theory, August 2022.
 G. Reeves, J. Xu, I. Zadik
The AllorNothing Phenomenon in Sparse Linear Regression
Mathematical Statistics and Learning
 L. Yu, J. Xu, X. Lin
Graph Matching with PartiallyCorrect Seeds
The Journal of Machine Learning Research, October 2021
 L. Yu, J. Xu, X. Lin
The Power of Dhops in Matching PowerLaw Graphs
Proceedings of the ACM on Measurement and Analysis of Computing Systems,
June 2021
[SLIDES]
 J. Ding, Y. Wu, J. Xu, D. Yang
Consistent recovery threshold of hidden nearest neighbor graphs
IEEE Transactions on Information Theory, August 2021
 M. Moharrami, C. Moore, J. Xu
The Planted Matching Problem: Phase Transitions and Exact Results
Annals of Applied Probability, Dec. 2021
[SLIDES]
 J. Ding, Z. Ma, Y. Wu, and J. Xu
Efficient Random Graph Matching via Degree Profiles
Probability Theory and Related Fields, Feb. 2021
[SLIDES]
 W. Hsu, J. Xu, X. Lin, and M. Bell
Integrated Online Learning and Adaptive Control in Queueing Systems with Uncertain Payoffs
Operations Research, March 2021
[SLIDES]
 J. Xu and Y. Zhong
Improved queuesize scaling for inputqueued switches via graph factorization
Advances in Applied Probability, Volume 52, Issue 3, Sept. 2020, pp. 798  824.
[SLIDES]
 X. Li, Y. Chen, and J. Xu
Convex Relaxation Methods for Community Detection
Statistical Science, Vol. 36, No.1, Feb. 2021, pp. 215, arXiv:1810.00315
 E. Mossel and J. Xu
Seeded Graph Matching via Large Neighborhood Statistics
Random Structures & Algorithms, vol. 57, no. 3, pp. 570611
June 2020. arXiv:1807.10262.
[SLIDES]
 V. Bagaria, J. Ding, D. Tse, Y. Wu, and J. Xu
Hidden Hamiltonian Cycle Recovery via Linear Programming
Operations Research, vol. 68, no. 1, pp. 5370, Jan. 2020.
arXiv:1804.05436.
[SLIDES]
 L. Su and J. Xu
Securing Distributed Gradient Descent in High Dimensional Statistical Learning
Proceedings of the ACM on Measurement and Analysis of Computing Systems, March 2019.
 B. Hajek, Y. Wu, and J. Xu
Recovering a hidden community beyond the spectral limit in
O(E log* V ) time
Journal of Applied Probability, vol. 55, no. 2, pp. 325352, June 2018.
[SLIDES]
 Y. Chen, X. Li, and J. Xu
Convexified modularity maximization for degreecorrected stochastic block models
The Annals of Statistics, vol. 46, no. 4, pp. 15731602, June 2018.
[SLIDES]
[CODE]
 B. Hajek, Y. Wu, and J. Xu
Submatrix localization via message passing
The Journal of Machine Learning Research, vol. 18, no. 186, pp. 152, Apr. 2018.
[SLIDES]
 Y. Chen, L. Su, and J. Xu
Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent
Proceedings of the ACM on Measurement and Analysis of Computing Systems, Dec. 2017.
[SLIDES]
 J. Banks, C. Moore, R. Vershynin, and J. Xu
Informationtheoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization
IEEE Trans. Inf. Theory, vol. 67, no. 7, pp. 48724894, July 2017.
[SLIDES]
 B. Hajek, Y. Wu, and J. Xu
Information limits for recovering a hidden community
IEEE Trans. Inf. Theory, vol. 63, pp. 47294745, Aug. 2017.
[SLIDES]
 B. Hajek, Y. Wu, and J. Xu
Achieving exact cluster recovery threshold via semidefinite programming: Extensions
IEEE Trans. Inf. Theory, vol. 62, pp. 59185937, Oct. 2016.
[SLIDES]
 B. Hajek, Y. Wu, and J. Xu
Achieving exact cluster recovery threshold via semidefinite programming
IEEE Trans. Inf. Theory, vol. 62, pp. 27882797, May 2016.
[SLIDES]
 M. Lelarge, L. Massoulié, and J. Xu
Reconstruction in the labeled stochastic block model
IEEE Transactions on Network Science and Engineering, vol. 2, pp. 152163, Oct. 2015.
[SLIDES]
 Y. Chen and J. Xu
Statisticalcomputational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices
The Journal of Machine Learning Research, vol. 17, no. 1, pp. 882938, 2016.
[SLIDES]
 J. Xu and B. Hajek
The Supermarket game
Stochastic Systems, Vol. 3, No. 2, 405441, 2013.
[SLIDES]
 J. Xu, J. G. Andrews, and S. A. Jafar
MISO broadcast channels with delayed finiterate feedback: predict or observe?
IEEE Transactions on Wireless Communications, Apr. 2012.
 J. Xu, J. Zhang, and J. G. Andrews
On the accuracy of the Wyner model of cellular networks
IEEE Transactions on Wireless Communications, July 2011.
Conference Publications
 L. Yu, J. Xu, and X. Lin
SeedGNN: Graph Neural Networks for Supervised Seeded Graph Matching
The International Conference on Machine Learning (ICML), July 2023
 Y. Wei, J. Xu, and S. H. Yu
Constant regret primaldual policy for multiway
dynamic matching
ACM SIGMETRICS, June 2023
 L. Su, J. Xu, and P. Yang
Global Convergence of Federated Learning for Mixed Regression
Conference on Neural Information Processing Systems (NeurIPS), December 2022.
 H. Wang, Y. Wu, J. Xu, and I. Yolou
Random Graph Matching in Geometric Models: the Case of Complete Graphs
Conferencer on Learning Theory, July 2022.
 L. Yu, J. Xu, X. Lin
The Power of Dhops in Matching PowerLaw Graphs
Proceedings of ACM SIGMETRICS, 2021
 Y. Wu, J. Xu, S. H. Yu
Settling the Sharp Reconstruction Thresholds of Random Graph Matching
International Symposium on Information Theory (ISIT), 2021
 J. Xu, K. Xu, D. Yang
LearnerPrivate Online Convex Optimization
International Conference on Machine Learning (ICML), July 2021.
 J. Xu, K. Xu, D. Yang
Optimal query complexity for private sequential learning against eavesdropping
The 24th International Conference on
Artificial Intelligence and Statistics (AISTATS), Apr. 2021.
 J. Xu and H. Zhu
Onepass Stochastic Gradient Descent in overparametrized twolayer neural networks
The 24th International Conference on
Artificial Intelligence and Statistics (AISTATS), Apr. 2021
 Z. Fan, C. Mao, Y. Wu, J. Xu
SSpectral Graph Matching and Regularized Quadratic Relaxations: Algorithm and Theory
International Conference on Machine Learning (ICML), 2020.
 J. Ding, Y. Wu, J. Xu, D. Yang
Consistent recovery threshold of hidden nearest neighbor graphs
Conference on Learning Theory (COLT), 2020.
 G. Reeves, J. Xu, I. Zadik
The AllorNothing Phenomenon in Sparse Linear Regression
Conference on Learning Theory (COLT), June 2019.
 E. Mossel and J. Xu
Seeded Graph Matching via Large Neighborhood Statistics
ACMSIAM Symposium on Discrete Algorithms (SODA), Jan. 2019.
 J. Xu
Rates of convergence of spectral methods for graphon estimation
Prooceedings of International Conference on Machine Learning (ICML), July 2018.
[SLIDES]
 Y. Chen, L. Su, and J. Xu
Distributed statistical machine learning in adversarial settings: Byzantine gradient descent
Proceedings of ACM SIGMETRICS, 2018.
[SLIDES]
 J. Banks, C. Moore, N. Verzelen, R. Vershynin, and J. Xu
Informationtheoretic bounds and
phase transitions in clustering, sparse PCA, and submatrix localization
Proceedings of IEEE International Symposium on Information Theory (ISIT), June 2017.
 F. Krzakala, J. Xu, and L. Zdeborova
Mutual Information in RankOne Matrix Estimation
Information Theory Workshop (ITW), Sept. 2016.
[SLIDES]
 B. Hajek, Y. Wu, and J. Xu
Information limits for recovering a hidden community
International Symposium on Information Theory (ISIT), July 2016.
 B. Hajek, Y. Wu, and J. Xu
Semidefinite programs for exact recovery of a hidden community
Conference on Learning Theory (COLT), June 2016.
[SLIDES]
 E. Mossel and J.Xu
Density evolution in the degreecorrelated stochastic block model
Conference on Learning Theory (COLT), June 2016.
[SLIDES]
 E. Mossel and J. Xu
Local algorithms for block models with side information
7th Innovations in Theoretical Computer Science (ITCS), Jan. 2016.
 S. Oh, K. K. Thekumparampil, and J. Xu
Collaboratively learning preferences from ordinal data
Neural Information Processing Systems (NIPS), Dec. 2015.
 B. Hajek, Y. Wu, and J. Xu
Achieving exact cluster recovery threshold via semidefinite programming under the stochastic block model
Asilomar Conference on Signals, Systems, and Computers, Nov. 2015, invited.
[SLIDES]
 B. Hajek, Y. Wu, and J. Xu
Exact recovery threshold in the binary censored block model
Information Theory Workshop (ITW), Oct. 2015, invited.
[SLIDES]
 E. Mossel and J. Xu
On the optimality of local belief propagation under the degreecorrelated stochastic block model
Information Theory Workshop (ITW), Oct. 2015, invited.
[SLIDES]
 B. Hajek, Y. Wu, and J. Xu
Computational lower bounds for community detection on random graphs
Conference on Learning Theory (COLT), July 2015.
[SLIDES]
 B. Hajek, Y. Wu, and J. Xu
Achieving exact cluster recovery threshold via semidefinite programming
International Symposium on Information Theory (ISIT), June 2015, semiplenary talk.
[SLIDES]
 R. Wu, J. Xu, R. Srikant, L. Massoulié, M. Lelarge, and B. Hajek
Clustering and inference from pairwise comparisons
ACM SIGMETRICS, June 2015 (short paper).
 B. Hajek, S. Oh, and J. Xu
Minimaxoptimal inference from partial rankings
Neural Information Processing Systems (NIPS), Dec. 2014.
 M. Lelarge, L. Massoulié, and J. Xu
Edge label inference in generalized stochastic block model: from spectral theory to impossibility results
Conference on Learning Theory (COLT), June 2014.
 J. Xu, R. Wu, K. Zhu, B. Hajek, R. Srikant, and L. Ying
Jointly clustering rows and columns of binary matrices: algorithms and tradeoffs
ACM SIGMETRICS, June 2014.
[SLIDES]
 Y. Chen and J. Xu
Statisticalcomputational phase transitions in planted models: the highdimensional setting
International Conference on Machine Learning (ICML), June 2014.
 M. Lelarge, L. Massoulié, and J. Xu
Reconstruction in the labeled stochastic block model
Information Theory Workshop (ITW), Sept. 2013.
[SLIDES]
 J. Xu and B. Hajek
The supermarket game
International Symposium on Information Theory (ISIT), July 2012.
[SLIDES]
Thesis
 Jiaming Xu
Statistical inference in networks: fundamental limits and efficient algorithms
Doctoral Dissertation, University of Illinois, Dec. 2014.
My research interests are in the broad area of stochastic systems with emphasis on large scale distributed networks and highdimensional data analysis.
Given a pair of graphs, the problem of graph matching or network alignment refers to finding a
bijection between the vertex sets so that the edge sets are maximally aligned.
This is a ubiquitous problem arising in a variety of applications, including network
deanonymization, pattern recognition, and computational biology.
Finding the best matching between two graphs can be cast as a quadratic assignment problem,
which is NPhard to solve or to approximate in the worst case.
I have been working on the averagecase analysis of graph matchings
where the two graphs are randomly generated.
 Graph matching via degree profiles

Despite the worstcase intractability of graph matching, we develop a nearly lineartime algorithm which perfectly recovers the true vertex correspondence with high probability, provided that the average degree is at least polylog(n) and the two graphs differ by at most 1/polylog(n) fraction of edges. The methodology is based on appropriately chosen distance statistics of the degree profiles (empirical distribution of the degrees of neighbors).
Paper:
J. Ding, Z. Ma, Y. Wu, and J. Xu
Efficient Random Graph Matching via Degree Profiles
arXiv:1811.07821, Nov. 2018.
[SLIDES]

 Spectral graph matching and regularized quadratic relaxations

We develop a new spectral method,
which computes eigendecomposition of the two graph adjacency matrices and returns a matching based on the pairwise alignments between all eigenvectors of the first graph with all eigenvectors of the second.
This spectral method can be equivalently viewed as solving a regularized quadratic programming relaxation of the quadratic assignment problem.
We show that this method can return the exact matching with high probability, provided that the average degree is at least polylog(n) and the two graphs differ by at most a 1/polylog(n) fraction of edges. Our analysis exploits local laws for the resolvents of sparse Wigner matrices.
Papers:
Z. Fan, C. Mao, Y. Wu, J. Xu
Spectral Graph Matching and Regularized Quadratic Relaxations I:
The Gaussian Model
arXiv:1907.08880, July 2019.
[SLIDES]
Z. Fan, C. Mao, Y. Wu, J. Xu
Spectral Graph Matching and Regularized Quadratic Relaxations II:
ErdősRényi Graphs and Universality
arXiv:1907.08883, July 2019.

 Seeded graph matching via large neighborhood statistics

We consider a seeded graph matching problem, where an initial seed set of correctly matched vertex
pairs is revealed as side information. We show that it is possible to achieve the information theoretic limit
of graph sparsity in polynomialtime with n^{eps} seeds. Our algorithm matches vertices
if their large neighborhoods have a significant overlap in the number of seeds.
Paper:
E. Mossel and J. Xu
Seeded Graph Matching via Large Neighborhood Statistics
arXiv:1807.10262, July 2018.
[SLIDES]

Community detection in networks
In many modern systems, e.g. recommender systems, similar objects form hidden clusters and we are interested in recovering the clusters based on observation of pairwise interactions among objects. The data of pairwise interactions can be viewed as a graph consisting of nodes representing objects and edge connections encoding pairwise interactions, and the cluster recovery problem is called community detection, a.k.a. graph clustering.
I have been working on developing optimal, fast, and robust community detection algorithms, and characterizing the fundamental limits for community detection.
 Community detection via message passing


Finding small communities in networks is a notoriously hard problem. We show that a single community can be
found in nearly linear time via the belief propagation algorithm in log*(n) iterations if and only if the suitably defined signaltonoise ratio λ>1/e, while a linear message passing algorithm finds the single community in loglog(n) iterations
if and only if λ>1.
Papers:
B. Hajek, Y. Wu, and J. Xu
Submatrix localization via message passing
The Journal of Machine Learning Research, Apr. 2018.
[SLIDES]
B. Hajek, Y. Wu, and J. Xu
Recovering a hidden community beyond the KestenStigum Threshold in
Journal of Applied Probability, June 2018.
[SLIDES]

 Community detection via SDP relaxations

The solid curves show the recovery threshold for a single community of size ρn for three values of ρ.
The two dashed curves correspond to the recovery threshold for two equalsized clusters

We show that a semidefinite programming (SDP) relaxation of the maximum likelihood estimator can
achieve the sharp threshold for exactly recovering the community structure if and only if the community size is above a certain threshold depending on the network size.
Papers:
B. Hajek, Y. Wu, and J. Xu
Semidefinite programs for exact recovery of a hidden community
Conference on Learning Theory (COLT), June 2016.
[SLIDES]
B. Hajek, Y. Wu, and J. Xu
Achieving exact cluster recovery threshold via semidefinite programming: Extensions IEEE Transactions on Information Theory. Oct. 2016.
[SLIDES]
B. Hajek, Y. Wu, and J. Xu
Achieving exact cluster recovery threshold via semidefinite programming
IEEE Transactions on Information Theory, May 2016.
[SLIDES]

 Community detection with degree corrections

The facebook friendship network formed by students at Caltech. Nodes are colored according to the clustering result of convexified modularity maximization.
The 8 clusters found roughly correspond to the 8 dorms at Caltech.

In realworld networks, the degree distributions are often highly inhomogeneous across nodes, sometimes exhibiting a heavy tail behavior with some nodes having very
high degrees (socalled hubs), and some nodes having very small degrees. We introduce a new approach based on a convexification of modularity maximization followed by weighted kmedian clustering, and show that our approach improves upon the stateoftheart both theoretically and empirically.
Paper:
Y. Chen, X. Li, and J. Xu
Convexified modularity maximization for degreecorrected stochastic block models
The Annals of Statistics,June 2018.
[SLIDES]
[CODE]

 Fundamental limits for community detection

(1) The impossible regime, where all algorithms fail; (2) the hard
regime, where the computationally intractable Maximum Likelihood Estimator (MLE) succeeds;
(3) the easy regime, where a convex relaxation of MLE succeeds; (4) the simple regime,
where a simple counting/thresholding procedure succeeds.

We study the fundamental limits of community detection under the stochastic block model. In its simplest form, it consists of n nodes with r K of them partitioned into r clusters of equal size K and the remaining nr K nodes not in any cluster; each pair of two nodes is connected independently by an edge with probability p if they are in the same cluster and q otherwise. Given a graph generated as above, the goal is to exactly recover the clusters with high probability as n goes to the infinity. In the case with more than one cluster, we show that the space of the model parameters can be partitioned into four disjoint regions in decreasing order of statistical and computational complexities.
Papers:
Y. Chen and J. Xu
Statisticalcomputational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices
The Journal of Machine Learning Research, 2016..
[SLIDES]
B. Hajek, Y. Wu, and J. Xu
Computational lower bounds for community detection on
random graphs
Conference on Learning Theory (COLT), July 2015.
[SLIDES]
B. Hajek, Y. Wu, and J. Xu
Information limits for recovering a hidden community
IEEE Trans. Inf. Theory, vol. 63, pp. 47294745, Aug. 2017.
[SLIDES]

Learning user preferences
Recommender systems sort through massive amounts of data to identify potential user preferences. They have been applied in a variety of applications, including personalized advertisement, online learning, and targeted marketing.
I have been working on developing and analyzing optimal and fast algorithms for predicting users' inherent preferences
from noisy and partial rating or ranking data.
 Rating predictions: algorithms and limits


When explicit user ratings are available, there are three popular approaches: (1) nearest neighbor (NN); (2) spectral method (3) convex method. We performed a theoretical analysis of these three methods assuming both users and items exhibit cluster structure. We find that the simple NN method outperforms the other two more sophisticated ones for small cluster sizes if there are abundant observations.
Papers:
J. Xu, R. Wu, K. Zhu, B. Hajek, R. Srikant, and L. Ying
Jointly clustering rows and columns of binary matrices:
algorithms and tradeoffs
ACM SIGMETRICS, June 2014.
[SLIDES]
M. Lelarge, L. Massoulié, and J. Xu
Edge label inference in generalized stochastic block model: from spectral theory to impossibility results
Conference on Learning Theory (COLT), June 2014.

 Inferring preferences from partial rankings


When only partial rankings are available, little is known about how to learn the individual preferences efficiently, and what is the sample complexity to reach a prescribed estimation accuracy. Our main results revealed important insight on this issue: (1) we propose a clustering and ranking algorithm, which is shown to be orderoptimal in sample complexity; (2) we show the estimation error depends on the spectral gap of a comparison graph and the random assignment of items to users is orderoptimal among all schemes.
Papers:
B. Hajek, S. Oh, and J. Xu
Minimaxoptimal inference from partial rankings
Neural Information Processing Systems (NIPS), Dec. 2014.
R. Wu, J. Xu, R. Srikant, L. Massoulié, M. Lelarge, and B. Hajek
Clustering and inference from pairwise comparisons
ACM SIGMETRICS, June 2015 (short paper).
S. Oh, K. K. Thekumparampil, and J. Xu
Collaboratively learning preferences from ordinal data
Neural Information Processing Systems (NIPS), Dec. 2015.

The supermarket game
Imagine being a customer in a supermarket where there is a large number of checkout counters, and the queue at each counter is only seen locally. With the goal of minimizing the sum of the waiting cost and the searching cost, how many counters would you prefer to check?
The above example reflects the spirit of my work on investigating the impact of customers'
strategic behavior in queueing systems. The problem described in the example is known as the
distributed load balancing problem, and it appears in a diverse set of applications such as network
routing, dynamic wireless spectrum access, and cloud computing services.

We propose a supermarket game model and study it in the large system regime using mean
field theory. By assuming Poisson arrival with rate λ and exponential service with unit rate, we show that there always exists a Nash equilibrium for λ < 1 and the Nash equilibrium is unique for λ <=1/sqrt(2).
Paper:
J. Xu and B. Hajek
The Supermarket game
Stochastic Systems, Vol. 3, No. 2, 405441, 2013.
[SLIDES]

Instructor

BA 990.03: Statistical Inference on Graphs, Duke, Spring 2020, 2022.

Decision 546Q: Modern Analytics, Duke, Fall 2023.

Decision 611: Decision Models, Duke, Spring 2023.

Decision 611W: Decision Models, Duke, Summer 2022.

Decision 521Q: Decision Analytics and Modeling, Duke, Spring 2019, 2020, 2021

MGMT 472: Advanced Spreadsheet Modeling
and Simulation, Purdue, Fall 2017.

MGMT 306: Management Science, Purdue, Spring and Fall 2017.

MGMT 690: PhD seminar in Analytics: Topics in Highdimensional Data Analysis, Purdue, Fall 2016.

ECE313: Probability with Engineering Applications, UIUC, Summer 2014.
Invited Seminars and Talks

A new primaldual algorithm for dynamic matching
Fuqua Seminar Series, Duke University, July 2024

Recent advances on random graph matching
Stochastic Networks Conference, Stockholm, Sweden, July 2024
Workshop on Statistical Network Analysis and Beyond, Nassau, Bahamas, June 2024
Tutorial lecture, ACM Sigmetrics, Venice, Italy, June 2024
Workshop on Learning in Networks: Discovering Hidden Structure, Northwestern University, April 2024

Recent results on planted assignment problems
Tutorial lectures, Artificial Intelligence Institute for Advances in Optimization, Georgia Tech, April 2024

The planted matching problem: Sharp threshold and infiniteorder phase transition
LUNUUMN Joint Probability Seminar, January 2022
Northwestern University, Industrial Engineering and Management Sciences, Oct. 2021
Harvard University, Statistics and School of Engineering and Applied Sciences, June 2021
INRIA, Paris, France, April 2021
Stochastic Networks, Applied Probability, and Performance (SNAPP) Seminar, Mar. 2021

Spectral graph matching and quadratic relaxations
Workshop on Graphical models, Exchangeable models and Graphons, MIT, August 2019

Efficient Random Graph Matching via Degree Profiles
Applied Probability Society Meeting, Brisbane, Austria, July 2019

Improved queuesize scaling for inputqueued switches via graph factorization
MostlyOM Workshop, The Chinese University of Hong Kong, Shenzhen, June 2019

Hidden Hamiltonian Cycle Recovery via Linear Programming
IMS Annual Meeting on Probability and Statistics, July 2018
Workshop in Operations Research and Data Science, Duke University, Dec. 2017
School of Operations Research and Information Engineering, Cornell University, Nov. 2017
Allerton Conference on Communication, Control, and Computing, Monticello, Oct. 2017
Joint Statistical Meeting, Baltimore, Aug. 2017
Simons Institute at UC Berkeley, June 2017
Workshop on Statistical Physics, Learning, Inference and Networks, Les Houches, France, Feb. 2017

Securing Distributed Machine Learning in High Dimensions
2018 ShanghaiTech Workshop on Information, Learning and Decision, June 2018

Two Vignettes from the Interface of Learning and Optimization
Booth School of Business, The University of Chicago, Feb. 2018

Informationtheoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization
Statistics Department, Yale University, Oct. 2016
Allerton Conference on Communication, Control, and Computing, Monticello, Sept. 2016

Finding a hidden community in networks: where is the
hard regime?
Applied Probability Society Meeting, July 2017
Industrial Engineering Department, Purdue University, Sept. 2016
Statistics Department, Purdue University, Sept. 2016
Simons Institute at UC Berkeley, Apr. 2016

Achieving exact cluster recovery threshold via semidefinite programming
Fudan International Conference on Data Science, Dec. 2016
INFORMS Annual Meeting, Nashville, Nov. 2016
Sante Fe Institute, Santa Fe, June 2016
Asilomar Conference on Signals, Systems, and Computers, Nov. 2015

Recovering a hidden community in networks
Electrical Engineering, Korea Advanced Institute of Science and Technology, Oct. 2015
On the optimality of local belief propagation under the degreecorrelated stochastic block model
Information Theory Workshop (ITW), Oct. 2015
Exact recovery threshold in the binary censored block model
Information Theory Workshop (ITW), Oct. 2015
Information and computation limits for recovering a hidden community in Networks
HajekFest: A Workshop on Networks, Games, and Algorithms, UIUC, Oct. 2015
Achieving exact cluster recovery threshold via semidefinite programming
International Symposium on Information Theory (ISIT), June 2015, SemiPlenary Talk
Community detection in networks: understanding the fundamental limits of polynomialtime algorithms
IDeAS Seminar, PACM, Princeton, Apr. 2015
Community detection in networks: fundamental limits and efficient algorithms
Information Theory and Applications Workshop (ITA), Feb. 2015, Graduation Day Talks
Statistical inference in networks: fundamental limits and efficient algorithms
Electrical Engineering Seminar Series, Harvard, Jan. 2015

Fundamental limits for community detection
Research Group Seminar, Department of Statistics, University of California, Berkeley, Oct. 2014

Fundamental limits for community detection
Information Theory Forum, Stanford University, Sept. 2014

Fundamental limits for community detection
Department of Statistics, The Wharton School, University of Pennsylvania, Aug. 2014
Jointly clustering rows and columns of binary matrices: algorithms and tradeoffs
ACM SIGMETRICS, June 2014

Statistical and computational phase transitions in planted models
Artificial Intelligence & Information Systems Seminar, Computer Science, UIUC, Mar. 2014

Statistical and computational phase transitions in planted models
CSL Communications Seminar, UIUC, Nov. 2013

Reconstruction in the sparse labeled stochastic block model
Information Theory Workshop (ITW), Sept. 2013

The supermarket game
Technicolor Paris Research Lab, June 2012
