Xiaorui Sun

STOC Conference 2025 Conference Paper

On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials V: Over Commutative Rings

• Joshua A. Grochow
• Youming Qiao
• Katherine E. Stange
• Xiaorui Sun

FOCS Conference 2024 Conference Paper

Canonical Forms for Matrix Tuples in Polynomial Time

• Youming Qiao
• Xiaorui Sun

Left-right and conjugation actions on matrix tuples have received considerable attention in theoretical computer science due to their connections with polynomial identity testing, group isomorphism, and tensor isomorphism. In this paper, we present polynomial-time algorithms for computing canonical forms of matrix tuples over a finite field under these actions. Our algorithm builds upon new structural insights for matrix tuples, which can be viewed as a generalization of Schur's lemma for irreducible representations to general representations. Index Terms-canonical form, matrix tuples, tensors, group isomorphism, computer algebra

FOCS Conference 2024 Conference Paper

Faster Isomorphism Testing of p-Groups of Frattini Class 2

• Gábor Ivanyos
• Euan J. Mendoza
• Youming Qiao
• Xiaorui Sun
• Chuanqi Zhang

The finite group isomorphism problem asks to decide whether two finite groups of order $N$ are isomorphic. Improving the classical $N^{O(\mathrm{I}\mathrm{o}\mathrm{g}N)}$ -time algorithm for group isomorphism is a long-standing open problem. It is generally regarded that $p$ groups of class 2 and exponent $p$ form a bottleneck case for group isomorphism in general. The recent breakthrough by Sun (STOC '23) presents an $N^{O\left((\log N)^{5 / 6}\right)}$ -time algorithm for this group class. In this paper, we improve Sun's algorithm by presenting an $N^{{\tilde{O}}\left((\log {N})^{1^{1 / 2}}\right)}$ -time algorithm for this group class. We also extend our result to the more general $p$ -groups of Frattini class 2. Our algorithm is obtained by sharpening the key technical ingredients in Sun's algorithm and building connections with other research topics. One intriguing connection is with the maximal and non-commutative ranks of matrix spaces, which have recently received considerable attention in algebraic complexity and computational invariant theory. Results from the theory of Tensor Isomorphism complexity class (Grochow-Qiao, SIAM J. Comput. '23) are utilized to simplify the algorithm and achieve the extension to $p$ -groups of Frattini class 2.

SODA Conference 2024 Conference Paper

Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time

• Wenyu Jin 0001
• Xiaorui Sun
• Mikkel Thorup

We present a deterministic fully dynamic algorithm with subpolynomial worst-case time per graph update such that after processing each update of the graph, the algorithm outputs a minimum cut of the graph if the graph has a cut of size at most c for some c = (log n ) o (1). Previously, the best update time was for any c > 2 and c = O (log n ) [28].

STOC Conference 2023 Conference Paper

Faster Isomorphism for 𝑝-Groups of Class 2 and Exponent 𝑝

• Xiaorui Sun

The group isomorphism problem determines whether two groups, given by their Cayley tables, are isomorphic. For groups with order n , an algorithm with n (log n + O (1)) running time, attributed to Tarjan, was proposed in the 1970s (Miller, STOC 1978). Despite the extensive study over the past decades, the current best group isomorphism algorithm has an n (1 / 4 + o (1))log n running time (Rosenbaum 2013). The isomorphism testing for p -groups of (nilpotent) class 2 and exponent p has been identified as a major barrier to obtaining an n o (log n ) time algorithm for the group isomorphism problem. Although the p -groups of class 2 and exponent p have much simpler algebraic structures than general groups, the best-known isomorphism testing algorithm for this group class also has an n O (log n ) running time. In this paper, we present an isomorphism testing algorithm for p -groups of class 2 and exponent p with running time n O ((log n ) 5/6 ) for any prime p > 2. Our result is based on a novel reduction to the skew-symmetric matrix tuple isometry problem (Ivanyos and Qiao, SIAM J. Computing, 2019). To obtain the reduction, we develop several tools for matrix space analysis, including a matrix space individualization-refinement method and a characterization of the low rank matrix spaces.

SODA Conference 2022 Conference Paper

Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based ℓ 1 -Oblivious Routing

• Goran Zuzic
• Gramoz Goranci
• Mingquan Ye
• Bernhard Haeupler
• Xiaorui Sun

