research
∙
05/21/2023
Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits
We investigate the online bandit learning of the monotone multi-linear D...
share
research
∙
11/16/2022
Near-Term Quantum Computing Techniques: Variational Quantum Algorithms, Error Mitigation, Circuit Compilation, Benchmarking and Classical Simulation
Quantum computing is a game-changing technology for global academia, res...
research
∙
08/30/2022
Improved Deterministic Algorithms for Non-monotone Submodular Maximization
Submodular maximization is one of the central topics in combinatorial op...
research
∙
05/30/2022
Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets
Multi-arm bandit (MAB) and stochastic linear bandit (SLB) are important ...
research
∙
04/27/2022
Bounded Memory Adversarial Bandits with Composite Anonymous Delayed Feedback
We study the adversarial bandit problem with composite anonymous delayed...
research
∙
03/23/2022
New Distinguishers for Negation-Limited Weak Pseudorandom Functions
We show how to distinguish circuits with log k negations (a.k.a k-monoto...
research
∙
11/12/2021
Moser-Tardos Algorithm: Beyond Shearer's Bound
In a seminal paper (Moser and Tardos, JACM'10), Moser and Tardos develop...
research
∙
09/13/2021
Online Influence Maximization with Node-level Feedback Using Standard Offline Oracles
We study the online influence maximization (OIM) problem in social netwo...
research
∙
07/08/2021
Perfect Sampling for (Atomic) Lovász Local Lemma
We give a Markov chain based perfect sampler for uniform sampling soluti...
research
∙
06/07/2021
Network Inference and Influence Maximization from Samples
Influence maximization is the task of selecting a small number of seed n...
research
∙
09/18/2020
Quantum Search with Prior Knowledge
Search-base algorithms have widespread applications in different scenari...
research
∙
08/16/2020
Discouraging Pool Block Withholding Attacks in Bitcoins
The arisen of Bitcoin has led to much enthusiasm for blockchain research...
research
∙
07/06/2020
Optimization from Structured Samples for Coverage Functions
We revisit the optimization from samples (OPS) model, which studies the ...
research
∙
03/25/2020
Tight Algorithms for the Submodular Multiple Knapsack Problem
Submodular function maximization has been a central topic in the theoret...
research
∙
11/29/2019
Hybrid Decision Trees: Longer Quantum Time is Strictly More Powerful
In this paper, we introduce the hybrid query complexity, denoted as Q(f;...
research
∙
10/28/2019
On the Degree of Boolean Functions as Polynomials over Z_m
Polynomial representations of Boolean functions over various rings such ...
research
∙
07/12/2019
A Quantum-inspired Classical Algorithm for Separable Non-negative Matrix Factorization
Non-negative Matrix Factorization (NMF) asks to decompose a (entry-wise)...
research
∙
07/11/2019
Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis
Due to the decoherence of the state-of-the-art physical implementations ...
research
∙
07/11/2019
Cake Cutting on Graphs: A Discrete and Bounded Proportional Protocol
The classical cake cutting problem studies how to find fair allocations ...
research
∙
06/13/2019
Querying a Matrix through Matrix-Vector Products
We consider algorithms with access to an unknown matrix M∈F^n × d via ma...
research
∙
04/26/2019
Dynamic MCMC Sampling
The Markov chain Monte Carlo (MCMC) methods are the primary tools for sa...
research
∙
04/08/2019
From independent sets and vertex colorings to isotropic spaces and isotropic decompositions
In the 1970's, Lovász built a bridge between graphs and alternating matr...
research
∙
10/09/2018
On the Relationship between Energy Complexity and Other Boolean Function Measures
In this work we investigate into energy complexity, a Boolean function m...
research
∙
06/28/2018
Coreness of Cooperative Games with Truncated Submodular Profit Functions
Coreness represents solution concepts related to core in cooperative gam...
research
∙
04/23/2018
A direct approach to false discovery rates by decoy permutations
The current approaches to false discovery rates (FDRs) in multiple hypot...
research
∙
04/19/2018
Quantum Lovász Local Lemma: Shearer's Bound is Tight
Lovász Local Lemma (LLL) is a very powerful tool in combinatorics and pr...
research
∙
03/02/2018
Higher order monotonicity and submodularity of influence in social networks: from local to global
Kempe, Kleinberg and Tardos (KKT) proposed the following conjecture abou...
research
∙
01/17/2018
Exact quantum query complexity of weight decision problems
The weight decision problem, which requires to determine the Hamming wei...
research
∙
12/28/2017
On the Decision Tree Complexity of String Matching
String matching is one of the most fundamental problems in computer scie...
research
∙
11/23/2016
Efficient Delivery Policy to Minimize User Traffic Consumption in Guaranteed Advertising
In this work, we study the guaranteed delivery model which is widely use...
research
∙
11/22/2016
Randomized Mechanisms for Selling Reserved Instances in Cloud
Selling reserved instances (or virtual machines) is a basic service in c...
research
∙
09/05/2012