BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Shang-Hua Teng

Shang-Hua Teng appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsSocial and Information NetworksComputer Science and Game TheoryMachine LearningComputational ComplexityDiscrete Mathematicsphysics.soc-phArtificial IntelligenceComputationComputation and LanguageComputational Engineering, Finance, and ScienceComputational GeometryInformation Retrievalmath.COmath.DGmath.MGmath.NANumerical Analysisphysics.data-an

Catalog footprint

What is connected

19works
19topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

19 published item(s)

preprint2026arXiv

A Theory of Time-Sensitive Language Generation: Sparse Hallucination Beats Mode Collapse

We study language generation in the limit under a global preference ordering on strings, as introduced by Kleinberg and Wei. As in [arXiv:2504.14370, arXiv:2511.05295], we aim for \emph{breadth}, but impose an additional requirement of timeliness: higher-ranked strings should be generated earlier. A string is then only credited if it is generated before a deadline, where its deadline is defined by a function that maps a string's rank in the target language to the time by which it must be produced. This is in keeping with a central consideration in machine learning, where inductive bias favors ``simpler'' or ``more plausible'' outputs, all else being equal. We show that timely generation is impossible in a strong sense for eventually consistent generators -- the protagonists of most prior related work. Under what is perhaps the mildest natural relaxation of consistency, a hallucination rate that vanishes over time, we show that we can circumvent our impossibility result. In particular, we can achieve optimal density with respect to any superlinear deadline function. We also show this is tight by ruling out timely generation with linear deadlines and vanishing hallucination rate.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Network Composition from Multi-layer Data

It is common for people to access multiple social networks, for example, using phone, email, and social media. Together, the multi-layer social interactions form a "integrated social network." How can we extend well developed knowledge about single-layer networks, including vertex centrality and community structure, to such heterogeneous structures? In this paper, we approach these challenges by proposing a principled framework of network composition based on a unified dynamical process. Mathematically, we consider the following abstract problem: Given multi-layer network data and additional parameters for intra and inter-layer dynamics, construct a (single) weighted network that best integrates the joint process. We use transformations of dynamics to unify heterogeneous layers under a common dynamics. For inter-layer compositions, we will consider several cases as the inter-layer dynamics plays different roles in various social or technological networks. Empirically, we provide examples to highlight the usefulness of this framework for network analysis and network design.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Mixture Selection, Mechanism Design, and Signaling

We pose and study a fundamental algorithmic problem which we term mixture selection, arising as a building block in a number of game-theoretic applications: Given a function $g$ from the $n$-dimensional hypercube to the bounded interval $[-1,1]$, and an $n \times m$ matrix $A$ with bounded entries, maximize $g(Ax)$ over $x$ in the $m$-dimensional simplex. This problem arises naturally when one seeks to design a lottery over items for sale in an auction, or craft the posterior beliefs for agents in a Bayesian game through the provision of information (a.k.a. signaling). We present an approximation algorithm for this problem when $g$ simultaneously satisfies two smoothness properties: Lipschitz continuity with respect to the $L^\infty$ norm, and noise stability. The latter notion, which we define and cater to our setting, controls the degree to which low-probability errors in the inputs of $g$ can impact its output. When $g$ is both $O(1)$-Lipschitz continuous and $O(1)$-stable, we obtain an (additive) PTAS for mixture selection. We also show that neither assumption suffices by itself for an additive PTAS, and both assumptions together do not suffice for an additive FPTAS. We apply our algorithm to different game-theoretic applications from mechanism design and optimal signaling. We make progress on a number of open problems suggested in prior work by easily reducing them to mixture selection: we resolve an important special case of the small-menu lottery design problem posed by Dughmi, Han, and Nisan; we resolve the problem of revenue-maximizing signaling in Bayesian second-price auctions posed by Emek et al. and Miltersen and Sheffet; we design a quasipolynomial-time approximation scheme for the optimal signaling problem in normal form games suggested by Dughmi; and we design an approximation algorithm for the optimal signaling problem in the voting model of Alonso and Câmara.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Spectral Sparsification of Random-Walk Matrix Polynomials

