Results 2161 - 2170 of 23899
This talk focuses on one of the most fundamental problems in private computation that arises in many practical scenarios: the Private Linear Computation (PLC) problem. In PLC, the objective is to compute a single linear combination of data items while minimizing the amount of data that needs to be downloaded, all while preserving data access privacy. We discuss several variations of the PLC problem, including different privacy requirements, the use of side information, and single-provider versus multi-provider scenarios. For each case, we present the state-of-the-art achievability schemes, converse proof techniques, and open research problems.
Counting queries are typically made differentially private by adding Laplace noise, but this can be resource-intensive. Robust Gray codes, introduced by Lolck and Pagh (SODA 2024), offer an alternative by achieving differential privacy through binary bitflips. Informally, a robust Gray code is a (binary) Gray code G so that, given a noisy version of the encoding G(j) of an integer j, one can recover j’ that is close to j (with high probability over the noise). In this talk, I will present near-optimal constructions of robust Gray codes with a rate of 1−H2 (p)−ϵ. I will discuss the motivation behind these codes and provide intuition on their construction.
Abstract not available.
A major challenge in quantum computing lies in our ability to efficiently perform computations fault-tolerantly. Schemes for such fault-tolerance often rely on quantum error-correcting codes with two key properties, namely (1) low-weight stabilizers (i.e. parity-checks), and (2) transversal non-Clifford gates (which provide a sort of algebraic structure). Yet these properties have proven difficult to obtain. Indeed, the first asymptotically good codes achieving either property (1) or (2) alone were only recently constructed. Asymptotically good codes achieving both properties simultaneously, which could lead to new fault-tolerance protocols with improved efficiency and error resilience, have remained out of reach.
In this talk, we describe new code constructions providing progress on this problem. We present the first known asymptotically good quantum codes with sublinear-weight checks that support transversal non-Clifford gates. We also obtain new constructions of (nearly) asymptotically good quantum codes with constant or subpolynomial-weight checks that are not based on the lifted/balanced product operation used in prior constructions. Instead, our codes are based on the much more elementary tensor product.
Based on joint work with Venkatesan Guruswami.
We present simple deterministic gap-producing reductions from the canonical NP-hard problem of solving systems of quadratic equations to the approximate versions of the Nearest Codeword Problem and the Minimum Distance Problem—achieving inapproximability within arbitrary constant factors. Our reductions and proofs are short and simple, relying primarily on linear codes in which all codewords have roughly equal weight.
Based on joint work with Vijay Bhattiprolu, Venkat Guruswami, and Euiwoong Lee.