More Like this

1. Positivity of the symmetric group characters is as hard as the polynomial time hierarchy

   Ikenmeyer, Christian; Pak, Igor; Panova, Greta (January 2023, Proceedings of the annual ACMSIAM Symposium on Discrete Algorithms)

   We prove that deciding the vanishing of the character of the symmetric group is C=P-complete. We use this hardness result to prove that the square of the character is not contained in #P, unless the polynomial hierarchy collapses to the second level. This rules out the existence of any (unsigned) combinatorial description for the square of the characters. As a byproduct of our proof we conclude that deciding positivity of the character is PP-complete under many-one reductions, and hence PH-hard under Turing-reductions. 

   more » « less
2. Gap MCSP Is Not (Levin) NP-Complete in Obfustopia

   https://doi.org/10.4230/lipics.ccc.2024.36  

   Mazor, Noam; Pass, Rafael (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Santhanam, Rahul (Ed.)

   We demonstrate that under believable cryptographic hardness assumptions, Gap versions of standard meta-complexity problems, such as the Minimum Circuit Size Problem (MCSP) and the Minimum Time-Bounded Kolmogorov Complexity problem (MKTP) are not NP-complete w.r.t. Levin (i.e., witness-preserving many-to-one) reductions. In more detail: - Assuming the existence of indistinguishability obfuscation, and subexponentially-secure one-way functions, an appropriate Gap version of MCSP is not NP-complete under randomized Levin-reductions. - Assuming the existence of subexponentially-secure indistinguishability obfuscation, subexponentially-secure one-way functions and injective PRGs, an appropriate Gap version of MKTP is not NP-complete under randomized Levin-reductions. 

   more » « less
3. The Minimum Oracle Circuit Size Problem

   https://doi.org/10.1007/s00037-016-0124-0  

   Allender, Eric; Holden, Dhiraj; Kabanets, Valentine (January 2016, computational complexity)

   We consider variants of the Minimum Circuit Size Problem MCSP, where the goal is to minimize the size of oracle circuits computing a given function. When the oracle is QBF, the resulting problem MCSP[superscript]QBF is known to be complete for PSPACE under ZPP reductions. We show that it is not complete under logspace reductions, and indeed it is not even hard for TC[superscript]0 under uniform AC[superscript]0 reductions. We obtain a variety of consequences that follow if oracle versions of MCSP are hard for various complexity classes under different types of reductions. We also prove analogous results for the problem of determining the resource-bounded Kolmogorov complexity of strings, for certain types of Kolmogorov complexity measures. 

   more » « less
4. The Non-Hardness of Approximating Circuit Size

   https://doi.org/10.1007/978-3-030-19955-5_2  

   Allender, Eric; Ilango, Rahul; Vafa, Neekon (January 2021, Theory of computing systems)

   The Minimum Circuit Size Problem (MCSP) has been the focus of intense study recently; MCSP is hard for SZK under rather powerful reductions, and is provably not hard under "local" reductions computable in TIME(n^0.49) . The question of whether MCSP is NP-hard (or indeed, hard even for small subclasses of P) under some of the more familiar notions of reducibility (such as many-one or Turing reductions computable in polynomial time or in AC^0) is closely related to many of the longstanding open questions in complexity theory. All prior hardness results for MCSP hold also for computing somewhat weak approximations to the circuit complexity of a function. Some of these results were proved by exploiting a connection to a notion of time-bounded Kolmogorov complexity (KT) and the corresponding decision problem (MKTP). More recently, a new approach for proving improved hardness results for MKTP was developed, but this approach establishes only hardness of extremely good approximations of the form 1+o(1), and these improved hardness results are not yet known to hold for MCSP. In particular, it is known that MKTP is hard for the complexity class DET under nonuniform AC^0 m-reductions, implying MKTP is not in AC^0[p] for any prime p. It was still open if similar circuit lower bounds hold for MCSP. One possible avenue for proving a similar hardness result for MCSP would be to improve the hardness of approximation for MKTP beyond 1 + o(1) to omega(1), as KT-complexity and circuit size are polynomially-related. In this paper, we show that this approach cannot succeed. More speci cally, we prove that PARITY does not reduce to the problem of computing superlinear approximations to KT-complexity or circuit size via AC^0-Turing reductions that make O(1) queries. This is signi cant, since approximating any set in P/poly AC^0-reduces to just one query of a much worse approximation of circuit size or KT-complexity. For weaker approximations, we also prove non-hardness under more powerful reductions. Our non-hardness results are unconditional, in contrast to conditional results presented in earlier work (for more powerful reductions, but for much worse approximations). This highlights obstacles that would have to be overcome by any proof that MKTP or MCSP is hard for NP under AC^0 reductions. It may also be a step toward con rming a conjecture of Murray and Williams, that MCSP is not NP-complete under logtime-uniform AC0 m-reductions. 

   more » « less
5. A generalized cubic moment and the Petersson formula for newforms

   https://doi.org/10.1007/s00208-018-1745-1  

   Petrow, Ian; Young, Matthew P. (August 2018, Mathematische Annalen)

   Using a cubic moment, we prove a Weyl-type subconvexity bound for the quadratic twists of a holomorphic newform of square-free level, trivial nebentypus, and arbitrary even weight. This generalizes work of Conrey and Iwaniec in that the newform that is being twisted may have arbitrary square-free level, and also that the quadratic character may have even conductor. One of the new tools developed in this paper is a more general Petersson formula for newforms of square-free level. 

   more » « less