Michael Sipser
- Aj83.M. AJTAI, #-formulae on finite structures, Annals of Pure and Applied Logic 24, 1-48, 1983.Google Scholar
Cross Ref
- AB87.N. ALON AND P#. B. BOPPANA, The monotone circuit complexity of Boolean functions, Combinatorica 7:1, 1-22, 1987. Google ScholarDigital Library
- An85.A.E. ANDREEV, On a method for obtaining lower bounds for the complexity of individual monotone functions, Doklady Akademii Nauk SSSR 282:5, 1033-1037 (in Russian). English translation in Soviet Mathematics DoUady 31:3, 530-534, 1985.Google Scholar
- As55.G. ASSER, Das Repr#entatenproblem im PrKdikatenkalkiil der ersten Stufe mit identit#t, Zeitschrift fiir Matemitische Logic und Grundlagen der Mathematik, 1, 252-263, 1955.Google Scholar
- BGS75.T. P. BAKER, J. GILL, AND R. SOLOVAY, Relativizations of the P=?NP question, SIAM Journal on Computing 4:4, 431-442, 1975.Google ScholarCross Ref
- Ba86a.D.A. BARRINGTOI#, Bounded-width polynomial-size branching programs recognize exactly those languages in NC1, Journal of Computer and System Sciences 38, 150-164, 1986. Google ScholarDigital Library
- Ba86a.D.A. BARRINQTON, A note on a theorem of Razborov, manuscript, 1986.Google Scholar
- BH91.S. BEN-DAVID AND S. HALEVI, On the independence of P versus NP, Tech. Report #699, Technion, 1991.Google Scholar
- Be82.S.J. BERKOWITZ, On some relationships between monotone and non-monotone circuit complexity, Technical Report, Computer Science Department, University of Toronto, 1982.Google Scholar
- Bl67.M. BLUM, A machine-independent theory of the complexity of recursive functions, Journal of the A CM, 14, no. 2, 322-336, 1967. Google ScholarDigital Library
- Bl84.N. BLUM, A Boolean function requiring 3n network size, Theoretical Computer Science 28, 337-345, 1984.Google ScholarCross Ref
- Bo86.R.B. BOPPANA, Threshold functions and bounded depth monotone circuits, Journal of Computer and System Sciences 32:2,222-229, 1986. Google ScholarDigital Library
- BS90.R.S. BOPPANA AND M. SIPSER, The complexity of finite functions, Handbook of Theoretical Computer Science, Elsevier, 758-804, 1990. Google ScholarDigital Library
- Bu86.S.R. Buss, Bounded Arilhmetic, Bibliopolis, 1986.Google Scholar
- Co64.A. COBHAM, The intrinsic computational difficulty of functions, Proc. of the 196# international Congress for Logic, Methodology, and lhe Philosophy of Science, edited by Y. Bar- Hillel, North-Holland, 24-30, 1964.Google Scholar
- CSV84.A. K. CHANDRA, L. J. STOCKMEYER, AND U. VISHKIN, Constant depth reducibility, SIAM Journal on Compufiug 13:2, 423-439, 1984.Google ScholarCross Ref
- Co71.S.A. COOK, The complexity of theorem proving procedures, Proceedings of #he 3rd Annual A CM Symposium on Theory of Computing, 151-158, 1971. Google ScholarDigital Library
- Co75.S.A. CooK, Feasably constructive proofs and the propositional calculus, Proceedings of the 7th Annual A CM Symposium on Theory of Computing, 83-97, 1975. Google ScholarDigital Library
- CU88.S.A. COOK AND A. URQUHART, Functional interpretations of feasibly constructive arithmetic, Technical Report 210/88, Computer Science Department, University of Toronto, 1988.Google Scholar
- DL79.R.E. DEMILLO AND R. J. LIPTON, The consistency of P--NP and related problems within fragments of number theory, Proceedings of #he 11th ACM Symposium on Theory of Computing, 153-159, 1979. Google ScholarDigital Library
- Du88.P.E. DUNNE, The Complexity of Boolean Networks, Academic Press, 1988. Google ScholarDigital Library
- Ed65.J. EDMONDS, Paths, trees, and flowers, Canadian Journal of Mathematics, 17, 449- 467, 1965.Google ScholarCross Ref
- Ed65b.J. EDMONDS, Minimum partition of a matroid into independent sets, Journal of Research of the National Bureau of Standards (B), 69, 67-72,Google Scholar
- EIRS91.J. EDMONDS, R. IMPAGLIAZZO, S. RUI)ICH, J. SGALL, Communication complexity towards lower bounds on circuit depth, Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 249-257, 1991. Google ScholarDigital Library
- Fa74.R. FAaIN, Generalized first-order spectra and polynomial-time recognizable sets, Complexity of Computation, SIAM-AMS Proceedings 7, 43-73, 1974.Google Scholar
- FS88.L. FORTNOW AND M. SIPSER, Are there interactive protocols for eo-NP languages7 Information Processing Letters 28, 249--251, 1988. Google ScholarDigital Library
- FSS84.M. FURST, J. SAX#., AND M. SIr'SER, Parity, circuits and the polynomial time hierarchy, Mathematical Systems Theory 17, 13-27, 1984.Google ScholarCross Ref
- Ga77.Z. GALm, On the complexity of regular resolution and the Davis-Putnam procedure, Theoretical Computer Science 4, 23-46, 1977.Google ScholarCross Ref
- GJ79.M. GAR#.Y AND D. S. JOHNSON, Computers and Intractability: a guide to the theory of NP-completeness, Freeman, 1979. Google ScholarDigital Library
- GH89.M. Goldmann, J. Hhstad, A lower bound for monotone clique using a communication game, manuscript, 1989.Google Scholar
- GS90.M. GRIGNI AND M. SIPSER, Monotone complexity, Proceedings of LMS workshop on Boolean Function Complexity, Durham, edited by M. S. Paterson, Cambridge University Press, 1990. Google ScholarDigital Library
- GS91.M. GrUGNI AND M. SIPSZR, Monotone separation of N C1 from logspaee, Proceedings of the 6th Annual Symposium on Structure in Complexity Theory, 294-298, 1991.Google Scholar
- HS72.L.H. HARPER AND J. E. SAVAGE, The complexity of the marriage problem, Advances in Mathematics 9, 299-312, 1972.Google ScholarCross Ref
- Ha89.J. HARTMANIS, GSdel, von Neumann and the P=?NP Problem, Bulletin of the European Association for Theoretical Computer Science, 101-107, June 1989.Google Scholar
- HH76.j. HARTMANIS AND j. HOPCROFT, Independence results in computer science, A CM SIGACT News 8, no. 4, 13-24, 1976. Google ScholarDigital Library
- HS65.J. HARTMANIS AND P#. E. STEARNS, On the computational complexity of algorithms, Transactions of the AMS 117, 285-306, 1965.Google ScholarCross Ref
- Ha85.A. HAKe, N, The intractability of resolution, Theoretical Computer Science 39, 297-308, 1985.Google ScholarCross Ref
- Hå86.J. HASTAD, Computational Limitations for Small Depth Circuits, MIT Press, 1986. Google ScholarDigital Library
- HW91.J. H),STAD, A. WmD#.RSON, Composition of the Universal Relation, manuscript, 1991.Google Scholar
- HU79.J.E. HOPCROFT AND J. D. ULLMAN, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979. Google ScholarDigital Library
- Im87.i. IMMERMAN, Languages that capture complexity classes, SIAM Journal on Computing 16:4, 760-778, 1987. Google ScholarDigital Library
- Im88.N. IMMERMAN, Nondeterministic space is closed under complement, SIAM Journal on Computing, 935-938, 1988. Google ScholarDigital Library
- JS74.N.D. JONES AND A. L. SELMAN, Turing machines and the spectra of first-order formulas, Journal of Symbolic Logic 39, 139-150, 1974.Google ScholarCross Ref
- KS87.B. KALYANASUNDARAM AND G. SCHNIT- GER, The probabilistic communication complexity of set intersection, Proceedings of #he Second Annual Conference on Structure in Complexity Theory, 41-49, 1987.Google Scholar
- KRW91.M. KARCHMER, R. RAZ, A. WIGDERSON, On proving super-logarithmic depth lower bounds via the direct sum in communication complexity, Proceedings of the Sixth Annual Conference on Structure in Complexity Theory, 1991.Google ScholarCross Ref
- KW88.M. KARCHMER AND A. WIGDERSON, Monotone circuits for connectivity require superlogarithmic depth, Proceedings of the 20th Annual A CM Symposium on Theory of Computing, 539-550, 1988. Google ScholarDigital Library
- Ka72.R.M. KARP, Reducibility among combinatorim problems, Complexity of Computer Computations, Plenum Press, 85-103, 1972.Google Scholar
- Ko77.D. KOZEN, Lower bounds for natural proof systems, Proceedings of the 18th Annual Symposium on Foundations of Computer Science, 254-266, 1977.Google Scholar
- LJK87.K. J. LANGE, B. JENNER, B, KIRSIG, The logarithmic hierarchy collapses: AEL = AII#, Proceedings of the 14th International Conference on Automata, Languages, and Programming, 1987. Google ScholarDigital Library
- Le05.H. L#.B#.SGU#., Sur les fonetions repr#sentables analytiquement, Journal de Math. 6# serie 1, 139-216, 1905.Google Scholar
- Le73.L. LEVIN, Universal sequential search problems, Probl. Pered. Inform. IX 3, 1973; translation in Problems of Information Trans 9, 3, 265--266; corrected translation in Trakhtenxbrot {Tr84}.Google Scholar
- Li78.R.J. LIPTON, Model theoretic aspects of complexity theory, Proceeding of the 19th Annual Symposium on Foundations of Computer Science, 193-200, 1978.Google Scholar
- LFKN90.C. LUND, L. FORTNOW, H. KARLOFF, AND N. NISAN, Algebraic methods for interactive proof systems, Proceedings of 2#h Annual ACM Symposium on Theory of Computing, 2-10, 1990; to appear in the Journal of the A CM. Google ScholarDigital Library
- MS72.A. R,. MEYER, AND L. J. STOCKMEYER, The equivalence problem for regular expressions with squaring requires exponential time, Proceedings of #he 13th Annual Symposium on Switching and Automata Theory, 125-129, 1972.Google ScholarDigital Library
- Mo80.Y.N. MOSCHOVAKIS, Descriptive Set Theory, North-Holland, 1980.Google Scholar
- Mu56.D. E. MULLER, Complexity in electronic switching circuits, IRE Transactions on Electronic Computers 5, 15-19, 1956.Google ScholarCross Ref
- Pa76.M. S. PATERSON, An introduction to Boolean function complexity, Astgrisque 38- 39, 183-201, 1976.Google Scholar
- Ra60.M.O. I#BIN, Degree of diflieutly of computing a function and a partial ordering of reeursive sets, Teeh. Rep. No. 2, Hebrew University, 1960.Google Scholar
- Ra66.M.O. tL#BIN, Mathematical theory of automata, Proceedings of 19th A CM Symposium in Applied Mathematics, 153-175, 1966.Google Scholar
- RW90.R. R#z AND A. WmD#.RSON, Monotone circuits for matching require linear depth, Proceedings of the #nd Annual A CM Symposium on Theory of Computing, 287-292, 1990. Google ScholarDigital Library
- Ra85a.A. A. RAZBOROV, A lower bound on the monotone network complexity of the logical permanent, Matematicheskie gametki 37:6, 887-900 (in Russian). En/#lish translation in Mathematical Notes of the Academy of Sciences of the USSR 37:6, 485-493, 1985.Google Scholar
- Ra85b.A. A. RAZBOROV, A lower bound on the monotone network complexity of the logical permanent, Matema#icheskie Zametki 37:6, 887-900 (in Russian). English translation in Mathematical Notes of the Academy of Sciences of the USSR 37:6, 485--493, 1985.Google Scholar
- Ra87.A.A. RAZBOROV, Lower bounds on the size of bounded depth networks over a complete basis with logical addition, Matematicheskie Zametki 41:4, 598-607 (in Russian). English translation in Mathematical Notes of the Academy of Sciences of the USSR 41:4, 333- 338, 1987.Google Scholar
- Ra89.A.A. RAZBOROV, On the method of approximations, Proceedings of the 21st Annual A CM Symposium on Theory of Computing, 168-176, 1989. Google ScholarDigital Library
- Ra90a.A.A. tLAZBOROV, On the distributional complexity of disjointness, Proceeding of the International Conference on Automata, Languages, and Computation, 1990; to appear in Theoretical Computer Science. Google ScholarDigital Library
- Ra90b.A. A. RAZBOROV, Applications of matrix methods for the theory of lower bounds in computational complexity, Combinalorica 10, 81-93, 1990.Google ScholarCross Ref
- Sa72.J.E. SAVAGE, Computational work and time on finite machines, Journal of the ACM 19:4, 660-674, 1972. Google ScholarDigital Library
- Sa80.V.Y. SAZANOV, A logical approach to the problem "P=NP?" Mathematical Foundations of Computer Science, Lecture notes in Computer Science #88, 562-575, 1980. Google ScholarDigital Library
- Sc52.H. SCHOLZ, Problem #1, Journal of Symbolic Logic, 17, 160, 1952.Google ScholarCross Ref
- Sh90.A. SHAMm, IP=PSPACE, Proceedings of 2#th Annual A CM Symposium on Theory of Computing, 11-15, 1990; to appear in the Journal of the A CM. Google ScholarDigital Library
- Sh49.C.E. SHANNON, The synthesis of twoterminal switching circuits, Bell Systems Technical Journal 28:1, 59-98, 1949.Google ScholarCross Ref
- Si81.M. SIPSZR, On polynomial vs. exponential growth, unpubfished, 1981.Google Scholar
- Si83.M. SIPS#R, Borel sets and circuit complexity, Proceedings of 15th Annual A CM Symposium on Theory of Computing, 61-69, 1983. Google ScholarDigital Library
- Si84.M. SIPSER, A topological view of some problems in complexity theory, Colloquia Mathematica Societatis Jdno8 Bolyai 44, 387-391, 1984.Google Scholar
- Sm87.R. SMOLENSKY, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, Proceedings of lgth Annual A CM Symposium on Theory of Computing, 77-82, 1987. Google ScholarDigital Library
- Sz88.R. SZZLEPCSk.NYI, The method of forced enumeration for nondeterministic automata, Acta Informatica 26, 279-284, 1988. Google ScholarDigital Library
- Ta88.TARDOS, The gap between monotone and non-monotone circuit complexity is exponential, Combinatorica 8:1, 141-142, 1988.Google ScholarCross Ref
- Tr84.B.A. TRAKHTBNBROT, A survey of Russian approaches to Perebor (brute-force search) algorithms, Annals of the History of Computing 6, no. 4, 384-400, 1984.Google ScholarDigital Library
- Ts62.G.S. TSI#ITIN, On the complexity of derivation in propositional calculus, Studies in Constructive Mathematics and Mathematical Logic, Part 2, Consultants Bureau, New Youk-London, 115-125, 1962.Google Scholar
- Va90.L.G. VALIANT, Why is Boolean complexity theory difficult? Proceedings of LMS workshop on Boolean Function Complezity, Durham, edited by M. S. Paterson, Cambridge University Press, 1990. Google ScholarDigital Library
- Vo53.J. VON NEUMANN, A certain zero-sum twoperson game equivalent to the optimal assignment problem, Contributions to the Theory of Games $, 5-12, 1953.Google Scholar
- We87.I. W}#GENER, The Complexity of Boolean Functions, Wiley-Teubner, 1987. Google ScholarDigital Library
- Ya59a.S. YABLONSKI, The algorithmic difficulties of synthesizing minimal switching circuits, Prob. lemy Kibernetiki 2, Moscow, Fizmatgiz, 75- 121, 1959; translation in Problems of Cybernetics 2, Pergamon Press, 401-457, 1961.Google Scholar
- Ya59b.S. YABLONSKI, On the impossibility of eliminating brute force search in solving some problems of circuit theory, Doklady, AN SSSR 124, 44-47, 1959.Google Scholar
- Ya85.A.C. YAO, Separating the polynomial-time hierarchy by oracles, Proceedings of 26th Annual IEEE Symposium on Foundations of Computer Science, 1-10, 1985. Google ScholarDigital Library
Index Terms
- The history and status of the P versus NP question
Recommendations
On the P versus NP intersected with co-NP question in communication complexity
We consider the analog of the P versus NP@?co-NP question for the classical two-party communication protocols where polynomial time is replaced by poly-logarithmic communication: if both a boolean function f and its negation @?f have small (poly-...
Comments