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

S. Cliff Liu

S. Cliff Liu contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsComputational Complexity

Trust snapshot

Quick read

Trust 15 - UnverifiedVerification L1Unclaimed author
3works
0followers
2topics
1close 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

3 published item(s)

preprint2020arXiv

Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT

We present the current fastest deterministic algorithm for $k$-SAT, improving the upper bound $(2-2/k)^{n + o(n)}$ dues to Moser and Scheder [STOC'11]. The algorithm combines a branching algorithm with the derandomized local search, whose analysis relies on a special sequence of clauses called chain, and a generalization of covering code based on linear programming. We also provide a more ingenious branching algorithm for $3$-SAT to establish the upper bound $1.32793^n$, improved from $1.3303^n$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Simple Concurrent Labeling Algorithms for Connected Components

We study a class of simple algorithms for concurrently computing the connected components of an $n$-vertex, $m$-edge graph. Our algorithms are easy to implement in either the COMBINING CRCW PRAM or the MPC computing model. For two related algorithms in this class, we obtain $Θ(\lg n)$ step and $Θ(m \lg n)$ work bounds. For two others, we obtain $O(\lg^2 n)$ step and $O(m \lg^2 n)$ work bounds, which are tight for one of them. All our algorithms are simpler than related algorithms in the literature. We also point out some gaps and errors in the analysis of previous algorithms. Our results show that even a basic problem like connected components still has secrets to reveal.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Simpler Partial Derandomization of PPSZ for $k$-SAT

We give a simpler derandomization of the best known $k$-SAT algorithm PPSZ [FOCS'97, JACM'05] for $k$-SAT with \emph{sub-exponential} number of solutions. The existing derandomization uses a complicated construction of small sample space, while we only use \emph{hashing}. Our algorithm and theorem also have a nice byproduct: It outperforms the current fastest deterministic $k$-SAT algorithm when the formula has \emph{moderately exponential} number of solutions.

0 citations0 reviewsNo code linkedOpen access