More Like this

1. Pseudodeterminism: promises and lowerbounds

   https://doi.org/10.1145/3519935.3520043  

   Dixon, Peter ; Pavan, A. ; Woude, Jason Vander ; Vinodchandran, N. V. ( July 2022 , Symposium on Theory of Computing (STOC))

   Stefano Leonardi and Anupam Gupta (Ed.)

   A probabilistic algorithm A is pseudodeterministic if, on every input, there exists a canonical value that is output with high probability. If the algorithm outputs one of k canonical values with high probability, then it is called a k-pseudodeterministic algorithm. In the study of pseudodeterminism, the Acceptance Probability Estimation Problem (APEP), which is to additively approximate the acceptance probability of a Boolean circuit, is emerging as a central computational problem. This problem admits a 2-pseudodeterministic algorithm. Recently, it was shown that a pseudodeterministic algorithm for this problem would imply that any multi-valued function that admits a k-pseudodeterministic algorithm for a constant k (including approximation algorithms) also admits a pseudodeterministic algorithm (Dixon, Pavan, Vinodchandran; ITCS 2021). The contribution of the present work is two-fold. First, as our main conceptual contribution, we establish that the existence of a pseudodeterministic algorithm for APEP is fundamentally related to the gap between probabilistic promise classes and the corresponding standard complexity classes. In particular, we show the following equivalence: APEP has a pseudodeterministic approximation algorithm if and only if every promise problem in PromiseBPP has a solution in BPP. A conceptual interpretation of this equivalence is that the algorithmic gap between 2-pseudodeterminism and pseudodeterminism is equivalent to the gap between PromiseBPP and BPP. Based on this connection, we show that designing pseudodeterministic algorithms for APEP leads to the solution of some open problems in complexity theory, including new Boolean circuit lower bounds. This equivalence also explains how multi-pseudodeterminism is connected to problems in SearchBPP. In particular, we show that if APEP has a pseudodeterministic algorithm, then every problem that admits a k(n)-pseudodeterministic algorithm (for any polynomial k) is in SearchBPP and admits a pseudodeterministic algorithm. Motivated by this connection, we also explore its connection to probabilistic search problems and establish that APEP is complete for certain notions of search problems in the context of pseudodeterminism. Our second contribution is establishing query complexity lower bounds for multi-pseudodeterministic computations. We prove that for every k ≥ 1, there exists a problem whose (k+1)-pseudodeterministic query complexity, in the uniform query model, is O(1) but has a k-pseudodeterministic query complexity of Ω(n), even in the more general nonadaptive query model. A key contribution of this part of the work is the utilization of Sperner’s lemma in establishing query complexity lower bounds. 

   more » « less
2. Promise Problems Meet Pseudodeterminism

   Dixon, Peter ; Pavan, A. ; Vinodchandran, N. V. ( April 2021 , Electronic colloquium on computational complexity)

   null (Ed.)

   The {\sc Acceptance Probability Estimation Problem} (APEP) is to additively approximate the acceptance probability of a Boolean circuit. This problem admits a probabilistic approximation scheme. A central question is whether we can design a {\em pseudodeterministic} approximation algorithm for this problem: a probabilistic polynomial-time algorithm that outputs a canonical approximation with high probability. Recently, it was shown that such an algorithm would imply that {\em every approximation algorithm can be made pseudodeterministic} (Dixon, Pavan, Vinodchandran; ITCS 2021). The main conceptual contribution of this work is to establish that the existence of a pseudodeterministic algorithm for APEP is fundamentally connected to the relationship between probabilistic promise classes and the corresponding standard complexity classes. In particular, we show the following equivalence: {\em every promise problem in PromiseBPP has a solution in BPP if and only if APEP has a pseudodeterministic algorithm}. Based on this intuition, we show that pseudodeterministic algorithms for APEP can shed light on a few central topics in complexity theory such as circuit lowerbounds, probabilistic hierarchy theorems, and multi-pseudodeterminism. 

   more » « less