We consider a fundamental algorithmic question in spectral graph theory: Compute a spectral sparsifier of random-walk matrix-polynomial $$L_α(G)=D-\sum_{r=1}^dα_rD(D^{-1}A)^r$$ where $A$ is the adjacency matrix of a weighted, undirected graph, $D$ is the diagonal matrix of weighted degrees, and $α=(α_1...α_d)$ are nonnegative coefficients with $\sum_{r=1}^dα_r=1$. Recall that $D^{-1}A$ is the transition matrix of random walks on the graph. The sparsification of $L_α(G)$ appears to be algorithmically challenging as the matrix power $(D^{-1}A)^r$ is defined by all paths of length $r$, whose precise calculation would be prohibitively expensive. In this paper, we develop the first nearly linear time algorithm for this sparsification problem: For any $G$ with $n$ vertices and $m$ edges, $d$ coefficients $α$, and $ε> 0$, our algorithm runs in time $O(d^2m\log^2n/ε^{2})$ to construct a Laplacian matrix $\tilde{L}=D-\tilde{A}$ with $O(n\log n/ε^{2})$ non-zeros such that $\tilde{L}\approx_εL_α(G)$. Matrix polynomials arise in mathematical analysis of matrix functions as well as numerical solutions of matrix equations. Our work is particularly motivated by the algorithmic problems for speeding up the classic Newton's method in applications such as computing the inverse square-root of the precision matrix of a Gaussian random field, as well as computing the $q$th-root transition (for $q\geq1$) in a time-reversible Markov model. The key algorithmic step for both applications is the construction of a spectral sparsifier of a constant degree random-walk matrix-polynomials introduced by Newton's method. Our algorithm can also be used to build efficient data structures for effective resistances for multi-step time-reversible Markov models, and we anticipate that it could be useful for other tasks in network analysis.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The Interplay Between Dynamics and Networks: Centrality, Communities, and Cheeger Inequality

We study the interplay between a dynamic process and the structure of the network on which it is defined. Specifically, we examine the impact of this interaction on the quality-measure of network clusters and node centrality. This enables us to effectively identify network communities and important nodes participating in the dynamics. As the first step towards this objective, we introduce an umbrella framework for defining and characterizing an ensemble of dynamic processes on a network. This framework generalizes the traditional Laplacian framework to continuous-time biased random walks and also allows us to model some epidemic processes over a network. For each dynamic process in our framework, we can define a function that measures the quality of every subset of nodes as a potential cluster (or community) with respect to this process on a given network. This subset-quality function generalizes the traditional conductance measure for graph partitioning. We partially justify our choice of the quality function by showing that the classic Cheeger's inequality, which relates the conductance of the best cluster in a network with a spectral quantity of its Laplacian matrix, can be extended from the Laplacian-conductance setting to this more general setting.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Efficient Clustering with Limited Distance Information

Given a point set S and an unknown metric d on S, we study the problem of efficiently partitioning S into k clusters while querying few distances between the points. In our model we assume that we have access to one versus all queries that given a point s 2 S return the distances between s and all other points. We show that given a natural assumption about the structure of the instance, we can efficiently find an accurate clustering using only O(k) distance queries. We use our algorithm to cluster proteins by sequence similarity. This setting nicely fits our model because we can use a fast sequence database search program to query a sequence against an entire dataset. We conduct an empirical study that shows that even though we query a small fraction of the distances between the points, we produce clusterings that are close to a desired clustering given by manual classification.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Fixed-Points of Social Choice: An Axiomatic Approach to Network Communities

We provide the first social choice theory approach to the question of what constitutes a community in a social network. Inspired by the classic preferences models in social choice theory, we start from an abstract social network framework, called preference networks; these consist of a finite set of members where each member has a total-ranking preference of all members in the set. Within this framework, we develop two complementary approaches to axiomatically study the formation and structures of communities. (1) We apply social choice theory and define communities indirectly by postulating that they are fixed points of a preference aggregation function obeying certain desirable axioms. (2) We directly postulate desirable axioms for communities without reference to preference aggregation, leading to eight natural community axioms. These approaches allow us to formulate and analyze community rules. We prove a taxonomy theorem that provides a structural characterization of the family of community rules that satisfies all eight axioms. The structure is actually quite beautiful: these community rules form a bounded lattice under the natural intersection and union operations. Our structural theorem is complemented with a complexity result: while identifying a community by the most selective rule of the lattice is in P, deciding if a subset is a community by the most comprehensive rule of the lattice is coNP-complete. Our studies also shed light on the limitations of defining community rules solely based on preference aggregation: any aggregation function satisfying Arrow's IIA axiom, or based on commonly used aggregation schemes like the Borda count or generalizations thereof, lead to communities which violate at least one of our community axioms. Finally, we give a polynomial-time rule consistent with seven axioms and weakly satisfying the eighth axiom.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Scalable Parallel Factorizations of SDD Matrices and Efficient Sampling for Gaussian Graphical Models

Motivated by a sampling problem basic to computational statistical inference, we develop a nearly optimal algorithm for a fundamental problem in spectral graph theory and numerical analysis. Given an $n\times n$ SDDM matrix ${\bf \mathbf{M}}$, and a constant $-1 \leq p \leq 1$, our algorithm gives efficient access to a sparse $n\times n$ linear operator $\tilde{\mathbf{C}}$ such that $${\mathbf{M}}^{p} \approx \tilde{\mathbf{C}} \tilde{\mathbf{C}}^\top.$$ The solution is based on factoring ${\bf \mathbf{M}}$ into a product of simple and sparse matrices using squaring and spectral sparsification. For ${\mathbf{M}}$ with $m$ non-zero entries, our algorithm takes work nearly-linear in $m$, and polylogarithmic depth on a parallel machine with $m$ processors. This gives the first sampling algorithm that only requires nearly linear work and $n$ i.i.d. random univariate Gaussian samples to generate i.i.d. random samples for $n$-dimensional Gaussian random fields with SDDM precision matrices. For sampling this natural subclass of Gaussian random fields, it is optimal in the randomness and nearly optimal in the work and parallel complexity. In addition, our sampling algorithm can be directly extended to Gaussian random fields with SDD precision matrices.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Multi-Scale Matrix Sampling and Sublinear-Time PageRank Computation

A fundamental problem arising in many applications in Web science and social network analysis is, given an arbitrary approximation factor $c>1$, to output a set $S$ of nodes that with high probability contains all nodes of PageRank at least $Δ$, and no node of PageRank smaller than $Δ/c$. We call this problem {\sc SignificantPageRanks}. We develop a nearly optimal, local algorithm for the problem with runtime complexity $\tilde{O}(n/Δ)$ on networks with $n$ nodes. We show that any algorithm for solving this problem must have runtime of $Ω(n/Δ)$, rendering our algorithm optimal up to logarithmic factors. Our algorithm comes with two main technical contributions. The first is a multi-scale sampling scheme for a basic matrix problem that could be of interest on its own. In the abstract matrix problem it is assumed that one can access an unknown {\em right-stochastic matrix} by querying its rows, where the cost of a query and the accuracy of the answers depend on a precision parameter $ε$. At a cost propositional to $1/ε$, the query will return a list of $O(1/ε)$ entries and their indices that provide an $ε$-precision approximation of the row. Our task is to find a set that contains all columns whose sum is at least $Δ$, and omits any column whose sum is less than $Δ/c$. Our multi-scale sampling scheme solves this problem with cost $\tilde{O}(n/Δ)$, while traditional sampling algorithms would take time $Θ((n/Δ)^2)$. Our second main technical contribution is a new local algorithm for approximating personalized PageRank, which is more robust than the earlier ones developed in \cite{JehW03,AndersenCL06} and is highly efficient particularly for networks with large in-degrees or out-degrees. Together with our multiscale sampling scheme we are able to optimally solve the {\sc SignificantPageRanks} problem.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Finding Endogenously Formed Communities

A central problem in e-commerce is determining overlapping communities among individuals or objects in the absence of external identification or tagging. We address this problem by introducing a framework that captures the notion of communities or clusters determined by the relative affinities among their members. To this end we define what we call an affinity system, which is a set of elements, each with a vector characterizing its preference for all other elements in the set. We define a natural notion of (potentially overlapping) communities in an affinity system, in which the members of a given community collectively prefer each other to anyone else outside the community. Thus these communities are endogenously formed in the affinity system and are "self-determined" or "self-certified" by its members. We provide a tight polynomial bound on the number of self-determined communities as a function of the robustness of the community. We present a polynomial-time algorithm for enumerating these communities. Moreover, we obtain a local algorithm with a strong stochastic performance guarantee that can find a community in time nearly linear in the of size the community. Social networks fit particularly naturally within the affinity system framework -- if we can appropriately extract the affinities from the relatively sparse yet rich information from social networks, our analysis then yields a set of efficient algorithms for enumerating self-determined communities in social networks. In the context of social networks we also connect our analysis with results about $(α,β)$-clusters introduced by Mishra, Schreiber, Stanton, and Tarjan \cite{msst}. In contrast with the polynomial bound we prove on the number of communities in the affinity system model, we show that there exists a family of networks with superpolynomial number of $(α,β)$-clusters.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Clustering Protein Sequences Given the Approximation Stability of the Min-Sum Objective Function