We provide universally-optimal distributed graph algorithms for (1+ ∊ )-approximate shortest path problems including shortest-path-tree and transshipment. The universal optimality of our algorithms guarantees that, on any n -node network G, our algorithm completes in T · n o (1) rounds whenever a T -round algorithm exists for G. This includes D · n o (1) -round algorithms for any planar or excluded-minor network. Our algorithms never require more than rounds, resulting in the first sub-linear-round distributed algorithm for transshipment. The key technical contribution leading to these results is the first efficient n o (1) -competitive linear ℓ 1 -oblivious routing operator that does not require the use of ℓ 1 -embeddings. Our construction is simple, solely based on low-diameter decompositions, and—in contrast to all known constructions—directly produces an oblivious flow instead of just an approximation of the optimal flow cost. This also has the benefit of simplifying the interaction with Sherman's multiplicative weight framework [SODA'17] in the distributed setting and its subsequent rounding procedures.

FOCS Conference 2021 Conference Paper

Fully Dynamic s-t Edge Connectivity in Subpolynomial Time (Extended Abstract)

• Wenyu Jin 0001
• Xiaorui Sun

We present a deterministic fully dynamic algorithm to answer c-edge connectivity queries on pairs of vertices in n°(1) worst case update and query time for any positive integer $c$ = (log n)° (1) for a graph with $n$ vertices. Previously, only polylogarithmic, O(√n), and O(n 2 / 3 ) worst case update time fully dynamic algorithms were known for answering 1, 2 and 3-edge connectivity queries respectively [Henzinger-King 1995, Frederikson 1997, Galil and Italiano 1991]. Our result extends the c-edge connectivity vertex sparsifier [Chalermsook et al. 2021] to a multi-level sparsification framework. As our main technical contribution, we present a novel update algorithm for the multi-level c-edge connectivity vertex sparsifier with subpolynomial update time. See https: //arxiv. org/abs/2004. 07650 for the full version of this paper.

FOCS Conference 2021 Conference Paper

Minor Sparsifiers and the Distributed Laplacian Paradigm

• Sebastian Forster
• Gramoz Goranci
• Yang P. Liu
• Richard Peng
• Xiaorui Sun
• Mingquan Ye

We study distributed algorithms built around minor-based vertex sparsifiers, and give the first algorithm in the CONGEST model for solving linear systems in graph Laplacian matrices to high accuracy. Our Laplacian solver has a round complexity of $O(n^{o(1)}(\sqrt{n}+D))$, and thus almost matches the lower bound of $\widetilde{\Omega}(\sqrt{n}+D)$, where $n$ is the number of nodes in the network and $D$ is its diameter. We show that our distributed solver yields new sublinear round algorithms for several cornerstone problems in combinatorial optimization. This is achieved by leveraging the powerful algorithmic framework of Interior Point Methods (IPMs) and the Laplacian paradigm in the context of distributed graph algorithms, which entails numerically solving optimization problems on graphs via a series of Laplacian systems. Problems that benefit from our distributed algorithmic paradigm include exact mincost flow, negative weight shortest paths, maxflow, and bipartite matching on sparse directed graphs. For the maxflow problem, this is the first exact distributed algorithm that applies to directed graphs, while the previous work by [Ghaffari et al. SICOMP'18] considered the approximate setting and works only for undirected graphs. For the mincost flow and the negative weight shortest path problems, our results constitute the first exact distributed algorithms running in a sublinear number of rounds. Given that the hybrid between IPMs and the Laplacian paradigm has proven useful for tackling numerous optimization problems in the centralized setting, we believe that our distributed solver will find future applications. At the heart of our distributed Laplacian solver is the notion of spectral subspace sparsifiers of [Li, Schild FOCS'18]. We present a nontrivial distributed implementation of their construction by (i) giving a parallel variant of their algorithm that avoids the sampling of random spanning trees and uses approximate leverage scores instead, and (ii) showing that the algorithm still produces a high-quality subspace spectral sparsifier by carefully setting up and analyzing matrix martingales. Combining this vertex reduction recursively with both tree and elimination-based preconditioners leads to our algorithm for solving Laplacian systems. The construction of the elimination-based preconditioners is based on computing short random walks, and we introduce a new technique for reducing the congestion incurred by the simulation of these walks on weighted graphs.

SODA Conference 2020 Conference Paper

Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds

• Laxman Dhulipala
• David Durfee
• Janardhan Kulkarni
• Richard Peng
• Saurabh Sawlani
• Xiaorui Sun

