Search for: All records

We investigate the problem of designing differentially private (DP), revenue- maximizing single item auction. Specifically, we consider broadly applicable settings in mechanism design where agents’ valuation distributions are indepen- dent, non-identical, and can be either bounded or unbounded. Our goal is to design such auctions with pure, i.e., (ω, 0) privacy in polynomial time. 

We introduce and study the problem of dueling optimization with a monotone adversary, a generalization of (noiseless) dueling convex optimization. The goal is to design an online algorithm to find a minimizer x* for a function f:X→R, for X \subseteq R^d. In each round, the algorithm submits a pair of guesses x1 and x2, and the adversary responds with any point in the space that is at least as good as both guesses. The cost of each query is the suboptimality of the worst of the two guesses; i.e., max(f(x1) − f(x*),f(x2) − f(x*)). The goal is to minimize the number of iterations required to find an ε-optimal point and to minimize the total cost (regret) of the guesses over many rounds. Our main result is an efficient randomized algorithm for several natural choices of the function f and set X that incurs cost O(d) and iteration complexity O(d log(1/ε)^2). Moreover, our dependence on d is asymptotically optimal, as we show examples in which any randomized algorithm for this problem must incur Ω(d) cost and iteration complexity. 

Quantum Internet has the potential to support a wide range of applications in quantum communication and quantum computing by generating, distributing, and processing quantum information. Generating a long-distance quantum entanglement is one of the most essential functions of a quantum Internet to facilitate these applications. However, entanglement is a probabilistic process, and its success rate drops significantly as distance increases. Entanglement swapping is an efficient technique used to address this challenge. How to efficiently manage the entanglement through swapping is a fundamental yet challenging problem. In this paper, we will consider two swapping methods: (1) BSM: a classic entanglement-swapping method based on Bell State measurements that fuse two successful quantum links, (2) nfusion: a more general and efficient swapping method based on Greenberger-Horne-Zeilinger measurements, capable of fusing n successful quantum links. Our goal is to maximize the entanglement rate for multiple quantum-user pairs over the quantum Internet with an arbitrary topology. We propose efficient entanglement management algorithms that utilized the unique properties of BSM and n-fusion. Evaluation results highlight that our approach outperforms existing routing protocols. 

Projection maintenance is one of the core data structure tasks. Efficient data structures for projection maintenance have led to recent breakthroughs in many convex programming algorithms. In this work, we further extend this framework to the Kronecker product structure. Given a constraint matrix A and a positive semi-definite matrix W∈R^{n×n} with a sparse eigenbasis, we consider the task of maintaining the projection in the form of B^⊤(BB^⊤)^{−1} B, where B=A(W⊗I) or B=A(W^{1/2}⊗W^{1/2}). At each iteration, the weight matrix W receives a low rank change and we receive a new vector h. The goal is to maintain the projection matrix and answer the query B^⊤(BB^⊤)^{−1} Bh with good approximation guarantees. We design a fast dynamic data structure for this task and it is robust against an adaptive adversary. Following the beautiful and pioneering work of [Beimel, Kaplan, Mansour, Nissim, Saranurak and Stemmer, STOC’22], we use tools from differential privacy to reduce the randomness required by the data structure and further improve the running time.