15 citations · 39 across the 8 of their papers we have counts for
9 papers
A Faster Algorithm for Pigeonhole Equal Sums
Ce Jin, Hongxun Wu
An important area of research in exact algorithms is to solve Subset-Sum-type problems faster than meet-in-middle. In this paper we study Pigeonhole Equal Sums, a total search prob…
Breaking the Metric Voting Distortion Barrier
Moses Charikar, Prasanna Ramakrishnan, Kangning Wang +1
We consider the following well-studied problem of metric distortion in social choice. Suppose we have an election with voters and candidates located in a shared metric spac…
Faster Matrix Multiplication via Asymmetric Hashing
Ran Duan, Hongxun Wu, Renfei Zhou
Fast matrix multiplication is one of the most fundamental problems in algorithm research. The exponent of the optimal time complexity of matrix multiplication is usually denoted by…
(Fractional) Online Stochastic Matching via Fine-Grained Offline Statistics
Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu
Motivated by display advertising on the internet, the online stochastic matching problem is proposed by Feldman, Mehta, Mirrokni, and Muthukrishnan (FOCS 2009). Consider a stochast…
Oblivious Online Contention Resolution Schemes
Hu Fu, Pinyan Lu, Zhihao Gavin Tang +4
Contention resolution schemes (CRSs) are powerful tools for obtaining "ex post feasible" solutions from candidates that are drawn from "ex ante feasible" distributions. Online cont…
Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions
Lijie Chen, Ce Jin, R. Ryan Williams +1
We consider low-space algorithms for the classic Element Distinctness problem: given an array of input integers with bit-length, decide whether or not all elements…
Fast and Simple Modular Subset Sum
Kyriakos Axiotis, Arturs Backurs, Karl Bringmann +4
We revisit the Subset Sum problem over the finite cyclic group for some given integer . A series of recent works has provided near-optimal algorithms for this pro…
Faster Algorithms for All Pairs Non-decreasing Paths Problem
Ran Duan, Ce Jin, Hongxun Wu
In this paper, we present an improved algorithm for the All Pairs Non-decreasing Paths (APNP) problem on weighted simple digraphs, which has running time $\tilde{O}(n^{\frac{3 + ω}…
A Simple Near-Linear Pseudopolynomial Time Randomized Algorithm for Subset Sum
Ce Jin, Hongxun Wu
Given a multiset of positive integers and a target integer , the Subset Sum problem asks to determine whether there exists a subset of that sums up to . The curre…