We study the problem of efficiently clustering protein sequences in a limited information setting. We assume that we do not know the distances between the sequences in advance, and must query them during the execution of the algorithm. Our goal is to find an accurate clustering using few queries. We model the problem as a point set $S$ with an unknown metric $d$ on $S$, and assume that we have access to \emph{one versus all} distance queries that given a point $s \in S$ return the distances between $s$ and all other points. Our one versus all query represents an efficient sequence database search program such as BLAST, which compares an input sequence to an entire data set. Given a natural assumption about the approximation stability of the \emph{min-sum} objective function for clustering, we design a provably accurate clustering algorithm that uses few one versus all queries. In our empirical study we show that our method compares favorably to well-established clustering algorithms when we compare computationally derived clusterings to gold-standard manual classifications.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Efficient Clustering with Limited Distance Information

Given a point set S and an unknown metric d on S, we study the problem of efficiently partitioning S into k clusters while querying few distances between the points. In our model we assume that we have access to one versus all queries that given a point s in S return the distances between s and all other points. We show that given a natural assumption about the structure of the instance, we can efficiently find an accurate clustering using only O(k) distance queries. Our algorithm uses an active selection strategy to choose a small set of points that we call landmarks, and considers only the distances between landmarks and other points to produce a clustering. We use our algorithm to cluster proteins by sequence similarity. This setting nicely fits our model because we can use a fast sequence database search program to query a sequence against an entire dataset. We conduct an empirical study that shows that even though we query a small fraction of the distances between the points, we produce clusterings that are close to a desired clustering given by manual classification.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Metric uniformization and spectral bounds for graphs

We present a method for proving upper bounds on the eigenvalues of the graph Laplacian. A main step involves choosing an appropriate "Riemannian" metric to uniformize the geometry of the graph. In many interesting cases, the existence of such a metric is shown by examining the combinatorics of special types of flows. This involves proving new inequalities on the crossing number of graphs. In particular, we use our method to show that for any positive integer k, the kth smallest eigenvalue of the Laplacian on an n-vertex, bounded-degree planar graph is O(k/n). This bound is asymptotically tight for every k, as it is easily seen to be achieved for square planar grids. We also extend this spectral result to graphs with bounded genus, and graphs which forbid fixed minors. Previously, such spectral upper bounds were only known for the case k=2.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Non-Conservative Diffusion and its Application to Social Network Analysis

The random walk is fundamental to modeling dynamic processes on networks. Metrics based on the random walk have been used in many applications from image processing to Web page ranking. However, how appropriate are random walks to modeling and analyzing social networks? We argue that unlike a random walk, which conserves the quantity diffusing on a network, many interesting social phenomena, such as the spread of information or disease on a social network, are fundamentally non-conservative. When an individual infects her neighbor with a virus, the total amount of infection increases. We classify diffusion processes as conservative and non-conservative and show how these differences impact the choice of metrics used for network analysis, as well as our understanding of network structure and behavior. We show that Alpha-Centrality, which mathematically describes non-conservative diffusion, leads to new insights into the behavior of spreading processes on networks. We give a scalable approximate algorithm for computing the Alpha-Centrality in a massive graph. We validate our approach on real-world online social networks of Digg. We show that a non-conservative metric, such as Alpha-Centrality, produces better agreement with empirical measure of influence than conservative metrics, such as PageRank. We hope that our investigation will inspire further exploration into the realms of conservative and non-conservative metrics in social network analysis.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A Complexity View of Markets with Social Influence

In this paper, inspired by the work of Megiddo on the formation of preferences and strategic analysis, we consider an early market model studied in the field of economic theory, in which each trader's utility may be influenced by the bundles of goods obtained by her social neighbors. The goal of this paper is to understand and characterize the impact of social influence on the complexity of computing and approximating market equilibria. We present complexity-theoretic and algorithmic results for approximating market equilibria in this model with focus on two concrete influence models based on the traditional linear utility functions. Recall that an Arrow-Debreu market equilibrium in a conventional exchange market with linear utility functions can be computed in polynomial time by convex programming. Our complexity results show that even a bounded-degree, planar influence network can significantly increase the difficulty of equilibrium computation even in markets with only a constant number of goods. Our algorithmic results suggest that finding an approximate equilibrium in markets with hierarchical influence networks might be easier than that in markets with arbitrary neighborhood structures. By demonstrating a simple market with a constant number of goods and a bounded-degree, planar influence graph whose equilibrium is PPAD-hard to approximate, we also provide a counterexample to a common belief, which we refer to as the myth of a constant number of goods, that equilibria in markets with a constant number of goods are easy to compute or easy to approximate.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs

We introduce a new approach to computing an approximately maximum s-t flow in a capacitated, undirected graph. This flow is computed by solving a sequence of electrical flow problems. Each electrical flow is given by the solution of a system of linear equations in a Laplacian matrix, and thus may be approximately computed in nearly-linear time. Using this approach, we develop the fastest known algorithm for computing approximately maximum s-t flows. For a graph having n vertices and m edges, our algorithm computes a (1-ε)-approximately maximum s-t flow in time \tilde{O}(mn^{1/3} ε^{-11/3}). A dual version of our approach computes a (1+ε)-approximately minimum s-t cut in time \tilde{O}(m+n^{4/3}\eps^{-8/3}), which is the fastest known algorithm for this problem as well. Previously, the best dependence on m and n was achieved by the algorithm of Goldberg and Rao (J. ACM 1998), which can be used to compute approximately maximum s-t flows in time \tilde{O}(m\sqrt{n}ε^{-1}), and approximately minimum s-t cuts in time \tilde{O}(m+n^{3/2}ε^{-3}).

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Spectral Sparsification of Graphs

We introduce a new notion of graph sparsificaiton based on spectral similarity of graph Laplacians: spectral sparsification requires that the Laplacian quadratic form of the sparsifier approximate that of the original. This is equivalent to saying that the Laplacian of the sparsifier is a good preconditioner for the Laplacian of the original. We prove that every graph has a spectral sparsifier of nearly linear size. Moreover, we present an algorithm that produces spectral sparsifiers in time $\softO{m}$, where $m$ is the number of edges in the original graph. This construction is a key component of a nearly-linear time algorithm for solving linear equations in diagonally-dominant matrcies. Our sparsification algorithm makes use of a nearly-linear time algorithm for graph partitioning that satisfies a strong guarantee: if the partition it outputs is very unbalanced, then the larger part is contained in a subgraph of high conductance.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

A bounded-degree network formation game

Motivated by applications in peer-to-peer and overlay networks we define and study the \emph{Bounded Degree Network Formation} (BDNF) game. In an $(n,k)$-BDNF game, we are given $n$ nodes, a bound $k$ on the out-degree of each node, and a weight $w_{vu}$ for each ordered pair $(v,u)$ representing the traffic rate from node $v$ to node $u$. Each node $v$ uses up to $k$ directed links to connect to other nodes with an objective to minimize its average distance, using weights $w_{vu}$, to all other destinations. We study the existence of pure Nash equilibria for $(n,k)$-BDNF games. We show that if the weights are arbitrary, then a pure Nash wiring may not exist. Furthermore, it is NP-hard to determine whether a pure Nash wiring exists for a given $(n,k)$-BDNF instance. A major focus of this paper is on uniform $(n,k)$-BDNF games, in which all weights are 1. We describe how to construct a pure Nash equilibrium wiring given any $n$ and $k$, and establish that in all pure Nash wirings the cost of individual nodes cannot differ by more than a factor of nearly 2, whereas the diameter cannot exceed $O(\sqrt{n \log_k n})$. We also analyze best-response walks on the configuration space defined by the uniform game, and show that starting from any initial configuration, strong connectivity is reached within $Θ(n^2)$ rounds. Convergence to a pure Nash equilibrium, however, is not guaranteed. We present simulation results that suggest that loop-free best-response walks always exist, but may not be polynomially bounded. We also study a special family of \emph{regular} wirings, the class of Abelian Cayley graphs, in which all nodes imitate the same wiring pattern, and show that if $n$ is sufficiently large no such regular wiring can be a pure Nash equilibrium.

0 citations0 reviewsNo code linkedOpen access
preprint1999arXiv

Regression Depth and Center Points

We show that, for any set of n points in d dimensions, there exists a hyperplane with regression depth at least ceiling(n/(d+1)). as had been conjectured by Rousseeuw and Hubert. Dually, for any arrangement of n hyperplanes in d dimensions there exists a point that cannot escape to infinity without crossing at least ceiling(n/(d+1)) hyperplanes. We also apply our approach to related questions on the existence of partitions of the data into subsets such that a common plane has nonzero regression depth in each subset, and to the computational complexity of regression depth problems.

0 citations0 reviewsNo code linkedOpen access