article

Counting Complexity of Solvable Black-Box Group Problems

Author:

N. V. VinodchandranAuthors Info & Claims

SIAM Journal on Computing, Volume 33, Issue 4

Pages 852 - 869

https://doi.org/10.1137/S0097539703420651

Published: 01 April 2004 Publication History

Abstract

We place many computational problems over solvable black-box groups in the counting complexity classes SPP or LWPP\@. The classes SPP and LWPP are considered classes of low counting complexity. In particular, SPP is low (powerless when used as oracles) for all gap-definable counting classes (PP\@, C$_=$P\@, Mod$_k$P\@, etc.) and LWPP is low for PP and C$_=$P\@. The results improve the upper bounds for these problems proved in [Arvind and Vinodchandran, Theoret. Comput. Sci., 180 (1997), pp. 17--45], where the authors place these problems in randomized versions of SPP and LWPP. Because of the randomization, upper bounds in that paper implied lowness only for the class PP. The results in this paper favor the belief that these problems are unlikely to be complete for NP.

Cited By

View all

Hemaspaandra EHemaspaandra LSpakowski HWatanabe O(2020)The Robustness of LWPP and WPP, with an Application to Graph Reconstruction Computational Complexity10.1007/s00037-020-00197-529:2Online publication date: 1-Dec-2020
https://dl.acm.org/doi/10.1007/s00037-020-00197-5
Morimae TNishimura HLe Gall F(2017)Modified group non-membership is in promise-awpp relative to group oraclesQuantum Information & Computation10.5555/3179532.317953517:3-4(242-250)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.5555/3179532.3179535
Arvind VKurur P(2006)Graph Isomorphism is in SPPInformation and Computation10.5555/1149028.1709610204:5(835-852)Online publication date: 1-May-2006
https://dl.acm.org/doi/10.5555/1149028.1709610
Show More Cited By

Index Terms

Counting Complexity of Solvable Black-Box Group Problems
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Enumeration
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes

Recommendations

Separating Complexity Classes Using Autoreducibility

A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from exponential space by showing that all Turing complete sets ...
SZK Proofs for Black-Box Group Problems
In this paper we classify several algorithmic problems in group theory in the complexity classes PZK and SZK (problems with perfect/statistical zero-knowledge proofs respectively). Prior to this, these problems were known to be in $\mbox {\rm AM}\cap \...
Impossibility results on weakly black-box hardness amplification
FCT'07: Proceedings of the 16th international conference on Fundamentals of Computation Theory

We study the task of hardness amplification which transforms a hard function into a harder one. It is known that in a high complexity class such as exponential time, one can convert worst-case hardness into average-case hardness. However, in a lower ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIAM Journal on Computing Volume 33, Issue 4

2004

162 pages

ISSN:0097-5397

Issue’s Table of Contents

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 April 2004

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hemaspaandra EHemaspaandra LSpakowski HWatanabe O(2020)The Robustness of LWPP and WPP, with an Application to Graph Reconstruction Computational Complexity10.1007/s00037-020-00197-529:2Online publication date: 1-Dec-2020
https://dl.acm.org/doi/10.1007/s00037-020-00197-5
Morimae TNishimura HLe Gall F(2017)Modified group non-membership is in promise-awpp relative to group oraclesQuantum Information & Computation10.5555/3179532.317953517:3-4(242-250)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.5555/3179532.3179535
Arvind VKurur P(2006)Graph Isomorphism is in SPPInformation and Computation10.5555/1149028.1709610204:5(835-852)Online publication date: 1-May-2006
https://dl.acm.org/doi/10.5555/1149028.1709610
Spakowski HTripathi R(2006)LWPP and WPP are not uniformly gap-definableJournal of Computer and System Sciences10.1016/j.jcss.2006.01.00272:4(660-689)Online publication date: 1-Jun-2006
https://dl.acm.org/doi/10.1016/j.jcss.2006.01.002

Abstract

Cited By

Index Terms

Recommendations

Separating Complexity Classes Using Autoreducibility

SZK Proofs for Black-Box Group Problems

Impossibility results on weakly black-box hardness amplification

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Share

Share this Publication link

Share on social media

Affiliations