In this paper we study the problem of dynamically maintaining graph properties under batches of edge insertions and deletions in the massively parallel model of computation. In this setting, the graph is stored on a number of machines, each having space strongly sublinear with respect to the number of vertices, that is, n ϵ for some constant 0 < ϵ < 1. Our goal is to handle batches of updates and queries where the data for each batch fits onto one machine in constant rounds of parallel computation, as well as to reduce the total communication between the machines. This objective corresponds to the gradual buildup of databases over time, while the goal of obtaining constant rounds of communication for problems in the static setting has been elusive for problems as simple as undirected graph connectivity. We give an algorithm for dynamic graph connectivity in this setting with constant communication rounds and communication cost almost linear in terms of the batch size. Our techniques combine a new graph contraction technique, an independent random sample extractor from correlated samples, as well as distributed data structures supporting parallel updates and queries in batches. We also illustrate the power of dynamic algorithms in the MPC model by showing that the batched version of the adaptive connectivity problem is P-complete in the centralized setting, but sub-linear sized batches can be handled in a constant number of rounds. Due to the wide applicability of our approaches, we believe it represents a practically-motivated workaround to the current difficulties in designing more efficient massively parallel static graph algorithms.

SODA Conference 2019 Conference Paper

Approximating LCS in Linear Time: Beating the √n Barrier

• MohammadTaghi Hajiaghayi
• Masoud Seddighin
• Saeed Seddighin
• Xiaorui Sun

Longest common subsequence (LCS) is one of the most fundamental problems in combinatorial optimization. Apart from theoretical importance, LCS has enormous applications in bioinformatics, revision control systems, and data comparison programs 1. Although a simple dynamic program computes LCS in quadratic time, it has been recently proven that the problem admits a conditional lower bound and may not be solved in truly subquadratic time [2]. In addition to this, LCS is notoriously hard with respect to approximation algorithms. Apart from a trivial sampling technique that obtains a n x approximation solution in time O ( n 2–2 x ) nothing else is known for LCS. This is in sharp contrast to its dual problem edit distance for which several linear time solutions are obtained in the past two decades [4, 5, 9, 10, 16]. In this work, we present the first nontrivial algorithm for approximating LCS in linear time. Our main result is a linear time algorithm for the longest common subsequence which has an approximation factor of O ( n 0. 497956 ). This beats the barrier for approximating LCS in linear time.

FOCS Conference 2019 Conference Paper

Approximation Algorithms for LCS and LIS with Truly Improved Running Times

• Aviad Rubinstein
• Saeed Seddighin
• Zhao Song 0002
• Xiaorui Sun

Longest common subsequence (LCS) is a classic and central problem in combinatorial optimization. While LCS admits a quadratic time solution, recent evidence suggests that solving the problem may be impossible in truly subquadratic time. A special case of LCS wherein each character appears at most once in every string is equivalent to the longest increasing subsequence problem (LIS) which can be solved in quasilinear time. In this work, we present novel algorithms for approximating LCS in truly subquadratic time and LIS in truly sublinear time. Our approximation factors depend on the ratio of the optimal solution size over the input size. We denote this ratio by λ and obtain the following results for LCS and LIS without any prior knowledge of λ. • A truly subquadratic time algorithm for LCS with approximation factor O(λ^3). • A truly sublinear time algorithm for LIS with approximation factor O(λ^3). Triangle inequality was recently used by Boroujeni et al. [1] and Chakraborty et al. [2] to present new approximation algorithms for edit distance. Our techniques for LCS extend the notion of triangle inequality to non-metric settings.

SODA Conference 2019 Conference Paper

Massively Parallel Approximation Algorithms for Edit Distance and Longest Common Subsequence

• MohammadTaghi Hajiaghayi
• Saeed Seddighin
• Xiaorui Sun

STOC Conference 2018 Conference Paper

The query complexity of graph isomorphism: bypassing distribution testing lower bounds

• Krzysztof Onak
• Xiaorui Sun

We study the query complexity of graph isomorphism in the property testing model for dense graphs. We give an algorithm that makes n 1+ o (1) queries, improving on the previous best bound of Õ( n 5/4 ). Since the problem is known to require Ω( n ) queries, our algorithm is optimal up to a subpolynomial factor. While trying to extend a known connection to distribution testing, discovered by Fischer and Matsliah (SICOMP 2008), one encounters a natural obstacle presented by sampling lower bounds such as the Ω( n 2/3 )-sample lower bound for distribution closeness testing (Valiant, SICOMP 2011). In the context of graph isomorphism testing, these bounds lead to an n 1+Ω(1) barrier for Fischer and Matsliah’s approach. We circumvent this and other limitations by exploiting a geometric representation of the connectivity of vertices. An approximate representation of similarities between vertices can be learned with a near-linear number of queries and allows relaxed versions of sampling and distribution testing problems to be solved more efficiently.

