14 citations · 63 across the 27 of their papers we have counts for
28 papers
Competitive Auctions with Imperfect Predictions
Pinyan Lu, Zongqi Wan, Jialin Zhang
The competitive auction was first proposed by Goldberg, Hartline, and Wright. In their paper, they introduce the competitive analysis framework of online algorithm designing into t…
Network Inference and Influence Maximization from Samples
Zhijie Zhang, Wei Chen, Xiaoming Sun +1
Influence maximization is the task of selecting a small number of seed nodes in a social network to maximize the influence spread from these seeds. It has been widely investigated…
Quantum Search with Prior Knowledge
Xiaoyu He, Jialin Zhang, Xiaoming Sun
Search-base algorithms have widespread applications in different scenarios. Grover's quantum search algorithms and its generalization, amplitude amplification, provide a quadratic…
Discouraging Pool Block Withholding Attacks in Bitcoins
Zhihuai Chen, Bo Li, Xiaohan Shan +2
The arisen of Bitcoin has led to much enthusiasm for blockchain research and block mining, and the extensive existence of mining pools helps its participants (i.e., miners) gain re…
Optimization from Structured Samples for Coverage Functions
Wei Chen, Xiaoming Sun, Jialin Zhang +1
We revisit the optimization from samples (OPS) model, which studies the problem of optimizing objective functions directly from the sample data. Previous results showed that we can…
Quantum Algorithm for Online Convex Optimization
Jianhao He, Feidiao Yang, Jialin Zhang +1
We explore whether quantum advantages can be found for the zeroth-order online convex optimization problem, which is also known as bandit convex optimization with multi-point feedb…
General Quantum Bernoulli Factory: Framework Analysis and Experiments
Yong Liu, Jiaqing Jiang, Pingyu Zhu +13
The unremitting pursuit for quantum advantages gives rise to the discovery of a quantum-enhanced randomness processing named quantum Bernoulli factory (QBF). This quantum enhanced…
Speedup in Classical Simulation of Gaussian Boson Sampling
Bujiao Wu, Bin Cheng, Jialin Zhang +2
Gaussian boson sampling is a promising model for demonstrating quantum computational supremacy, which eases the experimental challenge of the standard boson-sampling proposal. Here…
Strategyproof Mechanism for Two Heterogeneous Facilities with Constant Approximation Ratio
Minming Li, Pinyan Lu, Yuhao Yao +1
In this paper, we study the two-facility location game on a line with optional preference where the acceptable set of facilities for each agent could be different and an agent's co…
A Quantum-inspired Classical Algorithm for Separable Non-negative Matrix Factorization
Zhihuai Chen, Yinan Li, Xiaoming Sun +2
Non-negative Matrix Factorization (NMF) asks to decompose a (entry-wise) non-negative matrix into the product of two smaller-sized nonnegative matrices, which has been shown intrac…
Cake Cutting on Graphs: A Discrete and Bounded Proportional Protocol
Xiaohui Bei, Xiaoming Sun, Hao Wu +3
The classical cake cutting problem studies how to find fair allocations of a heterogeneous and divisible resource among multiple agents. Two of the most commonly studied fairness c…
Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis
Jiaqing Jiang, Xiaoming Sun, Shang-Hua Teng +3
Decoherence -- in the current physical implementations of quantum computers -- makes depth reduction a vital task in quantum-circuit design. Moore and Nilsson (SIAM Journal of Comp…
Querying a Matrix through Matrix-Vector Products
Xiaoming Sun, David P. Woodruff, Guang Yang +1
We consider algorithms with access to an unknown matrix via matrix-vector products, namely, the algorithm chooses vectors $\mathbf{v}^1, \ldots, \math…
Coreness of Cooperative Games with Truncated Submodular Profit Functions
Wei Chen, Xiaohan Shan, Xiaoming Sun +1
Coreness represents solution concepts related to core in cooperative games, which captures the stability of players. Motivated by the scale effect in social networks, economics and…
Higher order monotonicity and submodularity of influence in social networks: from local to global
Wei Chen, Qiang Li, Xiaohan Shan +2
Kempe, Kleinberg and Tardos (KKT) proposed the following conjecture about the general threshold model in social networks: local monotonicity and submodularity imply global monotoni…
Quantum-to-Quantum Bernoulli Factory
Jiaqing Jiang, Jialin Zhang, Xiaoming Sun
Given a coin with unknown bias , can we exactly simulate another coin with bias ? The exact set of simulable functions has been well characterized 20 years ago. I…
Local unitary classification for sets of generalized Bell states
Bujiao Wu, Jiaqing Jiang, Jialin Zhang +2
In this paper, we study the local unitary classification for pairs (triples) of generalized Bell states, based on the local unitary equivalence of two sets. In detail, we firstly i…
A Linear Algorithm for Finding the Sink of Unique Sink Orientations on Grids
Xiaoming Sun, Jialin Zhang, Zhijie Zhang
An orientation of a grid is called unique sink orientation (USO) if each of its nonempty subgrids has a unique sink. Particularly, the original grid itself has a unique global sink…
Efficient Delivery Policy to Minimize User Traffic Consumption in Guaranteed Advertising
Jia Zhang, Zheng Wang, Qian Li +4
In this work, we study the guaranteed delivery model which is widely used in online display advertising. In the guaranteed delivery scenario, ad exposures (which are also called im…
On the Optimality of Tape Merge of Two Lists with Similar Size
Qian Li, Xiaoming Sun, Jialin Zhang
The problem of merging sorted lists in the least number of pairwise comparisons has been solved completely only for a few special cases. Graham and Karp \cite{taocp} independently…
Cumulative Activation in Social Networks
Xiaohan Shan, Wei Chen, Qiang Li +2
Most studies on influence maximization focus on one-shot propagation, i.e. the influence is propagated from seed users only once following a probabilistic diffusion model and users…
Communities in Preference Networks: Refined Axioms and Beyond
Gang Zeng, Yuyi Wang, Juhua Pu +3
Borgs et al. [2016] investigated essential requirements for communities in preference networks. They defined six axioms on community functions, i.e., community detection rules. Tho…
The Routing of Complex Contagion in Kleinberg's Small-World Networks
Wei Chen, Qiang Li, Xiaoming Sun +1
In Kleinberg's small-world network model, strong ties are modeled as deterministic edges in the underlying base grid and weak ties are modeled as random edges connecting remote nod…
How to select the largest k elements from evolving data?
Qin Huang, Xingwu Liu, Xiaoming Sun +1
In this paper we investigate the top--selection problem, i.e. determine the largest, second largest, ..., and the -th largest elements, in the dynamic data model. In this mod…