BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Yinzhan Xu

Yinzhan Xu contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsComputational ComplexityComputational GeometryComputer Science and Game TheoryCryptography and SecurityMultiagent Systems

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
8works
0followers
6topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

8 published item(s)

preprint2022arXiv

All-Pairs Shortest Path Distances with Differential Privacy: Improved Algorithms for Bounded and Unbounded Weights

We revisit the problem of privately releasing the all-pairs shortest path distances of a weighted undirected graph up to low additive error, which was first studied by Sealfon [Sea16]. In this paper, we improve significantly on Sealfon's results, both for arbitrary weighted graphs and for bounded-weight graphs on $n$ nodes. Specifically, we provide an approximate-DP algorithm that outputs all-pairs shortest path distances up to maximum additive error $\tilde{O}(\sqrt{n})$, and a pure-DP algorithm that outputs all pairs shortest path distances up to maximum additive error $\tilde{O}(n^{2/3})$ (where we ignore dependencies on $\varepsilon, δ$). This improves over the previous best result of $\tilde{O}(n)$ additive error for both approximate-DP and pure-DP [Sea16], and partially resolves an open question posed by Sealfon [Sea16, Sea20]. We also show that if the graph is promised to have reasonably bounded weights, one can improve the error further to roughly $n^{\sqrt{2}-1+o(1)}$ in the approximate-DP setting and roughly $n^{(\sqrt{17}-3)/2 + o(1)}$ in the pure-DP setting. Previously, it was only known how to obtain $\tilde{O}(n^{1/2})$ additive error in the approximate-DP setting and $\tilde{O}(n^{2/3})$ additive error in the pure-DP setting for bounded-weight graphs [Sea16].

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV

The $3$SUM hypothesis, the APSP hypothesis and SETH are the three main hypotheses in fine-grained complexity. So far, within the area, the first two hypotheses have mainly been about integer inputs in the Word RAM model of computation. The "Real APSP" and "Real $3$SUM" hypotheses, which assert that the APSP and $3$SUM hypotheses hold for real-valued inputs in a reasonable version of the Real RAM model, are even more believable than their integer counterparts. Under the very believable hypothesis that at least one of the Integer $3$SUM hypothesis, Integer APSP hypothesis or SETH is true, Abboud, Vassilevska W. and Yu [STOC 2015] showed that a problem called Triangle Collection requires $n^{3-o(1)}$ time on an $n$-node graph. Our main result is a nontrivial lower bound for a slight generalization of Triangle Collection, called All-Color-Pairs Triangle Collection, under the even more believable hypothesis that at least one of the Real $3$SUM, the Real APSP, and the OV hypotheses is true. Combined with slight modifications of prior reductions, we obtain polynomial conditional lower bounds for problems such as the (static) ST-Max Flow problem and dynamic Max Flow, now under the new weaker hypothesis. Our main result is built on the following two lines of reductions. * Real APSP and Real $3$SUM hardness for the All-Edges Sparse Triangle problem. Prior reductions only worked from the integer variants of these problems. * Real APSP and OV hardness for a variant of the Boolean Matrix Multiplication problem. Along the way we show that Triangle Collection is equivalent to a simpler restricted version of the problem, simplifying prior work. Our techniques also have other interesting implications, such as a super-linear lower bound of Integer All-Numbers $3$SUM based on the Real $3$SUM hypothesis, and a tight lower bound for a string matching problem based on the OV hypothesis.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds

The AP-LCA problem asks, given an $n$-node directed acyclic graph (DAG), to compute for every pair of vertices $u$ and $v$ in the DAG a lowest common ancestor (LCA) of $u$ and $v$ if one exists. In this paper we study several interesting variants of AP-LCA, providing both algorithms and fine-grained lower bounds for them. The lower bounds we obtain are the first conditional lower bounds for LCA problems higher than $n^{ω-o(1)}$, where $ω$ is the matrix multiplication exponent. Some of our results include: - In any DAG, we can detect all vertex pairs that have at most two LCAs and list all of their LCAs in $O(n^ω)$ time. This algorithm extends a result of [Kowaluk and Lingas ESA'07] which showed an $\tilde{O}(n^ω)$ time algorithm that detects all pairs with a unique LCA in a DAG and outputs their corresponding LCAs. - Listing $7$ LCAs per vertex pair in DAGs requires $n^{3-o(1)}$ time under the popular assumption that 3-uniform 5-hyperclique detection requires $n^{5-o(1)}$ time. This is surprising since essentially cubic time is sufficient to list all LCAs (if $ω=2$). - Counting the number of LCAs for every vertex pair in a DAG requires $n^{3-o(1)}$ time under the Strong Exponential Time Hypothesis, and $n^{ω(1,2,1)-o(1)}$ time under the $4$-Clique hypothesis. This shows that the algorithm of [Echkardt, Mühling and Nowak ESA'07] for listing all LCAs for every pair of vertices is likely optimal. - Given a DAG and a vertex $w_{u,v}$ for every vertex pair $u,v$, verifying whether all $w_{u,v}$ are valid LCAs requires $n^{2.5-o(1)}$ time assuming 3-uniform 4-hyperclique requires $n^{4 - o(1)}$ time. This defies the common intuition that verification is easier than computation since returning some LCA per vertex pair can be solved in $O(n^{2.447})$ time [Grandoni et al. SODA'21].

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules

We present an almost optimal algorithm for the classic Chamberlin-Courant multiwinner voting rule (CC) on single-peaked preference profiles. Given $n$ voters and $m$ candidates, it runs in almost linear time in the input size, improving the previous best $O(nm^2)$ time algorithm of Betzler et al. (2013). We also study multiwinner voting rules on nearly single-peaked preference profiles in terms of the candidate-deletion operation. We show a polynomial-time algorithm for CC where a given candidate-deletion set $D$ has logarithmic size. Actually, our algorithm runs in $2^{|D|} \cdot poly(n,m)$ time and the base of the power cannot be improved under the Strong Exponential Time Hypothesis. We also adapt these results to all non-constant Thiele rules which generalize CC with approval ballots.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Tight Dynamic Problem Lower Bounds from Generalized BMM and OMv

The main theme of this paper is using $k$-dimensional generalizations of the combinatorial Boolean Matrix Multiplication (BMM) hypothesis and the closely-related Online Matrix Vector Multiplication (OMv) hypothesis to prove new tight conditional lower bounds for dynamic problems. The combinatorial $k$-Clique hypothesis, which is a standard hypothesis in the literature, naturally generalizes the combinatorial BMM hypothesis. In this paper, we prove tight lower bounds for several dynamic problems under the combinatorial $k$-Clique hypothesis. For instance, we show that: * The Dynamic Range Mode problem has no combinatorial algorithms with $\mathrm{poly}(n)$ pre-processing time, $O(n^{2/3-ε})$ update time and $O(n^{2/3-ε})$ query time for any $ε> 0$, matching the known upper bounds for this problem. Previous lower bounds only ruled out algorithms with $O(n^{1/2-ε})$ update and query time under the OMv hypothesis. Other examples include tight combinatorial lower bounds for Dynamic Subgraph Connectivity, Dynamic 2D Orthogonal Range Color Counting, Dynamic 2-Pattern Document Retrieval, and Dynamic Range Mode in higher dimensions. Furthermore, we propose the OuMv$_k$ hypothesis as a natural generalization of the OMv hypothesis. Under this hypothesis, we prove tight lower bounds for various dynamic problems. For instance, we show that: * The Dynamic Skyline Points Counting problem in $(2k-1)$-dimensional space has no algorithm with $\mathrm{poly}(n)$ pre-processing time and $O(n^{1-1/k-ε})$ update and query time for $ε> 0$, even if the updates are semi-online. Other examples include tight conditional lower bounds for (semi-online) Dynamic Klee's measure for unit cubes, and high-dimensional generalizations of Erickson's problem and Langerman's problem.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths

APSP with small integer weights in undirected graphs [Seidel&#39;95, Galil and Margalit&#39;97] has an $\tilde{O}(n^ω)$ time algorithm, where $ω<2.373$ is the matrix multiplication exponent. APSP in directed graphs with small weights however, has a much slower running time that would be $Ω(n^{2.5})$ even if $ω=2$ [Zwick&#39;02]. To understand this $n^{2.5}$ bottleneck, we build a web of reductions around directed unweighted APSP. We show that it is fine-grained equivalent to computing a rectangular Min-Plus product for matrices with integer entries; the dimensions and entry size of the matrices depend on the value of $ω$. As a consequence, we establish an equivalence between APSP in directed unweighted graphs, APSP in directed graphs with small $(\tilde{O}(1))$ integer weights, All-Pairs Longest Paths in DAGs with small weights, approximate APSP with additive error $c$ in directed graphs with small weights, for $c\le \tilde{O}(1)$ and several other graph problems. We also provide fine-grained reductions from directed unweighted APSP to All-Pairs Shortest Lightest Paths (APSLP) in undirected graphs with $\{0,1\}$ weights and $\#_{\text{mod}\ c}$APSP in directed unweighted graphs (computing counts mod $c$). We complement our hardness results with new algorithms. We improve the known algorithms for APSLP in directed graphs with small integer weights and for approximate APSP with sublinear additive error in directed unweighted graphs. Our algorithm for approximate APSP with sublinear additive error is optimal, when viewed as a reduction to Min-Plus product. We also give new algorithms for variants of #APSP in unweighted graphs, as well as a near-optimal $\tilde{O}(n^3)$-time algorithm for the original #APSP problem in unweighted graphs. Our techniques also lead to a simpler alternative for the original APSP problem in undirected graphs with small integer weights.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Faster Dynamic Range Mode

In the dynamic range mode problem, we are given a sequence $a$ of length bounded by $N$ and asked to support element insertion, deletion, and queries for the most frequent element of a contiguous subsequence of $a$. In this work, we devise a deterministic data structure that handles each operation in worst-case $\tilde{O}(N^{0.655994})$ time, thus breaking the $O(N^{2/3})$ per-operation time barrier for this problem. The data structure is achieved by combining the ideas in Williams and Xu (SODA 2020) for batch range mode with a novel data structure variant of the Min-Plus product.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Monochromatic Triangles, Triangle Listing and APSP

One of the main hypotheses in fine-grained complexity is that All-Pairs Shortest Paths (APSP) for $n$-node graphs requires $n^{3-o(1)}$ time. Another famous hypothesis is that the $3$SUM problem for $n$ integers requires $n^{2-o(1)}$ time. Although there are no direct reductions between $3$SUM and APSP, it is known that they are related: there is a problem, $(\min,+)$-convolution that reduces in a fine-grained way to both, and a problem Exact Triangle that both fine-grained reduce to. In this paper we find more relationships between these two problems and other basic problems. Pătraşcu had shown that under the $3$SUM hypothesis the All-Edges Sparse Triangle problem in $m$-edge graphs requires $m^{4/3-o(1)}$ time. The latter problem asks to determine for every edge $e$, whether $e$ is in a triangle. It is equivalent to the problem of listing $m$ triangles in an $m$-edge graph where $m=\tilde{O}(n^{1.5})$, and can be solved in $O(m^{1.41})$ time [Alon et al.&#39;97] with the current matrix multiplication bounds, and in $\tilde{O}(m^{4/3})$ time if $ω=2$. We show that one can reduce Exact Triangle to All-Edges Sparse Triangle, showing that All-Edges Sparse Triangle (and hence Triangle Listing) requires $m^{4/3-o(1)}$ time also assuming the APSP hypothesis. This allows us to provide APSP-hardness for many dynamic problems that were previously known to be hard under the $3$SUM hypothesis. We also consider the previously studied All-Edges Monochromatic Triangle problem. Via work of [Lincoln et al.&#39;20], our result on All-Edges Sparse Triangle implies that if the All-Edges Monochromatic Triangle problem has an $O(n^{2.5-ε})$ time algorithm for $ε>0$, then both the APSP and $3$SUM hypotheses are false. We also connect the problem to other ``intermediate&#39;&#39; problems, whose runtimes are between $O(n^ω)$ and $O(n^3)$, such as the Max-Min product problem.

0 citations0 reviewsNo code linkedOpen access