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

Paul Liu

Paul Liu contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsDiscrete MathematicsMachine LearningSocial and Information NetworksComputer Science and Game TheoryComputer VisionDistributed, Parallel, and Cluster ComputingInformation Retrievalmath.COMultimediaphysics.soc-ph

Trust snapshot

Quick read

Trust 19 - UnverifiedVerification L1Unclaimed author
5works
0followers
11topics
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

5 published item(s)

preprint2022arXiv

MonoTrack: Shuttle trajectory reconstruction from monocular badminton video

Trajectory estimation is a fundamental component of racket sport analytics, as the trajectory contains information not only about the winning and losing of each point, but also how it was won or lost. In sports such as badminton, players benefit from knowing the full 3D trajectory, as the height of shuttlecock or ball provides valuable tactical information. Unfortunately, 3D reconstruction is a notoriously hard problem, and standard trajectory estimators can only track 2D pixel coordinates. In this work, we present the first complete end-to-end system for the extraction and segmentation of 3D shuttle trajectories from monocular badminton videos. Our system integrates badminton domain knowledge such as court dimension, shot placement, physical laws of motion, along with vision-based features such as player poses and shuttle tracking. We find that significant engineering efforts and model improvements are needed to make the overall system robust, and as a by-product of our work, improve state-of-the-art results on court recognition, 2D trajectory estimation, and hit recognition.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Streaming Submodular Maximization under Matroid Constraints

Recent progress in (semi-)streaming algorithms for monotone submodular function maximization has led to tight results for a simple cardinality constraint. However, current techniques fail to give a similar understanding for natural generalizations, including matroid constraints. This paper aims at closing this gap. For a single matroid of rank $k$ (i.e., any solution has cardinality at most $k$), our main results are: 1) a single-pass streaming algorithm that uses $\widetilde{O}(k)$ memory and achieves an approximation guarantee of $0.3178$, and 2) a multi-pass streaming algorithm that uses $\widetilde{O}(k)$ memory and achieves an approximation guarantee of $(1-1/e - \varepsilon)$ by taking a constant (depending on $\varepsilon$) number of passes over the stream. This improves on the previously best approximation guarantees of $1/4$ and $1/2$ for single-pass and multi-pass streaming algorithms, respectively. In fact, our multi-pass streaming algorithm is tight in that any algorithm with a better guarantee than $1/2$ must make several passes through the stream and any algorithm that beats our guarantee of $1-1/e$ must make linearly many passes (as well as an exponential number of value oracle queries). Moreover, we show how the approach we use for multi-pass streaming can be further strengthened if the elements of the stream arrive in uniformly random order, implying an improved result for $p$-matchoid constraints.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

An Elo-like System for Massive Multiplayer Competitions

Rating systems play an important role in competitive sports and games. They provide a measure of player skill, which incentivizes competitive performances and enables balanced match-ups. In this paper, we present a novel Bayesian rating system for contests with many participants. It is widely applicable to competition formats with discrete ranked matches, such as online programming competitions, obstacle courses races, and some video games. The simplicity of our system allows us to prove theoretical bounds on robustness and runtime. In addition, we show that the system aligns incentives: that is, a player who seeks to maximize their rating will never want to underperform. Experimentally, the rating system rivals or surpasses existing systems in prediction accuracy, and computes faster than existing systems by up to an order of magnitude.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A polynomial lower bound on adaptive complexity of submodular maximization

In large-data applications, it is desirable to design algorithms with a high degree of parallelization. In the context of submodular optimization, adaptive complexity has become a widely-used measure of an algorithm&#39;s &#34;sequentiality&#34;. Algorithms in the adaptive model proceed in rounds, and can issue polynomially many queries to a function $f$ in each round. The queries in each round must be independent, produced by a computation that depends only on query results obtained in previous rounds. In this work, we examine two fundamental variants of submodular maximization in the adaptive complexity model: cardinality-constrained monotone maximization, and unconstrained non-mono-tone maximization. Our main result is that an $r$-round algorithm for cardinality-constrained monotone maximization cannot achieve an approximation factor better than $1 - 1/e - Ω(\min \{ \frac{1}{r}, \frac{\log^2 n}{r^3} \})$, for any $r < n^c$ (where $c>0$ is some constant). This is the first result showing that the number of rounds must blow up polynomially large as we approach the optimal factor of $1-1/e$. For the unconstrained non-monotone maximization problem, we show a positive result: For every instance, and every $δ>0$, either we obtain a $(1/2-δ)$-approximation in $1$ round, or a $(1/2+Ω(δ^2))$-approximation in $O(1/δ^2)$ rounds. In particular (and in contrast to the cardinality-constrained case), there cannot be an instance where (i) it is impossible to achieve an approximation factor better than $1/2$ regardless of the number of rounds, and (ii) it takes $r$ rounds to achieve a factor of $1/2-O(1/r)$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A simple bipartite graph projection model for clustering in networks

Graph datasets are frequently constructed by a projection of a bipartite graph, where two nodes are connected in the projection if they share a common neighbor in the bipartite graph; for example, a coauthorship graph is a projection of an author-publication bipartite graph. Analyzing the structure of the projected graph is common, but we do not have a good understanding of the consequences of the projection on such analyses. Here, we propose and analyze a random graph model to study what properties we can expect from the projection step. Our model is based on a Chung-Lu random graph for constructing the bipartite representation, which enables us to rigorously analyze the projected graph. We show that common network properties such as sparsity, heavy-tailed degree distributions, local clustering at nodes, the inverse relationship between node degree, and global transitivity can be explained and analyzed through this simple model. We also develop a fast sampling algorithm for our model, which we show is provably optimal for certain input distributions. Numerical simulations where model parameters come from real-world datasets show that much of the clustering behavior in some datasets can just be explained by the projection step.

0 citations0 reviewsNo code linkedOpen access