More Like this

1. Dueling Optimization with a Monotone Adversary

   Blum, Avrim; Gupta, Meghal; Li, Gene; Manoj, Naren Sarayu; Saha, Aadirupa; Yang, Yuanyuan (February 2024, The 35th International Conference on Algorithmic Learning Theory (ALT 2024))

   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. 

   more » « less
2. Communication-rounds tradeoffs for common randomness and secret key generation

   Bafna, Mitali; Ghazi, Badih; Golowich, Noah; Sudan, Madhu (January 2019, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms)

   We study the role of interaction in the Common Randomness Generation (CRG) and Secret Key Generation (SKG) problems. In the CRG problem, two players, Alice and Bob, respectively get samples X1, X2, . . . and Y1, Y2, . . . with the pairs (X1, Y1), (X2, Y2), . . . being drawn independently from some known probability distribution μ. They wish to communicate so as to agree on L bits of randomness. The SKG problem is the restriction of the CRG problem to the case where the key is required to be close to random even to an eavesdropper who can listen to their communication (but does not have access to the inputs of Alice and Bob). In this work, we study the relationship between the amount of communication and the number of rounds of interaction in both the CRG and the SKG problems. Specifically, we construct a family of distributions μ = μr,n,L, parametrized by integers r, n and L, such that for every r there exists a constant b = b(r) for which CRG (respectively SKG) is feasible when (Xi, Yi) ~ μr,n,L with r + 1 rounds of communication, each consisting of O(log n) bits, but when restricted to r/2 − 2 rounds of interaction, the total communication must exceed Ω(n/ logb(n)) bits. Prior to our work no separations were known for r ≥ 2. 

   more » « less
3. Graphs with no even holes and no sector wheels are the union of two chordal graphs

   https://doi.org/10.1016/j.ejc.2024.104035  

   Abrishami, Tara; Berger, Eli; Chudnovsky, Maria; Zerbib, Shira (December 2024, European Journal of Combinatorics)

   Sivaraman (2020) conjectured that if G is a graph with no induced even cycle then there exist sets X1,X2⊆V(G) satisfying V(G)=X1∪X2 such that the induced graphs G[X1] and G[X2] are both chordal. We prove this conjecture in the special case where G contains no sector wheel, namely, a pair (H,w) where H is an induced cycle of G and w is a vertex in V(G)∖V(H) such that N(w)∩H is either V(H) or a path with at least three vertices. 

   more » « less
4. Optimally selecting the top k values from X + Y with layer-ordered heaps

   https://doi.org/http://dx.doi.org/10.7717/peerj-cs.501  

   Serang, Oliver (May 2021, PeerJ)

   null (Ed.)

   Selection and sorting the Cartesian sum, X + Y, are classic and important problems. Here, a new algorithm is presented, which generates the top k values of the form Xi+Yj. The algorithm relies on layer-ordered heaps, partial orderings of exponentially sized layers. The algorithm relies only on median-of-medians and is simple to implement. Furthermore, it uses data structures contiguous in memory, cache efficient, and fast in practice. The presented algorithm is demonstrated to be theoretically optimal. 

   more » « less
5. On Differentially Private U Statistics

   Chaudhuri, Kamalika; Loh, Po-Ling; Pandey, Shourya; Sarkar, Purnamrita (July 2024, https://doi.org/10.48550/arXiv.2407.04945)

   We consider the problem of privately estimating a parameter 𝔼[h(X1,…,Xk)], where X1, X2, …, Xk are i.i.d. data from some distribution and h is a permutation-invariant function. Without privacy constraints, standard estimators are U-statistics, which commonly arise in a wide range of problems, including nonparametric signed rank tests, symmetry testing, uniformity testing, and subgraph counts in random networks, and can be shown to be minimum variance unbiased estimators under mild conditions. Despite the recent outpouring of interest in private mean estimation, privatizing U-statistics has received little attention. While existing private mean estimation algorithms can be applied to obtain confidence intervals, we show that they can lead to suboptimal private error, e.g., constant-factor inflation in the leading term, or even Θ(1/n) rather than O(1/n²) in degenerate settings. To remedy this, we propose a new thresholding-based approach using local Hájek projections to reweight different subsets of the data. This leads to nearly optimal private error for non-degenerate U-statistics and a strong indication of near-optimality for degenerate U-statistics. 

   more » « less