research
∙
07/25/2023
A model for efficient dynamical ranking in networks
We present a physics-inspired method for inferring dynamic rankings in d...
share
research
∙
10/15/2022
Disordered Systems Insights on Computational Hardness
In this review article, we discuss connections between the physics of di...
research
∙
03/11/2022
The spectrum of the Grigoriev-Laurent pseudomoments
Grigoriev (2001) and Laurent (2003) independently showed that the sum-of...
research
∙
10/01/2021
Belief propagation for permutations, rankings, and partial orders
Many datasets give partial information about an ordering or ranking by i...
research
∙
07/29/2021
Improved Reconstruction of Random Geometric Graphs
Embedding graphs in a geographical or latent space, i.e., inferring loca...
research
∙
08/27/2020
Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs
We study the problem of efficiently refuting the k-colorability of a gra...
research
∙
12/18/2019
The Planted Matching Problem: Phase Transitions and Exact Results
We study the problem of recovering a planted matching in randomly weight...
research
∙
11/22/2019
Linear Consistency for Proof-of-Stake Blockchains
The blockchain data structure maintained via the longest-chain rule—popu...
research
∙
09/03/2019
Percolation is Odd
We discuss the number of spanning configurations in site percolation. We...
research
∙
07/30/2019
Lecture Notes on Automata, Languages, and Grammars
These lecture notes are intended as a supplement to Moore and Mertens' T...
research
∙
04/08/2019
The Kikuchi Hierarchy and Tensor PCA
For the tensor PCA (principal component analysis) problem, we propose a ...
research
∙
10/26/2017
Minimum Circuit Size, Graph Isomorphism, and Related Problems
We study the computational power of deciding whether a given truth-table...
research
∙
08/30/2017
Designing Strassen's algorithm
In 1969, Strassen shocked the world by showing that two n x n matrices c...
research
∙
06/19/2015
Detectability thresholds and optimal algorithms for community structure in dynamic networks
We study the fundamental limits on learning latent community structure i...
research
∙
04/29/2015
On the universal structure of human lexical semantics
How universal is human conceptual structure? The way concepts are organi...
research
∙
04/30/2014
Phase transitions in semisupervised clustering of sparse networks
Predicting labels of nodes in a network, such as community memberships o...
research
∙
03/23/2014
Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
Modularity is a popular measure of community structure. However, maximiz...
research
∙
12/02/2013
Phase Transitions in Community Detection: A Solvable Toy Model
Recently, it was shown that there is a phase transition in the community...
research
∙
06/24/2013
Spectral redemption: clustering sparse networks
Spectral algorithms are classic approaches to clustering and community d...
research
∙
03/28/2013
Scalable Text and Link Analysis with Mixed-Topic Link Models
Many data sets contain rich information about objects, as well as pairwi...
research
∙
07/17/2012
Model Selection for Degree-corrected Block Models
The proliferation of models for networks raises challenging problems of ...
research
∙
05/31/2012
Oriented and Degree-generated Block Models: Generating and Inferring Communities with Inhomogeneous Degree Distributions
The stochastic block model is a powerful tool for inferring community st...
research
∙
09/15/2011
Active Learning for Node Classification in Assortative and Disassortative Networks
In many real-world networks, nodes have class labels, attributes, or var...
research
∙
11/04/2008