STOC Conference 2017 Conference Paper

Efficient massively parallel methods for dynamic programming

• Sungjin Im
• Benjamin Moseley
• Xiaorui Sun

Modern science and engineering is driven by massively large data sets and its advance heavily relies on massively parallel computing platforms such as Spark, MapReduce, and Hadoop. Theoretical models have been proposed to understand the power and limitations of such platforms. Recent study of developed theoretical models has led to the discovery of new algorithms that are fast and efficient in both theory and practice, thereby beginning to unlock their underlying power. Given recent promising results, the area has turned its focus on discovering widely applicable algorithmic techniques for solving problems efficiently.

NeurIPS Conference 2017 Conference Paper

Linear regression without correspondence

• Daniel Hsu
• Kevin Shi
• Xiaorui Sun

This article considers algorithmic and statistical aspects of linear regression when the correspondence between the covariates and the responses is unknown. First, a fully polynomial-time approximation scheme is given for the natural least squares optimization problem in any constant dimension. Next, in an average-case and noise-free setting where the responses exactly correspond to a linear function of i. i. d. draws from a standard multivariate normal distribution, an efficient algorithm based on lattice basis reduction is shown to exactly recover the unknown linear function in arbitrary dimension. Finally, lower bounds on the signal-to-noise ratio are established for approximate recovery of the unknown linear function by any estimator.

STOC Conference 2015 Conference Paper

Faster Canonical Forms for Primitive Coherent Configurations: Extended Abstract

• Xiaorui Sun
• John Wilmes

