More Like this

1. Brief Announcement: Relations Between Space-Bounded and Adaptive Massively Parallel Computations

   https://doi.org/10.4230/LIPIcs.DISC.2023.37  

   Chen, Michael; Pavan, A; Vinodchandran, N V (October 2023, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Oshman, Rotem (Ed.)

   In this work, we study the class of problems solvable by (deterministic) Adaptive Massively Parallel Computations in constant rounds from a computational complexity theory perspective. A language L is in the class AMPC⁰ if, for every ε > 0, there is a deterministic AMPC algorithm running in constant rounds with a polynomial number of processors, where the local memory of each machine s = O(N^ε). We prove that the space-bounded complexity class ReachUL is a proper subclass of AMPC⁰. The complexity class ReachUL lies between the well-known space-bounded complexity classes Deterministic Logspace (DLOG) and Nondeterministic Logspace (NLOG). In contrast, we establish that it is unlikely that PSPACE admits AMPC algorithms, even with polynomially many rounds. We also establish that showing PSPACE is a subclass of nonuniform-AMPC with polynomially many rounds leads to a significant separation result in complexity theory, namely PSPACE is a proper subclass of EXP^{Σ₂^{𝖯}}. 

   more » « less
2. Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling

   Blanca, Antonio; Chen, Zongchen; Štefankovič, Daniel; Vigoda, Eric (August 2023, COLT 2023)

   We study the identity testing problem for high-dimensional distributions. Given as input an explicit distribution μ, an ε>0, and access to sampling oracle(s) for a hidden distribution π, the goal in identity testing is to distinguish whether the two distributions μ and π are identical or are at least ε-far apart. When there is only access to full samples from the hidden distribution π, it is known that exponentially many samples (in the dimension) may be needed for identity testing, and hence previous works have studied identity testing with additional access to various “conditional” sampling oracles. We consider a significantly weaker conditional sampling oracle, which we call the Coordinate Oracle, and provide a computational and statistical characterization of the identity testing problem in this new model. We prove that if an analytic property known as approximate tensorization of entropy holds for an n-dimensional visible distribution μ, then there is an efficient identity testing algorithm for any hidden distribution π using O˜(n/ε) queries to the Coordinate Oracle. Approximate tensorization of entropy is a pertinent condition as recent works have established it for a large class of high-dimensional distributions. We also prove a computational phase transition: for a well-studied class of n-dimensional distributions, specifically sparse antiferromagnetic Ising models over {+1,−1}^n, we show that in the regime where approximate tensorization of entropy fails, there is no efficient identity testing algorithm unless RP=NP. We complement our results with a matching Ω(n/ε) statistical lower bound for the sample complexity of identity testing in the model. 

   more » « less
3. Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization

   https://doi.org/10.1145/3564246.3585246  

   Bun, Mark; Gaboardi, Marco; Hopkins, Max; Impagliazzo, Russell; Lei, Rex; Pitassi, Toniann; Sivakumar, Satchit; Sorrell, Jessica (June 2023, STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing)

   The notion of replicable algorithms was introduced by Impagliazzo, Lei, Pitassi, and Sorrell (STOC’22) to describe randomized algorithms that are stable under the resampling of their inputs. More precisely, a replicable algorithm gives the same output with high probability when its randomness is fixed and it is run on a new i.i.d. sample drawn from the same distribution. Using replicable algorithms for data analysis can facilitate the verification of published results by ensuring that the results of an analysis will be the same with high probability, even when that analysis is performed on a new data set. In this work, we establish new connections and separations between replicability and standard notions of algorithmic stability. In particular, we give sample-efficient algorithmic reductions between perfect generalization, approximate differential privacy, and replicability for a broad class of statistical problems. Conversely, we show any such equivalence must break down computationally: there exist statistical problems that are easy under differential privacy, but that cannot be solved replicably without breaking public-key cryptography. Furthermore, these results are tight: our reductions are statistically optimal, and we show that any computational separation between DP and replicability must imply the existence of one-way functions. Our statistical reductions give a new algorithmic framework for translating between notions of stability, which we instantiate to answer several open questions in replicability and privacy. This includes giving sample-efficient replicable algorithms for various PAC learning, distribution estimation, and distribution testing problems, algorithmic amplification of δ in approximate DP, conversions from item-level to user-level privacy, and the existence of private agnostic-to-realizable learning reductions under structured distributions. 

   more » « less
4. Quantum Computational Advantage with String Order Parameters of One-Dimensional Symmetry-Protected Topological Order

   https://doi.org/https://doi.org/10.1103/PhysRevLett.126.090505  

   Daniel, Austin K; Miyake, Akimasa (March 2021, Physical review letters)

   null (Ed.)

   Nonlocal games with advantageous quantum strategies give arguably the most fundamental demonstration of the power of quantum resources over their classical counterparts. Recently, certain multiplayer generalizations of nonlocal games have been used to prove unconditional separations between limited computational complexity classes of shallow-depth circuits. Here, we show advantageous strategies for these nonlocal games for generic ground states of one-dimensional symmetry-protected topological orders (SPTOs), when a discrete invariant of a SPTO known as a twist phase is nontrivial and -1. Our construction demonstrates that sufficiently large string order parameters of such SPTOs are indicative of globally constrained correlations useful for the unconditional computational separation. 

   more » « less
5. Dynamical Schrödinger Bridge Problems on Graphs

   https://doi.org/10.1007/s10884-021-09977-1  

   Chow, Shui-Nee; Li, Wuchen; Mou, Chenchen; Zhou, Haomin (February 2021, Journal of Dynamics and Differential Equations)

   null (Ed.)

   We study a discrete dynamical Schrödinger bridge problem (SBP) as a dynamical variational problem on a finite graph. We prove that the discrete SBP exists a unique minimizer, which satisfies a boundary value Hamiltonian flow on probability simplex equipped with L2-Wasserstein metric. In our formulation, we establish the connection between discrete SBP problems and Hamiltonian flows. 

   more » « less