Publications by Topic
Numbers reference publication list.
Computational Learning: 41, 45, 49, 50, 61, 62,
Complexity of Counting: 18, 19, 46, 80, 84, 90
Bulk Synchronous Parallelism: 53, 54, 55, 58, 59, 89
Algebraic Complexity: 5, 18, 21, 23, 25, 27, 36, 57, 84
Graph Connectivity and Complexity: 9, 16, 57
Routing, Load - Balancing: 28, 31, 35
Resource Tradeoffs in Computaton: 4, 10, 14
One-way Functions: 7, 44
Boolean Complexity Theory: 10, 17, 33, 39, 43
Probabilistic Analysis, Derandomization: 15,
Holographic Algorithms: 74, 75, 77, 79, 83, 84, 90
Foundations of Artificial Intelligence: 72, 73, 82, 85, 86
Neuroscience: 52, 71, 78, 81, 88
Evolution: 87, 91
Recent Publications (since 2000)
71. Circuits of the Mind, Oxford University Press, (1994, 2000).
72. Robust logics, Artificial Intelligence Journal, 117 (2000) 231-253.
73. A neuroidal architecture for cognitive computation, J. Assoc. Computing Machinery, 47:5 (2000) 854-882.
74. Quantum circuits that can be simulated classically in polynomial time, SIAM J. on Computing, 31:4 (2002) 1229-1254.
75. Expressiveness of matchgates, Theoretical Computer Science, 289:1 (2002) 457-471 (and 299 (2003) 795.
76. Three problems in computer science, J. Assoc. Computing Machinery, 50:1 (2003) 96-99.
77. Holographic algorithms (extended abstract), Proc. 45th Annual IEEE Symposium on Foundations of Computer Science, Oct 17-19, Rome, Italy, (2004). IEEE Press, 306-315.
78. Memorization and association on a realistic neural model, Neural Computation, 17:3 (2005) 527-555.
79. Holographic circuits, Proc. 32nd International Colloquium on Automata, Languages and Programming, July 11-15, Lisbon, Portugal, LNCS, Vol. 3580, (2005), Springer-Verlag, 1-15.
80. Completeness for parity problems, Proc. 11th International Computing and Combinatorics Conference, Aug 16-19, Kunming, China, LNCS, Vol. 3959, (2005), Springer-Verlag, 1-9.
81. A quantitative theory of neural computation, Biological Cybernetics, 95:3 (2006) 205-211.
82. Knowledge infusion, Proc. 21st National Conference on Artificial Intelligence, AAAI06, Jul 16-20, Boston, MA, AAAI Press, (2006), 1546-1551.
83. Accidental algorithms, Proc. 47th Annual IEEE Symposium on Foundations of Computer Science, Oct 22 -24, Berkeley, CA, IEEE Press, (2006), 509-517.
84. Holographic algorithms, SIAM J. on Computing, 37:5 (2008) 1565-1594. (Earlier version: Electronic Colloquium on Computational Complexity, Report TR05-099, (2005).)
85. A first experimental demonstration of massive knowledge infusion, (with Loizos Michael), Proc. 11th International Conference on Principles of Knowledge Representation and Reasoning, Sept. 16-20, 2008, Sydney, Australia, 378-389.
86. Knowledge infusion: In pursuit of robustness in artificial intelligence, Proc 28th Conference on Foundations of Software Technology and Theoretical Computer Science, Dec 9-11, 2008, Bangalore, India, Indian Association for Research in Computing Science, 415-422.
87. Evolvability, J. Assoc. Computing Machinery, 56:1 (2009) 3:1 - 3:21. (Earlier version: Proc. 32nd International Symposium on Mathematical Foundations of Computer Science, Aug. 26-31, Český Krumlov, Czech Republic, LNCS, Vol 4708, (2007) Springer-Verlag, 22-43.)
88. Experience-induced neural circuits that achieve high capacity, (with Vitaly Feldman), Neural Computation, 21:10 (2009) 2715-2754.
89. A bridging model for multi-core computing, Journal of Computer and System Sciences, 77:1 (2011) 154-166 . (Earlier version: Proc. 16th Annual European Symposium on Algorithms, Sept. 15-17, 2008, Karlsruhe, Germany, LNCS, Vol 5193, (2008), Springer-Verlag, 13-28.)
90. Some observations on holographic algorithms, Proc. 9th Latin American Theoretical Informatics Symposium, LATIN 2010: Oaxaca, Mexico, April 19-23, 2010, LNCS, Vol 6034 Springer-Verlag (2010), 577-590.
91. Evolution with drifting targets, (with Varun Kanade and Jennifer Wortman Vaughan), Proc, 23rd Annual Conference on Learning Theory, (COLT 2010).
Articles written before 2000
1. The equivalence problem for deterministic finite-turn pushdown automata. Information and Control, 25, (1974), pp.123-133.
2. Regularity and related problems for deterministic pushdown automata. J. ACM, 22, (1975), pp.1-10.
3. Deterministic one-counter automata, (with M. S. Paterson). J. Computer and System Sciences 10, (1975) pp.340-350.
4. Parallelism in comparison problems. SIAM J. on Computing, 4, (1975), pp.348-355.
5. General context-free recognition in less than cubic time. J. Computer and System Sciences, 10, (1975), pp.308-315.
6. On non-linear lower bounds in computational complexity. Proc. 7th ACM. Symp. on Theory of Computing, Albuquerque, NM, May 5-7, 1975. pp.45-53.
7. Relative complexity of checking and evaluating. Information Processing Letters, 5 (1976), pp.20-23.
8. Shifting graphs and their applications, (with N. J. Pippenger). J. ACM 23 (1976), pp.423-432.
9. Graph theoretic properties in computational complexity. J. Computer and System Sciences, 13, (1976), pp.278-285.
10. Circuit size is non-linear in depth, (with M. S. Paterson). Theoretical Computer Science, 2 (1976) pp.397-400.
11. The equivalence problem for DOL systems and its decidability for binary alphabets.; In Automata, Languages and Programming, (S. Michaelson and R. Milner, eds.), Edinburgh University Press (1976), pp.31-37.
12. Space time tradeoffs in computation. Asterisque 38, (1976), pp. 253-264.
13. A note on the succinctness of descriptions of deterministic languages. Information and Control 32, (1976), pp.139-145.
14. On time versus space, (with J. E. Hopcroft and W. J. Paul). J. ACM 24, (1977), pp.332-337.
15. Fast probabilistic algorithms for Hamiltonian circuits and matchings, (with D. Angluin). J. Computer and System Sciences, 18: 2, (1979), pp.155-193.
16. Graph theoretic arguments in low-level complexity. Lecture Notes in Computer Science, 53, Springer Verlag (1977), pp.162-176.
17. Universal circuits. Proc. 8th ACM. Symp. on Theory of Computing, Hershey, PA, May (1976), pp.196-203.
18. The complexity of computing the permanent. Theoretical Computer Science, 8 (1979), pp. 189-201.
19. The complexity of enumeration and reliability problems. SIAM J. Computing, 8:3 (1979), pp.410-421.
20. The complexity of combinatorial computations. In GI8 Jahrestagung Informatik, Fachbereichte Band 16, (S. Schindler and W. K. Giloi, eds.) Springer-Verlag (1978), pp.326-337.
21. Completeness classes in algebra. Proc. 11th ACM. Symp. on Theory of Computing, Atlanta, GA, April 30 - May 2, 1979. pp. 249-261.
22. Negative results on counting. Lecture Notes in Computer Science, 67, Springer-Verlag (1979), pp. 38-46.
23. Negation can be exponentially powerful. Theoretical Computer Science 12 (1980), pp.303-314.
24. A fast parallel algorithm for routing in permutation networks. (with G. Lev and N. J. Pippenger), IEEE Trans. on Computers C-30, 2 (1981), pp.93-100.
25. Computing multivariate polynomials in parallel. Information Processing Letters, 11:1 (1980), pp. 44-45 and 12:1 (1981), p. 54.
26. Universality considerations in VLSI circuits. IEEE Trans. on Computers C-30:2 (1981), pp. 135-140.
27. Reducibility by algebraic projections. Monographie No. 30 de L'Enseignement Mathematique: Logic and Algorithmic, Geneva (1982),pp.365-380.
28. A scheme for fast parallel communication. SIAM J. Computing, 11: 2 (1982), 350-361.
29. Experiments with a parallel communication scheme. Proc. 18th Allerton Conference on Communication Control and Computing, University of Illinois (1980), pp. 802-811.
30. Size bounds for superconcentrators, (with G. Lev). Theoretical Computer Science 22, 3 (1983), pp.233-252.
31. Universal schemes for parallel communication, (with G. J. Brebner). Proc. 13th ACM. Symp. on Theory of Computing, Milwaukee, IL, May 11-13, 1981, pp.263-277.
32. Fast parallel computation of polynomials using few processors, (with S. Skyum). Lecture Notes in Computer Science, 118, Springer Verlag (1981), pp.132-139.
33. A complexity theory based on Boolean algebra, (with S. Skyum). J. ACM 32: 2 (1985) pp.484-502.
34. Parallel computation. Proc. of 7th IBM Symp. on Mathematical Foundations of Computer Science, Hakone, Japan, May 24-26, 1982, pp.171-189.
35. Optimality of a two-phase strategy for routing in interconnection network. IEEE Trans. on Computers, C-32:9 (1983), pp.861-863.
36. Fast parallel computation of polynomials using few processors, (with S. Skyum, S. Berkowitz and C. Rackoff). SIAM J. Computing, 12:4 (1983), pp.641-644.
37. A logarithmic time sort on linear size networks, (with J. H. Reif). J. ACM. 34:1 (1987) 60-76.
38. Exponential lower bounds for restricted monotone circuits. Proc. 15th ACM. Symp. on Theory of Computing, Boston, MA, April 25-27, 1983. pp.110-117.
39. Short monotone formulae for the majority function. J. Algorithms 5 (1984), pp.363-366.
40. An algebraic approach to computational complexity. Proc. International Congress of Mathematicians, August 1983. Polish Scientific Publishers, Warsaw, and Elsevier Science Publishers, Amsterdam, Vol. 2, pp. 1637-1644
41. A theory of the learnable. C.ACM 27:11 (1984) pp.1134-1142.
42. Deductive learning. Phil. Trans. R. Soc. Lond. A 312 (1984), pp.441-446. (Also in Mathematical Logic and Programming Languages, C. A. R. Hoare and J. C. Shepherdson, eds. Prentice-Hall, Englewood Cliffs, NJ. (1985), pp. 107-112.
43. Negation is powerless for Boolean slice functions. SIAM J. Computing. 15:2 (1986) 531-535.
44. NP is as easy as detecting single solutions. (with V. V. Vazirani) Theoretical Computer . 47 (1986) 85-93.
45. Learning disjunctions of conjunctions. Proc. Ninth International Joint Conferences on Artificial Intelligence, Los Angeles, CA (August 1985) pp. 560-566.
46. Random generation of combinatorial structures from a uniform distribution. (with M. R. Jerrum and V. V. Vazirani). Theoretical Computer Science 43 (1986) 169-188.
47. On the learnability of Boolean formulae. (with M. Kearns, M. Li, and L. Pitt) Proc. 19th ACM Symp. on Theory of Computing, New York, NY, May 25-27 (1987) 285-295.
48. Recent results on Boolean concept learning. (with M. Kearns, M. Li and L. Pitt) Proc 4th Int. Workshop on Machine Learning, Morgan Kaufmann, Los Altos, CA (1987) 337-352.
49. Computational limitations on learning from examples, (with L. Pitt). J. ACM, 35:4 (1988) 965-984.
50. A general lower bound on the number of examples needed for learning. (with A. Ehrenfeucht, D. Haussler and M. Kearns) Inf. and Computation. 82:2 (1989) 247-261.
51. Optimally universal parallel computers. Phil. Trans. R. Soc. London. A326 (1988) 373-376.
52. Functionality in neural nets. Proc. American Association for Artificial Intelligence 1988, Morgan Kaufmann, San Mateo, CA, (1988) 629-634.
53. Bulk-synchronous parallel computers. In Parallel Processing and Artificial Intelligence. (M. Reeve and S. Zenith, eds.), John Wiley and Sons, (1989) 15-22.
54. General purpose parallel architectures. In Handbook of Theoretical Computer Science (J. van Leeuwen, ed.), North Holland, Amsterdam (1990) pp. 944-971.
55. A bridging model for parallel computation. C.ACM, 33:8 (1990) pp. 103-111.
56. A view of computational learning theory. In Computation and Cognition (C.W. Gear, ed.), Soc. Ind. and Appl. Math., Philadelphia, (1990) 32-53.
57. Why is Boolean complexity theory difficult? In Boolean Function Complexity, (M.S. Paterson, ed.), London Mathematical Society Lecture Note Series, Cambridge University Press, 169 (1992) 84-94.
58. Direct bulk-synchronous parallel algorithms. (with A.V. Gerbessiotis.) J. of Parallel and Distributed Computing, 22 (1994) 251-267.
59. A combining mechanism for parallel computers. In Parallel Architectures and Their Efficient Use. Lecture Notes in Computer Science vol. 678, Springer-Verlag, (1993) 1-10.
60. Why BSP computers? In Proc 7th International Parallel Processing Symposium, IEEE Computer Society Press, Los Alamitos, CA (1993) 2-5.
61. Cryptographic limitations on learning Boolean formulae and finite automata. (with M. Kearns) J. ACM, 41:1 (1994) 67-95. (Preliminary version in Proc. 21st ACM Symp. on Theory of Computing , ACM Press, New York, NY. (1989) 433-444.)
62. Learning Boolean formulas (with M. Kearns and M. Li).J.ACM, 41:6 (1994) 1298-1328.
63. A neuroidal model for cognition. In Natural and Artificial Parallel Computation, (D.L. Waltz, ed.) Soc. Ind. and Appl. Math., Philadelphia, (1995) 127-140.
64. Bulk-synchronous parallel computing - a paradigm for transportable software. (with T. Cheatham, A. Fahmy, and D. Stefanescu.) In Proc. 28th Hawaii International Conference on System Science, Wailea, Maui, Hawaii, Jan 3-6 (1995).
65. Rationality. Proc. 8th ACM Workshop on Computational Learning Theory, ACM Press, (1995), 3-14.
66. Some theoretical questions in neuroscience, In Cortical Dynamics in Jerusalem (M. Abeles and H. Sompolinsky, eds.), The Hebrew University Center for Neural Computation, (1995) 793-798.
67. Cognitive computation. Proc. 36th IEEE Symp. on Foundations of Computer Science, IEEE Press, (1995) 2-3.
68. Managing complexity in neuroidal circuits. In Algorithmic Learning Theory (S. Arikawa and A.K. Sharma, eds.) Lecture Notes in Artificial Intelligence, Vol. 1160, Springer Verlag, Berlin 1996, pp. 1-11.
69. Relational learning for NLP using linear threshold elements. (with R. Khardon and D. Roth), In Proc Sixteenth International Joint Conferences on Artificial Intelligence, IJCAI 1999, Stockholm, Sweden, July 1999. Morgan Kaufmann, 911-917
70. Projection learning. Machine Learning 37:2 (1999)115-130.
