The complexity of computing the permanent

Aho, 1974

Bauer, 1973, A note on disjunctive form tautologies, SIGACT News, 52, 17, 10.1145/1811123.1811124

Cook, 1971, The complexity of theorem proving procedures, Proc. 3rd ACM Symp. on Theory of Computing, 151

Gill, 1974, Computational complexity of probabilistic Turing machines, Proc. 6th ACM Symp. on Theory of Computing, 91

Hall, 1956, An algorithm for distinct representatives, Am. Math. Monthly, 63, 716, 10.2307/2309562

Harary, 1973

Hardy, 1960

Hartmanis, 1976, On Isomorphisms and density of NP and other complete sets, Proc. 8th ACM Symp. on Theory of Computing, 30

Herrmann, 1973, On reducibility among combinatorial problems

Hopcroft, 1973, An n52 algorithm for maximum matchings in bipartite graphs, SIAM J. Comput., 2, 225, 10.1137/0202019

Karp, 1972, Reducibility among combinatorial problems

Little, 1975, A characterization of convertible (0, 1)-matrices, J. Combin. Theory, 18, 187, 10.1016/0095-8956(75)90048-9

Marcus, 1961, On the relation between the determinant and the permanent, Illinois J. Math., 5, 376, 10.1215/ijm/1255630882

Meyer, 1972, The equivalence problem for regular expressions with squaring requires exponential space, Proc. 13th Symp. on Switching and Automata Theory, 125, 10.1109/SWAT.1972.29

Muir, 1882, On a class of permanent symmetric functions, Proc. Roy. Soc. Edinburgh, 11, 409, 10.1017/S0370164600047593

Polya, 1913, Aufgabe 424, Arch. Math. Phys., 20, 27

Ryser, 1963, Combinatorial Mathematics, Carus Math. Monograph no. 14

Schnorr, 1976, A lower bound on the number of additions in monotone computations, Theor. Comput. Sci., 2, 305, 10.1016/0304-3975(76)90083-9

Simon, 1975, On some central problems in computational complexity

Simon, 1977, On the difference between one and many, Proc. 4th Colloq. on Automata, Languages and Programming

Stockmeyer, 1977, The polynomial-time hierarchy, Theoret. Comput. Sci., 3, 1, 10.1016/0304-3975(76)90061-X

Strassen, 1969, Gaussian elimination is not optimal, Numer. Math., 13, 354, 10.1007/BF02165411

Valiant, 1974

Valiant, 1976, The relative complexity of checking and evaluating, Information Processing Lett., 5, 20, 10.1016/0020-0190(76)90097-1

L.G. Valiant, The complexity of enumeration and reliability problems, SIAM J. Comput. (to appear).

Diffie, 1976, New directions is cryptography, IEEE. Trans Information Theory, 10.1109/TIT.1976.1055638

Pratt, 1975, Every prime has a succint certificate, SIAM J. Comput., 4, 214, 10.1137/0204018

Rivest, 1977, On digital signatures and public-key cryptosystems