research
∙
09/11/2023
Combinative Cumulative Knowledge Processes
We analyze Cumulative Knowledge Processes, introduced by Ben-Eliezer, Mi...
share
research
∙
09/11/2023
Influence Maximization in Ising Models
Given a complex high-dimensional distribution over {± 1}^n, what is the ...
research
∙
07/14/2023
Influences in Mixing Measures
The theory of influences in product measures has profound applications i...
research
∙
02/28/2023
Sharp thresholds in inference of planted subgraphs
A major question in the study of the Erdős–Rényi random graph is to unde...
research
∙
01/31/2023
A Mathematical Model for Curriculum Learning
Curriculum learning (CL) - training using samples that are generated and...
research
∙
12/06/2022
Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees
In this paper we continue to rigorously establish the predictions in gro...
research
∙
10/12/2022
The Power of Two Matrices in Spectral Algorithms
Spectral algorithms are some of the main tools in optimization and infer...
research
∙
09/22/2022
A second moment proof of the spread lemma
This note concerns a well-known result which we term the “spread lemma,”...
research
∙
09/07/2022
On the Second Kahn–Kalai Conjecture
For any given graph H, we are interested in p_crit(H), the minimal p suc...
research
∙
05/23/2022
Agreement and Statistical Efficiency in Bayesian Perception Models
Bayesian models of group learning are studied in Economics since the 197...
research
∙
04/10/2022
Efficient Reconstruction of Stochastic Pedigrees: Some Steps From Theory to Practice
In an extant population, how much information do extant individuals prov...
research
∙
04/05/2022
Almost-Linear Planted Cliques Elude the Metropolis Process
A seminal work of Jerrum (1992) showed that large cliques elude the Metr...
research
∙
03/22/2022
Spectral Algorithms Optimally Recover (Censored) Planted Dense Subgraphs
We study spectral algorithms for the planted dense subgraph problem (PDS...
research
∙
09/14/2021
Reconstruction on Trees and Low-Degree Polynomials
The study of Markov processes and broadcasting on trees has deep connect...
research
∙
07/25/2021
In Defense of Fluid Democracy
Fluid democracy is a voting paradigm that allows voters to choose betwee...
research
∙
07/13/2021
Information Spread with Error Correction
We study the process of information dispersal in a network with communic...
research
∙
07/13/2021
Spectral Recovery of Binary Censored Block Models
Community detection is the problem of identifying community structure in...
research
∙
06/15/2021
Spoofing Generalization: When Can't You Trust Proprietary Models?
In this work, we study the computational complexity of determining wheth...
research
∙
05/31/2021
Approximate polymorphisms
For a function g{0,1}^m→{0,1}, a function f{0,1}^n→{0,1} is called a g-p...
research
∙
01/15/2021
Learning to Sample from Censored Markov Random Fields
We study learning Censor Markov Random Fields (abbreviated CMRFs). These...
research
∙
10/03/2020
Broadcasting on Two-Dimensional Regular Grids
We study a specialization of the problem of broadcasting on directed acy...
research
∙
05/08/2020
Efficient Reconstruction of Stochastic Pedigrees
We introduce a new algorithm called Rec-Gen for reconstructing the gene...
research
∙
04/27/2020
A Phase Transition in Arrow's Theorem
Arrow's Theorem concerns a fundamental problem in social choice theory: ...
research
∙
04/24/2020
Robust testing of low-dimensional functions
A natural problem in high-dimensional inference is to decide if a classi...
research
∙
11/01/2019
AND Testing and Robust Judgement Aggregation
A function f{0,1}^n→{0,1} is called an approximate AND-homomorphism if c...
research
∙
05/24/2019
Accuracy-Memory Tradeoffs and Phase Transitions in Belief Propagation
The analysis of Belief Propagation and other algorithms for the reconst...
research
∙
05/10/2019
Seeding with Costly Network Information
The spread of behavior over social networks depends on the contact struc...
research
∙
04/11/2019
The Circuit Complexity of Inference
Belief propagation is one of the foundations of probabilistic and causal...
research
∙
04/08/2019
Junta correlation is testable
The problem of tolerant junta testing is a natural and challenging probl...
research
∙
11/07/2018
How Many Subpopulations is Too Many? Exponential Lower Bounds for Inferring Population Histories
Reconstruction of population histories is a central problem in populatio...
research
∙
11/07/2018
Broadcasting on Random Directed Acyclic Graphs
We study a generalization of the well-known model of broadcasting on tre...
research
∙
09/27/2018
Being Corrupt Requires Being Clever, But Detecting Corruption Doesn't
We consider a variation of the problem of corruption detection on networ...
research
∙
09/04/2018
Reasoning in Bayesian Opinion Exchange Networks Is PSPACE-Hard
We study the Bayesian model of opinion exchange of fully rational agents...
research
∙
07/26/2018
Seeded Graph Matching via Large Neighborhood Statistics
We study a well known noisy model of the graph isomorphism problem. In t...
research
∙
07/23/2018
Contextual Stochastic Block Models
We provide the first information theoretic tight analysis for inference ...
research
∙
06/26/2018
Is your function low-dimensional?
We study the problem of testing if a function depends on a small number ...
research
∙
06/26/2018
Is your data low-dimensional?
We study the problem of testing if a function depends on a small number ...
research
∙
05/25/2018
Learning Restricted Boltzmann Machines via Influence Maximization
Graphical models are a rich language for describing high-dimensional dis...
research
∙
03/20/2018
Broadcasting on Bounded Degree DAGs
We study the following generalization of the well-known model of broadca...
research
∙
02/16/2018
The Vertex Sample Complexity of Free Energy is Polynomial
We study the following question: given a massive Markov random field on ...
research
∙
02/16/2018
The Mean-Field Approximation: Information Inequalities, Algorithms, and Complexity
The mean field approximation to the Ising model is a canonical variation...
research
∙
11/05/2017
Approximating Partition Functions in Constant Time
We study approximations of the partition function of dense graphical mod...
research
∙
05/12/2017
Bayesian Group Decisions: Algorithms and Complexity
We address the computations that Bayesian agents undertake to realize th...
research
∙
09/10/2015
Density Evolution in the Degree-correlated Stochastic Block Model
There is a recent surge of interest in identifying the sharp recovery th...
research
∙
08/10/2015
Local Algorithms for Block Models with Side Information
There has been a recent interest in understanding the power of local alg...
research
∙
03/12/2015
On the Impossibility of Learning the Missing Mass
This paper shows that one cannot learn the probability of rare events wi...
research
∙
07/13/2013
MCMC Learning
The theory of learning under the uniform distribution is rich and deep, ...
research
∙
06/24/2013
Spectral redemption: clustering sparse networks
Spectral algorithms are classic approaches to clustering and community d...
research
∙
02/03/2010