Primitive coherent configurations (PCCs) are edge-colored digraphs that generalize strongly regular graphs (SRGs), a class perceived as difficult for Graph Isomorphism (GI). Moreover, PCCs arise naturally as obstacles to combinatorial divide-and-conquer approaches for general GI. In a natural sense, the isomorphism problem for PCCs is a stepping stone between SRGs and general GI. In his 1981 paper in the Annals of Math., Babai proposed a combinatorial approach to GI testing via an analysis of the standard individualization/refinement (I/R) technique and proved that I/R yields canonical forms of PCCs in time exp(~O(n 1/2 )). (The tilde hides polylogarithmic factors.) We improve this bound to exp(~O(n 1/3 )). This is faster than the current best bound, exp(~O(n 1/2 )), for general GI, and subsumes Spielman's exp(~O(n 1/3 )) bound for SRGs (STOC'96, only recently improved to exp(~O(n 1/5 )) by the present authors and their coauthors (FOCS'13)).

FOCS Conference 2015 Conference Paper

On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms

• Xi Chen 0001
• Ilias Diakonikolas
• Anthi Orfanou
• Dimitris Paparas
• Xiaorui Sun
• Mihalis Yannakakis

We study the optimal lottery problem and the optimal mechanism design problem in the setting of a single unit-demand buyer with item values drawn from independent distributions. Optimal solutions to both problems are characterized by a linear program with exponentially many variables. For the menu size complexity of the optimal lottery problem, we present an explicit, simple instance with distributions of support size 2, and show that exponentially many lotteries are required to achieve the optimal revenue. We also show that, when distributions have support size 2 and share the same high value, the simpler scheme of item pricing can achieve the same revenue as the optimal menu of lotteries. The same holds for the case of two items with support size 2 (but not necessarily the same high value). For the computational complexity of the optimal mechanism design problem, we show that unless the polynomial-time hierarchy collapses (more exactly, PNP = P#P), there is no universal efficient randomized algorithm to implement an optimal mechanism even when distributions have support size 3.

STOC Conference 2014 Conference Paper

Efficient density estimation via piecewise polynomial approximation

• Siu On Chan
• Ilias Diakonikolas
• Rocco A. Servedio
• Xiaorui Sun

NeurIPS Conference 2014 Conference Paper

Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms

• Siu On Chan
• Ilias Diakonikolas
• Rocco Servedio
• Xiaorui Sun

Let $p$ be an unknown and arbitrary probability distribution over $[0, 1)$. We consider the problem of \emph{density estimation}, in which a learning algorithm is given i. i. d. draws from $p$ and must (with high probability) output a hypothesis distribution that is close to $p$. The main contribution of this paper is a highly efficient density estimation algorithm for learning using a variable-width histogram, i. e. , a hypothesis distribution with a piecewise constant probability density function. In more detail, for any $k$ and $\eps$, we give an algorithm that makes $\tilde{O}(k/\eps^2)$ draws from $p$, runs in $\tilde{O}(k/\eps^2)$ time, and outputs a hypothesis distribution $h$ that is piecewise constant with $O(k \log^2(1/\eps))$ pieces. With high probability the hypothesis $h$ satisfies $\dtv(p, h) \leq C \cdot \opt_k(p) + \eps$, where $\dtv$ denotes the total variation distance (statistical distance), $C$ is a universal constant, and $\opt_k(p)$ is the smallest total variation distance between $p$ and any $k$-piecewise constant distribution. The sample size and running time of our algorithm are both optimal up to logarithmic factors. The ``approximation factor'' $C$ that is present in our result is inherent in the problem, as we prove that no algorithm with sample size bounded in terms of $k$ and $\eps$ can achieve $C < 2$ regardless of what kind of hypothesis distribution it uses.

SODA Conference 2014 Conference Paper

The Complexity of Optimal Multidimensional Pricing

• Xi Chen 0001
• Ilias Diakonikolas
• Dimitris Paparas
• Xiaorui Sun
• Mihalis Yannakakis

We resolve the complexity of revenue-optimal deterministic auctions in the unit-demand single-buyer Bayesian setting, i. e. , the optimal item pricing problem, when the buyer's values for the items are independent. We show that the problem of computing a revenue-optimal pricing can be solved in polynomial time for distributions of support size 2 and its decision version is NP-complete for distributions of support size 3. We also show that the problem remains NP-complete for the case of identical distributions.

FOCS Conference 2013 Conference Paper

Faster Canonical Forms for Strongly Regular Graphs

• László Babai
• Xi Chen 0001
• Xiaorui Sun
• Shang-Hua Teng
• John Wilmes

We show that a canonical form for strongly regular (s. r.) graphs can be found in time exp(O~(n1/5)) and therefore isomorphism of s. r. graphs can be tested within the same time bound, where n is the number of vertices and the tilde hides a polylogarithmic factor. The best previous bound for testing isomorphism of s. r. graphs was exp(O~(n1/3)) (Spiel man, STOC 1996) while the bound for GI in general has been standing firmly at exp(O~(n1/2)) for three decades. (These results, too, provided canonical forms.) The previous bounds on isomorphism of s. r. graphs (Babai 1980 and Spiel man 1996) were based on the analysis of the classical individualization/refinement (I/R) heuristic. The present bound depends on a combination of a deeper analysis of the I/R heuristic with Luks's group theoretic divide-and-conquer methods following Babai-Luks (STOC 1983) and Miller (1983). Our analysis builds on Spiel man's work that brought Neumaier's 1979 classification of s. r. graphs to bear on the problem. One of Neumaier's classes, the line-graphs of Steiner 2-designs, has been eliminated as a bottleneck in recent work by the present authors (STOC'13). In the remaining hard cases, we have the benefit of Neumaier's claw bound" and its asymptotic consequences derived by Spiel man, some of which we improve via a new "clique geometry. " We also prove, by an analysis of the I/R heuristic, that, with known (trivial) exceptions, s. r. graphs have exp(O~(n9/37)) automorphisms, improving Spiel man's exp(O~(n1/3)) bound. No knowledge of group theory is required for this paper. The group theoretic method is only used through an easily stated combinatorial consequence (Babai -- Luks, 1983 combined with Miller, 1983). While the bulk of this paper is joint work by the five authors, it also includes two contributions by subsets of the authors: the clique geometry [BW] and the auto orphism bound [CST]. "

SODA Conference 2013 Conference Paper

Learning mixtures of structured distributions over discrete domains

• Siu On Chan
• Ilias Diakonikolas
• Rocco A. Servedio
• Xiaorui Sun

Let be a class of probability distributions over the discrete domain [ n ] = {1, …, n }. We show that if satisfies a rather general condition – essentially, that each distribution in can be well-approximated by a variable-width histogram with few bins – then there is a highly efficient (both in terms of running time and sample complexity) algorithm that can learn any mixture of k unknown distributions from. We analyze several natural types of distributions over [ n ], including log-concave, monotone hazard rate and unimodal distributions, and show that they have the required structural property of being well-approximated by a histogram with few bins. Applying our general algorithm, we obtain near-optimally efficient algorithms for all these mixture learning problems as described below. More precisely, Log-concave distributions: We learn any mixture of k log-concave distributions over [ n ] using k · Õ (1/ε 4 ) samples (independent of n ) and running in time Õ ( k log( n )/ε 4 ) bit-operations (note that reading a single sample from [ n ] takes Θ(log n ) bit operations). For the special case k = 1 we give an efficient algorithm using Õ (1/ε 3 ) samples; this generalizes the main result of [DDS12b] from the class of Poisson Binomial distributions to the much broader class of all log-concave distributions. Our upper bounds are not far from optimal since any algorithm for this learning problem requires Ω( k /ε 5/2 ) samples. Monotone hazard rate (MHR) distributions: We learn any mixture of k MHR distributions over [ n ] using O ( k log( n /ε)/ε 4 ) samples and running in time Õ ( k log ( n )/ε 4 ) bit-operations. Any algorithm for this learning problem must use Ω( k log( n )/ε 3 ) samples. Unimodal distributions: We give an algorithm that learns any mixture of k unimodal distributions over [ n ] using O ( k log( n )/ε 4 ) samples and running in time Õ ( k log 2 ( n )/ε 4 ) bit-operations. Any algorithm for this problem must use Ω( k log( n )/ε 3 ) samples.

STOC Conference 2013 Conference Paper

Multi-stage design for quasipolynomial-time isomorphism testing of steiner 2-systems

• Xi Chen 0001
• Xiaorui Sun
• Shang-Hua Teng

A standard heuristic for testing graph isomorphism is to first assign distinct labels to a small set of vertices of an input graph, and then propagate to create new vertex labels across the graph, aiming to assign distinct and isomorphism-invariant labels to all vertices in the graph. This is usually referred to as the individualization/refinement method for canonical labeling of graphs. We present a quasipolynomial-time algorithm for isomorphism testing of Steiner 2-systems. A Steiner 2-system consists of points and lines, where each line passes the same number of points and each pair of points uniquely determines a line. Each Steiner 2-system induces a Steiner graph, in which vertices represent lines and edges represent intersections of lines. Steiner graphs are an important subfamily of strongly regular graphs whose isomorphism testing has challenged researchers for years. Inspired by both the individualization/refinement method and the previous analyses of Babai and Spielman, we consider an extended framework for isomorphism testing of Steiner 2-systems, in which we use a small set of randomly chosen points and lines to build isomorphism-invariant multi-stage combinatorial structures that are sufficient to distinguish all pairs of points of a Steiner 2-system. Applying this framework, we show that isomorphism of Steiner 2-systems with n lines can be tested in time smash{n O(log n) }, improving the previous best bound of smash{exp(~{O}(n 1/4 ))} by Spielman. Before our result, quasipolynomial-time isomorphism testing was only known for the case when the line size is polylogarithmic, as shown by Babai and Luks. A result essentially identical to ours was obtained simultaneously by Laszlo Babai and John Wilmes. They performed a direct analysis of the individualization/refinement method, building on a different philosophy and combinatorial structure theory. We comment on how this paper fits into the overall project of improved isomorphism testing for strongly regular graphs (the ultimate goal being subexponential exp(n o(1) ) time). In the remaining cases, we only need to deal with strongly regular graphs satisfying "Neumaier's claw bound," permitting the use of a separate set of asymptotic structural tools. In joint work (in progress) with Babai and Wilmes, we address that case and have already pushed the overall bound below smash{exp(~{O}(n 1/4 ))}. The present paper is a methodologically distinct and stand-alone part of the overall project.

SODA Conference 2012 Conference Paper

Information dissemination via random walks in d -dimensional space

• Henry Lam
• Zhenming Liu
• Michael Mitzenmacher
• Xiaorui Sun
• Yajun Wang 0001

IJCAI Conference 2011 Conference Paper

Community Detection in Social Networks through Community Formation Games

• Wei Chen
• Zhenming Liu
• Xiaorui Sun
• Yajun Wang

We introduce a game-theoretic framework to address the community detection problem based on the social networks' structure. The dynamics of community formation is framed as a strategic game called community formation game: Given a social network, each node is selfish and selects communities to join or leave based on her own utility measurement. A community structure can be interpreted as an equilibrium of this game. We formulate the agents' utility by the combination of a gain function and a loss function. Each agent can select multiple communities, which naturally captures the concept of "overlapping communities". We propose a gain function based on Newman's modularity function and a simple loss function that reflects the intrinsic costs incurred when people join the communities. We conduct extensive experiments under this framework; our results show that our algorithm is effective in identifying overlapping communities, and is often better than other algorithms we evaluated especially when many people belong to multiple communities.