3. Learning Neural Networks with Two Nonlinear Layers in Polynomial Time

   Goel, Surbhi ; Klivans, Adam ( June 2019 , Conference on Learning Theory)

   We give a polynomial-time algorithm for learning neural networks with one layer of sigmoids feeding into any Lipschitz, monotone activation function (e.g., sigmoid or ReLU). We make no assumptions on the structure of the network, and the algorithm succeeds with respect to {\em any} distribution on the unit ball in n dimensions (hidden weight vectors also have unit norm). This is the first assumption-free, provably efficient algorithm for learning neural networks with two nonlinear layers. Our algorithm-- Alphatron-- is a simple, iterative update rule that combines isotonic regression with kernel methods. It outputs a hypothesis that yields efficient oracle access to interpretable features. It also suggests a new approach to Boolean learning problems via real-valued conditional-mean functions, sidestepping traditional hardness results from computational learning theory. Along these lines, we subsume and improve many longstanding results for PAC learning Boolean functions to the more general, real-valued setting of {\em probabilistic concepts}, a model that (unlike PAC learning) requires non-i.i.d. noise-tolerance. 

   more » « less
4. On Efficiently Solvable Cases of Quantum k-SAT

   https://doi.org/10.4230/LIPIcs.MFCS.2018.38  

   Aldi, Marco ; De Beaudrap, Marco ; Gharibian, Sevag ; Saeedi, Seyran ( January 2018 , International Symposium on Mathematical Foundations of Computer Science)

   The constraint satisfaction problems k-SAT and Quantum k-SAT (k-QSAT) are canonical NP-complete and QMA_1-complete problems (for k >= 3), respectively, where QMA_1 is a quantum generalization of NP with one-sided error. Whereas k-SAT has been well-studied for special tractable cases, as well as from a parameterized complexity perspective, much less is known in similar settings for k-QSAT. Here, we study the open problem of computing satisfying assignments to k-QSAT instances which have a "matching" or "dimer covering"; this is an NP problem whose decision variant is trivial, but whose search complexity remains open. Our results fall into three directions, all of which relate to the "matching" setting: (1) We give a polynomial-time classical algorithm for k-QSAT when all qubits occur in at most two clauses. (2) We give a parameterized algorithm for k-QSAT instances from a certain non-trivial class, which allows us to obtain exponential speedups over brute force methods in some cases by reducing the problem to solving for a single root of a single univariate polynomial. (3) We conduct a structural graph theoretic study of 3-QSAT interaction graphs which have a "matching". We remark that the results of (2), in particular, introduce a number of new tools to the study of Quantum SAT, including graph theoretic concepts such as transfer filtrations and blow-ups from algebraic geometry; we hope these prove useful elsewhere. 

   more » « less
5. Optimization of crystal packing in semiconducting spin-crossover materials with fractionally charged TCNQ δ− anions (0 δ < 1)

   https://doi.org/10.1039/D1SC02843J  

   Üngör, Ökten ; Choi, Eun Sang ; Shatruk, Michael ( August 2021 , Chemical Science)

   Co-crystallization of the prominent Fe( ii ) spin-crossover (SCO) cation, [Fe(3-bpp) 2 ] 2+ (3-bpp = 2,6-bis(pyrazol-3-yl)pyridine), with a fractionally charged TCNQ δ − radical anion has afforded a hybrid complex [Fe(3-bpp) 2 ](TCNQ) 3 ·5MeCN (1·5MeCN, where δ = −0.67). The partially desolvated material shows semiconducting behavior, with the room temperature conductivity σ RT = 3.1 × 10 −3 S cm −1 , and weak modulation of conducting properties in the region of the spin transition. The complete desolvation, however, results in the loss of hysteretic behavior and a very gradual SCO that spans the temperature range of 200 K. A related complex with integer-charged TCNQ − anions, [Fe(3-bpp) 2 ](TCNQ) 2 ·3MeCN (2·3MeCN), readily loses the interstitial solvent to afford desolvated complex 2 that undergoes an abrupt and hysteretic spin transition centered at 106 K, with an 11 K thermal hysteresis. Complex 2 also exhibits a temperature-induced excited spin-state trapping (TIESST) effect, upon which a metastable high-spin state is trapped by flash-cooling from room temperature to 10 K. Heating above 85 K restores the ground-state low-spin configuration. An approach to improve the structural stability of such complexes is demonstrated by using a related ligand 2,6-bis(benzimidazol-2′-yl)pyridine (bzimpy) to obtain [Fe(bzimpy) 2 ](TCNQ) 6 ·2Me 2 CO (4) and [Fe(bzimpy) 2 ](TCNQ) 5 ·5MeCN (5), both of which exist as LS complexes up to 400 K and exhibit semiconducting behavior, with σ RT = 9.1 × 10 −2 S cm −1 and 1.8 × 10 −3 S cm −1 , respectively. 

   more » « less