research
∙
04/03/2023
A d^1/2+o(1) Monotonicity Tester for Boolean Functions on d-Dimensional Hypergrids
Monotonicity testing of Boolean functions on the hypergrid, f:[n]^d →{0,...
share
research
∙
11/16/2022
A Dichotomy Theorem for Linear Time Homomorphism Orbit Counting in Bounded Degeneracy Graphs
Counting the number of homomorphisms of a pattern graph H in a large inp...
research
∙
11/11/2022
Spectral Triadic Decompositions of Real-World Networks
A fundamental problem in mathematics and network analysis is to find con...
research
∙
11/10/2022
Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an O(n√(d)) Monotonicity Tester
The problem of testing monotonicity for Boolean functions on the hypergr...
research
∙
01/20/2022
Classic Graph Structural Features Outperform Factorization-Based Graph Embedding Methods on Community Labeling
Graph representation learning (also called graph embeddings) is a popula...
research
∙
06/05/2021
Faster and Generalized Temporal Triangle Counting, via Degeneracy Ordering
Triangle counting is a fundamental technique in network analysis, that h...
research
∙
04/19/2021
Randomized Algorithms for Scientific Computing (RASC)
Randomized algorithms have propelled advances in artificial intelligence...
research
∙
10/16/2020
Near-Linear Time Homomorphism Counting in Bounded Degeneracy Graphs: The Barrier of Long Induced Cycles
Counting homomorphisms of a constant sized pattern graph H in an input g...
research
∙
07/30/2020
Distribution-Free Models of Social Networks
The structure of large-scale social networks has predominantly been arti...
research
∙
06/24/2020
Provably and Efficiently Approximating Near-cliques using the Turán Shadow: PEANUTS
Clique and near-clique counts are important graph properties with applic...
research
∙
06/22/2020
How to Count Triangles, without Seeing the Whole Graph
Triangle counting is a fundamental problem in the analysis of large grap...
research
∙
03/29/2020
How the Degeneracy Helps for Triangle Counting in Graph Streams
We revisit the well-studied problem of triangle count estimation in grap...
research
∙
03/27/2020
The impossibility of low rank representations for triangle-rich complex networks
The study of complex networks is a significant development in modern sci...
research
∙
01/19/2020
The Power of Pivoting for Exact Clique Counting
Clique counting is a fundamental task in network analysis, and even the ...
research
∙
11/24/2019
Efficiently Counting Vertex Orbits of All 5-vertex Subgraphs, by EVOKE
Subgraph counting is a fundamental task in network analysis. Typically, ...
research
∙
11/14/2019
Linear Time Subgraph Counting, Graph Degeneracy, and the Chasm at Size Six
We consider the problem of counting all k-vertex subgraphs in an input g...
research
∙
04/01/2019
Random walks and forbidden minors II: A poly(dε^-1)-query tester for minor-closed properties of bounded-degree graphs
Let G be a graph with n vertices and maximum degree d. Fix some minor-cl...
research
∙
11/11/2018
Faster sublinear approximations of k-cliques for low arboricity graphs
Given query access to an undirected graph G, we consider the problem of ...
research
∙
11/04/2018
Domain Reduction for Monotonicity Testing: A o(d) Tester for Boolean Functions in d-Dimensions
We describe a Õ(d^5/6)-query monotonicity tester for Boolean functions f...
research
∙
11/04/2018
Domain Reduction for Monotonicity Testing: A o(d) Tester for Boolean Functions on Hypergrids
Testing monotonicity of Boolean functions over the hypergrid, f:[n]^d →{...
research
∙
05/21/2018
Finding forbidden minors in sublinear time: a n^1/2+o(1)-query one-sided tester for minor closed properties on bounded degree graphs
Let G be an undirected, bounded degree graph with n vertices. Fix a fini...
research
∙
05/21/2018
Fiding forbidden minors in sublinear time: a O(n^1/2 + o(1))-query one-sided tester for minor closed properties on bounded degree graphs
Let G be an undirected, bounded degree graph with n vertices. Fix a fini...
research
∙
04/20/2018
Finding Cliques in Social Networks: A New Distribution-Free Model
We propose a new distribution-free model of social networks. Our definit...
research
∙
01/09/2018
Adaptive Boolean Monotonicity Testing in Total Influence Time
The problem of testing monotonicity of a Boolean function f:{0,1}^n →{0,...
research
∙
10/29/2017
A o(d) ·polylog n Monotonicity Tester for Boolean Functions over the Hypergrid [n]^d
We study monotonicity testing of Boolean functions over the hypergrid [n...
research
∙
10/24/2017
Provable and practical approximations for the degree distribution using sublinear graph samples
The degree distribution is one of the most fundamental properties used i...
research
∙
07/19/2011