Article

On the hardness of permanent

Authors:

D. SivakumarAuthors Info & Claims

STACS'99: Proceedings of the 16th annual conference on Theoretical aspects of computer science

Pages 90 - 99

Published: 04 March 1999 Publication History

Abstract

We prove that if there is a polynomial time algorithm which computes the permanent of a matrix of order n for any inverse polynomial fraction of all inputs, then there is a BPP algorithm computing the permanent for every matrix. It follows that this hypothesis implies P^#P = BPP. Our algorithm works over any sufficiently large finite field (polynomially larger than the inverse of the assumed success ratio), or any interval of integers of similar range. The assumed algorithm can also be a probabilistic polynomial time algorithm. Our result is essentially the best possible based on any black box assumption of permanent solvers, and is a simultaneous improvement of the results of Gemmell and Sudan [GS92], Feige and Lund [FL92] as well as Cai and Hemachandra [CH91], and Toda (see [ABG90]).

References

[1]

A. Amir, R. Beigel, and W. Gasarch. Some connections between query classes and non-uniform complexity. In Proceedings of the 5th Structure in Complexity Theory, pages 232{243. IEEE Computer Society, 1990.

[2]

S. Ar, R. Lipton, R. Rubinfeld, and M. Sudan. Reconstructing algebraic functions from mixed data. In Proc. 33rd FOCS, pages 503{512, 1992.

Digital Library

[3]

E. Berlekamp and L. Welch. Error correction of algebraic codes. US Patent Number 4, 633, 470.

[4]

J. Cai and L. Hemachandra. A note on enumerative counting. Information Processing Letters, 38(4):215{219, 1991.

Digital Library

[5]

U. Feige and C. Lund. On the hardness of computing permanent of random matrices. In Proceedings of 24th STOC, pages 643{654, 1992.

Digital Library

[6]

P. Gemmell, R. Lipton, R. Rubinfeld, M. Sudan, and A. Wigderson. Self-testing/correcting for polynomials and for approximate functions. In Proceedings of 23rd STOC, pages 32{42, 1991.

Digital Library

[7]

P. Gemmell and M. Sudan. Highly resilient correctors for polynomials. Information Processing Letters, 43:169{174, 1992.

Digital Library

[8]

O. Goldreich and D. Ron and M. Sudan. Chinese remaindering with errors. ECCC Technical Report TR 98-062, October 29, 1998. Available at www.eccc.uni-trier.de.

[9]

R. Impagliazzo and A. Wigderson. Randomness vs Time, Derandomization under a uniform assumption. Manuscript, 1998. To appear in FOCS '98.

Digital Library

[10]

E. Kaltofen. Polynomial factorization 1987{1991. LATIN '92, I. Simon (Ed.), LNCS, vol.583, pp294{313, Springer, 1992.

Digital Library

[11]

C. Lund, L. Fortnow, H. Karloff, and N. Nisan. Algebraic methods for interactive proof systems. In Proceedings of 31st FOCS, pages 2{10, 1990.

Digital Library

[12]

R. Lipton. New directions in testing, In Distributed Computing and Cryptography, volume 2 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 191{202. AMS, 1991

[13]

R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.

Digital Library

[14]

H. J. Ryser. Combinatorial Mathematics. Carus Mathematical Monograph No 14, Math. Assoc. of America, 1963.

[15]

M. Sudan. Maximum likelihood decoding of Reed-Solomon codes. In Proceedings of the 37th FOCS, pages 164{172, 1996.

Digital Library

[16]

S. Toda. On the computational power of PP and ⊕P. In Proceedings of the 30th FOCS, pages 514{519, 1989.

Digital Library

[17]

L. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 47(1):85{93, 1979.

Cited By

Hirahara SShimizu NMarx D(2021)Nearly optimal average-case complexity of counting bicliques under SETHProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458204(2346-2365)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458204
Ji ZJin ZLu PMarx D(2021)Approximating permanent of random matrices with vanishing meanProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458124(959-975)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458124
Ball MRosen ASabin MVasudevan PHatami HMcKenzie PKing V(2017)Average-case fine-grained hardnessProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3055399.3055466(483-496)Online publication date: 19-Jun-2017
https://dl.acm.org/doi/10.1145/3055399.3055466
Show More Cited By

Index Terms

On the hardness of permanent
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on polynomials

Index terms have been assigned to the content through auto-classification.

Recommendations

Using nondeterminism to amplify hardness
STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing

We revisit the problem of hardness amplification in NP, as recently studied by O'Donnell (STOC '02). We prove that if NP has a balanced function f such that any circuit of size s(n) fails to compute f on a 1/poly(n) fraction of inputs, then NP has a ...
Average-case hardness of NP from exponential worst-case hardness assumptions
STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing

A long-standing and central open question in the theory of average-case complexity is to base average-case hardness of NP on worst-case hardness of NP. A frontier question along this line is to prove that PH is hard on average if UP requires (sub-)...
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

cover image Guide Proceedings

STACS'99: Proceedings of the 16th annual conference on Theoretical aspects of computer science

March 1999

582 pages

ISBN:354065691X

Editors:
Christoph Meinel
FB IV - Informatik, Universität Trier, Trier, Germany
,
Sophie Tison
LIFL, Université de Lille I, Bâtiment 3, Villeneuve d'Ascq Cedex, France

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 04 March 1999

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
3
Total Downloads

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

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hirahara SShimizu NMarx D(2021)Nearly optimal average-case complexity of counting bicliques under SETHProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458204(2346-2365)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458204
Ji ZJin ZLu PMarx D(2021)Approximating permanent of random matrices with vanishing meanProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458124(959-975)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458124
Ball MRosen ASabin MVasudevan PHatami HMcKenzie PKing V(2017)Average-case fine-grained hardnessProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3055399.3055466(483-496)Online publication date: 19-Jun-2017
https://dl.acm.org/doi/10.1145/3055399.3055466
Rudra AWootters MShmoys D(2014)Every list-decodable code for high noise has abundant near-optimal rate puncturingsProceedings of the forty-sixth annual ACM symposium on Theory of computing10.1145/2591796.2591797(764-773)Online publication date: 31-May-2014
https://dl.acm.org/doi/10.1145/2591796.2591797
Tassa TMazza AGionis A(2012)k-ConcealmentTransactions on Data Privacy10.5555/2207141.22071425:1(189-222)Online publication date: 1-Apr-2012
https://dl.acm.org/doi/10.5555/2207141.2207142
Hemaspaandra L(2009)SIGACT news complexity theory column 64ACM SIGACT News10.1145/1620491.162050540:3(60-76)Online publication date: 25-Sep-2009
https://dl.acm.org/doi/10.1145/1620491.1620505
Shaltiel RViola ELadner RDwork C(2008)Hardness amplification proofs require majorityProceedings of the fortieth annual ACM symposium on Theory of computing10.1145/1374376.1374461(589-598)Online publication date: 17-May-2008
https://dl.acm.org/doi/10.1145/1374376.1374461
Trevisan LVadhan S(2007)Pseudorandomness and Average-Case Complexity Via Uniform ReductionsComputational Complexity10.1007/s00037-007-0233-x16:4(331-364)Online publication date: 1-Dec-2007
https://dl.acm.org/doi/10.1007/s00037-007-0233-x
Goldreich OVadhan S(2007)Special Issue On Worst-case Versus Average-case Complexity Editors' ForewordComputational Complexity10.1007/s00037-007-0232-y16:4(325-330)Online publication date: 1-Dec-2007
https://dl.acm.org/doi/10.1007/s00037-007-0232-y
Healy AVadhan SViola EBabai L(2004)Using nondeterminism to amplify hardnessProceedings of the thirty-sixth annual ACM symposium on Theory of computing10.1145/1007352.1007389(192-201)Online publication date: 13-Jun-2004
https://dl.acm.org/doi/10.1145/1007352.1007389
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents