Journal of the Association for Computing Machinery Short Title: J. Assoc. Comput. Mach. Publisher: Association for Computing Machinery (ACM), New York, NY ISSN: 0004-5411 Online: http://dl.acm.org/citation.cfm?id=J401 Successor: Journal of the ACM Comments: Journal; No longer indexed Documents Indexed: 1,779 Publications (1955–1995) References Indexed: 15 Publications with 169 References. all top 5 Latest Issues 42, No. 6 (1995) 42, No. 5 (1995) 42, No. 4 (1995) 42, No. 3 (1995) 42, No. 2 (1995) 42, No. 1 (1995) 41, No. 6 (1994) 41, No. 5 (1994) 41, No. 4 (1994) 41, No. 3 (1994) 41, No. 2 (1994) 41, No. 1 (1994) 40, No. 5 (1993) 40, No. 4 (1993) 40, No. 3 (1993) 40, No. 2 (1993) 40, No. 1 (1993) 39, No. 4 (1992) 39, No. 3 (1992) 39, No. 2 (1992) 39, No. 1 (1992) 38, No. 4 (1991) 38, No. 3 (1991) 38, No. 2 (1991) 38, No. 1 (1991) 37, No. 4 (1990) 37, No. 3 (1990) 37, No. 2 (1990) 37, No. 1 (1990) 36, No. 4 (1989) 36, No. 3 (1989) 36, No. 2 (1989) 36, No. 1 (1989) 35, No. 4 (1988) 35, No. 3 (1988) 35, No. 2 (1988) 35, No. 1 (1988) 34 (1987) 33 (1986) 32 (1985) 31 (1984) 30 (1983) 29 (1982) 28 (1981) 27 (1980) 26 (1979) 25 (1978) 24 (1977) 23 (1976) 22 (1975) 21 (1974) 20 (1973) 19 (1972) 18 (1971) 17 (1970) 16 (1969) 15 (1968) 14 (1967) 13 (1966) 12 (1965) 11 (1964) 10 (1963) 9 (1962) 8 (1961) 7 (1960) 6 (1959) 5 (1958) 2 (1955) all top 5 Authors 21 Ginsburg, Seymour 18 Tarjan, Robert Endre 15 Papadimitriou, Christos Harilaos 15 Ullman, Jeffrey David 13 Sethi, Ravi 12 Coffman, Edward Grady jun. 12 Halpern, Joseph Yehuda 12 Lynch, Nancy Ann 12 Yannakakis, Mihalis 11 Galil, Zvi 11 Rosenberg, Arnold Leonard 11 Sahni, Sartaj K. 10 Fagin, Ronald 10 Slagle, James R. 9 Dolev, Danny 9 Harrison, Michael A. 9 Ibarra, Oscar H. 9 Kung, H. T. 9 Winograd, Shmuel 9 Yao, Andrew Chi-Chih 8 Fischer, Michael J. 8 Sagiv, Yehoshua 8 Traub, Joseph Frederick 7 Adiri, Igal 7 Aho, Alfred Vaino 7 Greibach, Sheila A. 7 Hopcroft, John Edward H. 7 Hunt, Harry Bowen III 7 Karp, Richard Manning 7 Konheim, Alan G. 7 Megiddo, Nimrod 7 Salton, Gerard 7 Stockmeyer, Larry J. 7 Towsley, Donald Fred 7 Valiant, Leslie Gabriel 7 Wong, Chak-Kuen 6 Attiya, Hagit 6 Curtis, H. Allen 6 Garey, Michael Randolph 6 Hibbard, Thomas N. 6 Lipton, Richard Jay 6 Meyer, Albert Ronald 6 Mitra, Debasis 5 Brent, Richard Peirce 5 Bruno, John L. 5 Chaitin, Gregory John 5 Dwork, Cynthia 5 Even, Shimon 5 Frederickson, Greg N. 5 Gelenbe, Sami Erol 5 Gonzalez, Teofilo F. 5 Hartmanis, Juris 5 Iglehart, Donald Lee 5 Johnson, Donald B. 5 Kleinrock, Leonard 5 Lamport, Leslie 5 Loveland, Donald W. 5 Manna, Zohar 5 Muntz, Richard R. 5 Pease, Marshall C. III 5 Peleg, David 5 Pippenger, Nicholas J. 5 Preparata, Franco P. 5 Reif, John H. 5 Reischuk, Rüdiger 5 Shostak, Robert E. 5 Upfal, Eli 5 Vardi, Moshe Ya’akov 5 Wagner, Robert A. 5 Wigderson, Avi 4 Baccelli, François Louis 4 Baker, Brenda S. 4 Beeri, Catriel 4 Blum, Manuel 4 Book, Ronald Vernon 4 Brzozowski, Janusz Antoni 4 Chandy, Kanianthra Mani 4 Chazelle, Bernard 4 Ehrenfeucht, Andrzej 4 Fischer, Patrick Carl 4 Fredman, Michael L. 4 Gabow, Harold N. 4 Gill, Arthur 4 Gottlob, Georg 4 Gurari, Eitan M. 4 Hennessy, Matthew C. B. 4 Henschen, Lawrence J. 4 Hirschberg, Daniel S. 4 Hofri, Micha 4 Horowitz, Ellis 4 Ja’Ja’, Joseph F. 4 Johnson, David Stifler 4 Kannan, Ravindran 4 Kosaraju, S. Rao 4 Ladner, Richard E. 4 Lavenberg, Stephen S. 4 Maier, David 4 Mansour, Yishay 4 Mehlhorn, Kurt 4 Merritt, Michael J. ...and 1,683 more Authors all top 5 Fields 1,087 Computer science (68-XX) 154 Numerical analysis (65-XX) 122 Mathematical logic and foundations (03-XX) 119 Operations research, mathematical programming (90-XX) 92 Information and communication theory, circuits (94-XX) 82 Combinatorics (05-XX) 58 Probability theory and stochastic processes (60-XX) 20 Linear and multilinear algebra; matrix theory (15-XX) 19 Number theory (11-XX) 11 Group theory and generalizations (20-XX) 10 Field theory and polynomials (12-XX) 9 Statistics (62-XX) 8 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 7 Convex and discrete geometry (52-XX) 6 Systems theory; control (93-XX) 5 General algebraic systems (08-XX) 5 Approximations and expansions (41-XX) 4 Biology and other natural sciences (92-XX) 3 Order, lattices, ordered algebraic structures (06-XX) 3 Real functions (26-XX) 3 Harmonic analysis on Euclidean spaces (42-XX) 3 Integral equations (45-XX) 3 Calculus of variations and optimal control; optimization (49-XX) 2 History and biography (01-XX) 2 Associative rings and algebras (16-XX) 2 Functions of a complex variable (30-XX) 2 Ordinary differential equations (34-XX) 2 Partial differential equations (35-XX) 2 Operator theory (47-XX) 1 Commutative algebra (13-XX) 1 Nonassociative rings and algebras (17-XX) 1 Integral transforms, operational calculus (44-XX) 1 Geometry (51-XX) 1 General topology (54-XX) 1 Algebraic topology (55-XX) 1 Manifolds and cell complexes (57-XX) 1 Global analysis, analysis on manifolds (58-XX) 1 Mechanics of particles and systems (70-XX) 1 Geophysics (86-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 1,543 Publications have been cited 43,174 times in 31,736 Documents Cited by ▼ Year ▼ Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Zbl 0885.68088 Goemans, Michel X.; Williamson, David P. 699 1995 A machine-oriented logic based on the resolution principle. Zbl 0139.12303 Robinson, J. A. 586 1965 Alternation. Zbl 0473.68043 Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J. 515 1981 A computing procedure for quantification theory. Zbl 0212.34203 Davis, M.; Putnam, H. 411 1960 Theoretical improvements in algorithmic efficiency for network flow problems. Zbl 0318.90024 Edmonds, Jack; Karp, Richard M. 386 1972 Fast probabilistic algorithms for verification of polynomial identities. Zbl 0452.68050 Schwartz, J. T. 363 1980 Impossibility of distributed consensus with one faulty process. Zbl 0629.68027 Fischer, Michael J.; Lynch, Nancy A.; Paterson, Michael S. 360 1985 Confluent reductions: Abstract properties and applications to term rewriting systems. Zbl 0458.68007 Huet, Gerard 353 1980 Optimal order of one-point and multipoint iteration. Zbl 0289.65023 Kung, H. T.; Traub, J. F. 352 1974 Integer programming formulation of traveling salesman problems. Zbl 0100.15101 Miller, C. E.; Tucker, A. W.; Zemlin, R. A. 352 1960 Scheduling algorithms for multiprogramming in a hard-real-time environment. Zbl 0265.68013 Liu, C. L.; Layland, James W. 347 1973 Algebraic laws for nondeterminism and concurrency. Zbl 0629.68021 Hennessy, Matthew; Milner, Robin 341 1985 P-complete approximation problems. Zbl 0348.90152 Sahni, Sartaj; Gonzalez, Teofilo 326 1976 Fibonacci heaps and their uses in improved network optimization algorithms. Zbl 1412.68048 Fredman, Michael L.; Tarjan, Robert Endre 326 1987 Efficient planarity testing. Zbl 0307.68025 Hopcroft, John; Tarjan, Robert 317 1974 Color-coding. Zbl 0885.68116 Alon, Noga; Yuster, Raphael; Zwick, Uri 302 1995 Learnability and the Vapnik-Chervonenkis dimension. Zbl 0697.68079 Blumer, Anselm; Ehrenfeucht, Andrzej; Haussler, David; Warmuth, Manfred K. 299 1989 ’Direct search’ solution of numerical and statistical problems. Zbl 0111.12501 Hooke, R.; Jeeves, T. A. 282 1961 A new approach to the maximum-flow problem. Zbl 0661.90031 Goldberg, Andrew V.; Tarjan, Robert E. 281 1988 The well-founded semantics for general logic programs. Zbl 0799.68045 Van Gelder, Allen; Ross, Kenneth A.; Schlipf, John S. 278 1991 Reaching agreement in the presence of faults. Zbl 0434.68031 Pease, M.; Shostak, R.; Lamport, L. 276 1980 The string-to-string correction problem. Zbl 0278.68032 Wagner, Robert A.; Fischer, Michael J. 264 1974 On context-free languages. Zbl 0154.25801 Parikh, R. J. 262 1966 Fast approximation algorithms for the knapsack and sum of subset problems. Zbl 0345.90049 Ibarra, Oscar H.; Kim, Chul E. 258 1975 The semantics of predicate logic as a programming language. Zbl 0339.68004 van Emden, M. H.; Kowalski, R. A. 256 1976 A theory of communicating sequential processes. Zbl 0628.68025 Brookes, S. D.; Hoare, C. A. R.; Roscoe, A. W. 252 1984 Open, closed, and mixed networks of queues with different classes of customers. Zbl 0313.68055 Baskett, Forest; Chandy, K. Mani; Muntz, Richard R.; Palacios, Fernando G. 248 1975 Approximation algorithms for NP-complete problems on planar graphs. Zbl 0807.68067 Baker, Brenda S. 247 1994 A machine-independent theory of the complexity of recursive functions. Zbl 0155.01503 Blum, Manuel 243 1967 The complexity of propositional linear temporal logics. Zbl 0632.68034 Sistla, A. P.; Clarke, E. M. 234 1985 “Strong” NP-completeness results: Motivation, examples, and implications. Zbl 0379.68035 Garey, M. R.; Johnson, D. S. 233 1978 Institutions: Abstract model theory for specification and programming. Zbl 0799.68134 Goguen, Joseph A.; Burstall, Rod M. 230 1992 A technique for the numerical solution of certain integral equations of the first kind. Zbl 0108.29902 Phillips, D. L. 229 1962 Efficiency of a good but not linear set union algorithm. Zbl 0307.68029 Tarjan, Robert Endre 222 1975 A framework for defining logics. Zbl 0778.03004 Harper, Robert; Honsell, Furio; Plotkin, Gordon 222 1993 Initial algebra semantics and continuous algebras. Zbl 0359.68018 Goguen, J. A.; Thatcher, J. W.; Wagner, E. G.; Wright, J. B. 217 1977 Open shop scheduling to minimize finish time. Zbl 0343.68031 Gonzalez, Teofilo; Sahni, Sartaj 216 1976 A theorem on Boolean matrices. Zbl 0118.33104 Warshall, S. 205 1962 “Sometimes” and “not never” revisited: On branching versus linear time temporal logic. Zbl 0629.68020 Emerson, E. Allen; Halpern, Joseph Y. 204 1986 A theory of program size formally identical to information theory. Zbl 0309.68045 Chaitin, Gregory J. 203 1975 Applying parallel computation algorithms in the design of serial algorithms. Zbl 0627.68034 Megiddo, Nimrod 201 1983 On the structure of polynomial time reducibility. Zbl 0322.68028 Ladner, Richard E. 200 1975 Derivatives of regular expressions. Zbl 0225.94044 Brzozowski, Janusz A. 197 1964 A space-economical suffix tree construction algorithm. Zbl 0329.68042 McCreight, Edward M. 196 1976 Knowledge and common knowledge in a distributed environment. Zbl 0699.68115 Halpern, Joseph Y.; Moses, Yoram 192 1990 Approximation schemes for covering and packing problems in image processing and VLSI. Zbl 0633.68027 Hochbaum, Dorit S.; Maass, Wolfgang 191 1985 On the desirability of acyclic database schemes. Zbl 0624.68087 Beeri, Catriel; Fagin, Ronald; Maier, David; Yannakakis, Mihalis 190 1983 Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Zbl 0799.68101 Goldreich, Oded; Micali, Silvio; Wigderson, Avi 187 1991 On the hardness of approximating minimization problems. Zbl 0814.68064 Lund, Carsten; Yannakakis, Mihalis 181 1994 Iterative procedures for nonlinear integral equations. Zbl 0149.11503 Anderson, D. G. 178 1965 Reversal-bounded multicounter machines and their decision problems. Zbl 0365.68059 Ibarra, Oscar H. 175 1978 Self-adjusting binary search trees. Zbl 0631.68060 Sleator, Daniel Dominic; Tarjan, Robert Endre 168 1985 Algorithms for scheduling independent tasks. Zbl 0326.68024 Sahni, Sartaj K. 166 1976 Linear programming in linear time when the dimension is fixed. Zbl 0637.90064 Megiddo, Nimrod 155 1984 A transformation system for developing recursive programs. Zbl 0343.68014 Burstall, R. M.; Darlington, John 150 1977 A fast direct solution of Poisson’s equation using Fourier analysis. Zbl 0139.10902 Hockney, R. W. 150 1965 Parallel prefix computation. Zbl 0445.68066 Ladner, Richard E.; Fischer, Michael J. 148 1980 Bisimulation can’t be traced. Zbl 0886.68027 Bloom, Bard; Istrail, Sorin; Meyer, Albert R. 146 1995 On communicating finite-state machines. Zbl 0512.68039 Brand, Daniel; Zafiropulo, Pitro 146 1983 The parallel evaluation of general arithmetic expressions. Zbl 0276.68010 Brent, Richard P. 143 1974 Storing a sparse table with O(1) worst case access time. Zbl 0629.68068 Fredman, Michael L.; Komlós, János; Szemerédi, Endre 142 1984 On the length of programs for computing finite binary sequences. Zbl 0158.25301 Chaitin, Gregory J. 141 1966 Dynamic programming treatment of the travelling salesman problem. Zbl 0106.14102 Bellman, Richard 135 1962 Indexed grammars - an extension of context-free grammars. Zbl 0175.27801 Aho, A. V. 135 1968 Complete sets of reductions for some equational theories. Zbl 0479.68092 Peterson, Gerald E.; Stickel, Mark E. 133 1981 Algebraic methods for interactive proof systems. Zbl 0799.68097 Lund, Carsten; Fortnow, Lance; Karloff, Howard; Nisan, Noam 132 1992 A random polynomial-time algorithm for approximating the volume of convex bodies. Zbl 0799.68107 Dyer, Martin; Frieze, Alan; Kannan, Ravi 132 1991 The complexity of some problems on subsequences and supersequences. Zbl 0371.68018 Maier, David 124 1978 The complexity of searching a graph. Zbl 0637.68081 Megiddo, N.; Hakimi, S. L.; Garey, M. R.; Johnson, D. S.; Papadimitriou, C. H. 123 1988 Characterizations of pushdown machines in terms of time-bounded computers. Zbl 0222.02035 Cook, Stephen A. 123 1971 A simple on-line bin-packing algorithm. Zbl 0629.68045 Lee, C. C.; Lee, D. T. 119 1985 The complexity of probabilistic verification. Zbl 0885.68109 Courcoubetis, Costas; Yannakakis, Mihalis 118 1995 Tree-manipulating systems and Church-Rosser theorems. Zbl 0267.68013 Rosen, Barry K. 116 1973 Efficient algorithms for shortest paths in sparse networks. Zbl 0343.68028 Johnson, Donald B. 116 1977 Slowing down sorting networks to obtain faster sorting algorithms. Zbl 1378.68037 Cole, Richard 115 1987 Asynchronous iterative methods for multiprocessors. Zbl 0372.68015 Baudet, Gerard M. 115 1978 Computing partitions with applications to the knapsack problem. Zbl 0329.90046 Horowitz, Ellis; Sahni, Sartaj 114 1974 Complexity of network synchronization. Zbl 0628.68045 Awerbuch, Baruch 113 1985 Constant depth circuits, Fourier transform, and learnability. Zbl 0781.94006 Linial, Nathan; Mansour, Yishay; Nisan, Noam 111 1993 Hard examples for resolution. Zbl 0639.68093 Urquhart, Alasdair 109 1987 Degrees of acyclicity for hypergraphs and relational database schemes. Zbl 0624.68088 Fagin, Ronald 108 1983 A really temporal logic. Zbl 0807.68065 Alur, Rajeev; Henzinger, Thomas A. 108 1994 Inference of reversible languages. Zbl 0485.68066 Angluin, Dana 108 1982 On finding the maxima of a set of vectors. Zbl 0316.68030 Kung, H. T.; Luccio, F.; Preparata, F. P. 105 1975 Exact and approximate algorithms for scheduling nonidentical processors. Zbl 0329.68041 Horowitz, Ellis; Sahni, Sartaj 105 1976 Error analysis of direct methods of matrix inversion. Zbl 0109.09005 Wilkinson, J. H. 105 1961 A decomposition of multidimensional point sets with applications to \(k\)-nearest-neighbors and \(n\)-body potential fields. Zbl 0886.68078 Callahan, Paul B.; Kosaraju, S. Rao 104 1995 Reasoning about knowledge and probability. Zbl 0806.68098 Fagin, Ronald; Halpern, Joseph Y. 101 1994 Contributions to the theory of logic programming. Zbl 0483.68004 Apt, Krzysztof R.; van Emden, M. H. 100 1982 A sufficient condition for backtrack-free search. Zbl 0477.68063 Freuder, Eugene C. 99 1982 A propositional modal logic of time intervals. Zbl 0799.68175 Halpern, Joseph Y.; Shoham, Yoav 98 1991 Computational limitations on learning from examples. Zbl 0662.68086 Pitt, Leonard; Valiant, Leslie G. 97 1988 Numerical inversion of Laplace transforms using a Fourier series approximation. Zbl 0315.65074 Crump, Kenny S. 96 1976 A new method of interpolation and smooth curve fitting based on local procedures. Zbl 0209.46805 Akima, Hiroshi 96 1970 An algorithm for subgraph isomorphism. Zbl 0323.05138 Ullman, J. R. 95 1976 Numerical inversion of Laplace transforms by relating them to the finite Fourier cosine transform. Zbl 0165.51403 Dubner, H.; Abate, J. 95 1968 Confluent and other types of Thue systems. Zbl 0478.68032 Book, Ronald V. 95 1982 Fast decision procedures based on congruence closure. Zbl 0441.68111 Nelson, Greg; Oppen, Derek C. 94 1980 Recontamination does not help to search a graph. Zbl 0768.68048 Lapaugh, Andrea S. 94 1993 Many hard examples for resolution. Zbl 0712.03008 Chvátal, Vašek; Szemerédi, Endre 94 1988 Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Zbl 0885.68088 Goemans, Michel X.; Williamson, David P. 699 1995 Color-coding. Zbl 0885.68116 Alon, Noga; Yuster, Raphael; Zwick, Uri 302 1995 Bisimulation can’t be traced. Zbl 0886.68027 Bloom, Bard; Istrail, Sorin; Meyer, Albert R. 146 1995 The complexity of probabilistic verification. Zbl 0885.68109 Courcoubetis, Costas; Yannakakis, Mihalis 118 1995 A decomposition of multidimensional point sets with applications to \(k\)-nearest-neighbors and \(n\)-body potential fields. Zbl 0886.68078 Callahan, Paul B.; Kosaraju, S. Rao 104 1995 Three logics for branching bisimulation. Zbl 0886.68064 de Nicola, Rocco; Vaandrager, Frits 73 1995 Designing programs that check their work. Zbl 0886.68046 Blum, Manuel; Kannan, Sampath 72 1995 Reasoning about temporal relations: A maximal tractable subclass of Allen’s interval algebra. Zbl 0886.68077 Nebel, Bernhard; Bürckert, Hans-Jürgen 68 1995 On the \(k\)-server conjecture. Zbl 0885.68075 Koutsoupias, Elias; Papadimitriou, Christos H. 66 1995 The complexity of logic-based abduction. Zbl 0886.68121 Eiter, Thomas; Gottlob, Georg 64 1995 A randomized linear-time algorithm to find minimum spanning trees. Zbl 0886.68079 Karger, David R.; Klein, Philip N.; Tarjan, Robert E. 47 1995 Sharing memory robustly in message-passing systems. Zbl 0886.68018 Attiya, Hagit; Bar-Noy, Amotz; Dolev, Danny 44 1995 Las Vegas algorithms for linear and integer programming when the dimension is small. Zbl 0885.65063 Clarkson, Kenneth L. 44 1995 Logical foundations of object-oriented and frame-based languages. Zbl 0885.68054 Kifer, Michael; Lausen, Georg; Wu, James 35 1995 Parametricity and local variables. Zbl 0885.68039 O’Hearn, P. W.; Tennent, R. D. 29 1995 Termination for direct sums of left-linear complete term rewriting systems. Zbl 0885.68093 Toyama, Y.; Klop, J. W.; Barendregt, H. P. 28 1995 On the minimality and global consistency of row-convex constraint networks. Zbl 0885.68087 van Beek, Peter; Dechter, Rina 25 1995 The isomorphism conjecture fails relative to a random oracle. Zbl 0886.68068 Kurtz, Stuart A.; Mahaney, Stephen R.; Royer, James S. 23 1995 On the existence of equilibria in noncooperative optimal flow control. Zbl 0885.68015 Korilis, Yannis A.; Lazar, Aurel A. 21 1995 NP trees and Carnap’s modal logic. Zbl 0886.68069 Gottlob, Georg 17 1995 Eigenvalues and expansion of regular graphs. Zbl 0885.68117 Kahale, Nabil 16 1995 On the impact of forgetting on learning machines. Zbl 0891.68088 Freivalds, Rūsiņš; Kinber, Efim; Smith, Carl H. 16 1995 Online tracking of mobile users. Zbl 0885.68017 Awerbuch, Baruch; Peleg, David 14 1995 A class of logic problems solvable by linear programming. Zbl 0900.03025 Conforti, Michele; Cornuéjols, Gérard 14 1995 Translating default logic into standard autoepistemic logic. Zbl 0884.03025 Gottlob, Georg 13 1995 Equational specifications, complete term rewriting systems, and computable and semicomputable algebras. Zbl 0885.68092 Bergstra, J. A.; Tucker, J. V. 12 1995 Dynamic fault-tolerant clock synchronization. Zbl 0886.68008 Dolev, Danny; Halpern, Joseph Y.; Simons, Barbara; Strong, Ray 10 1995 Computing with faulty shared objects. Zbl 0890.68019 Afek, Yehuda; Greenberg, David S.; Merritt, Michael; Taubenfeld, Gadi 10 1995 Provably correct theories of action. Zbl 0886.68122 Lin, Fangzhen; Shoham, Yoav 6 1995 Deterministic on-line routing on area-universal networks. Zbl 0885.68029 Bay, Paul; Bilardi, Gianfranco 4 1995 Calculating normalization constants of closed queuing networks by numerically inverting their generating functions. Zbl 0885.68026 Choudhury, Gagan L.; Leung, Kin K.; Whitt, Ward 4 1995 Subquadratic zero-knowledge. Zbl 0890.68054 Boyar, Joan; Brassard, Gilles; Peralta, René 4 1995 Planar-adaptive routing: Low-cost adaptive networks for multiprocessors. Zbl 0886.68017 Chien, Andrew A.; Kim, Jae H. 3 1995 Constructing 1-writer multireader multivalued atomic variables from regular variables. Zbl 0886.68019 Haldar, S.; Vidyasankar, K. 3 1995 Nearly optimal algorithms and bounds for multilayer channel routing. Zbl 0886.68021 Berger, Bonnie; Brady, Martin; Brown, Donna; Leighton, Tom 3 1995 Expected deadlock time in a multiprocessing system. Zbl 0885.68040 Compton, Kevin J.; Ravishankar, Chinya 3 1995 On the average communication complexity of asynchronous distributed algorithms. Zbl 0886.68070 Tsitsiklis, John N.; Stamoulis, George D. 2 1995 An optimal service policy for buffer systems. Zbl 0885.68016 Birman, Alexander; Gail, H. Richard; Hantler, Sidney L.; Rosberg, Zvi; Sidi, Moshe 2 1995 A constant-time optimal parallel string-matching algorithm. Zbl 0885.68082 Galil, Zvi 2 1995 Bounds on the speedup and efficiency of partial synchronization in parallel processing systems. Zbl 0886.68020 Chang, C. S.; Nelson, R. 1 1995 A theory of using history for equational systems with applications. Zbl 0885.68128 Verma, Rakesh M. 1 1995 Recoverable sequence transmission protocols. Zbl 0885.68018 Tempero, Ewan D.; Ladner, Richard E. 1 1995 Approximation algorithms for NP-complete problems on planar graphs. Zbl 0807.68067 Baker, Brenda S. 247 1994 On the hardness of approximating minimization problems. Zbl 0814.68064 Lund, Carsten; Yannakakis, Mihalis 181 1994 A really temporal logic. Zbl 0807.68065 Alur, Rajeev; Henzinger, Thomas A. 108 1994 Reasoning about knowledge and probability. Zbl 0806.68098 Fagin, Ronald; Halpern, Joseph Y. 101 1994 Cryptographic limitations on learning Boolean formulae and finite automata. Zbl 0807.68073 Kearns, Michael; Valiant, Leslie 72 1994 Biconnectivity approximations and graph carvings. Zbl 0822.68082 Khuller, Samir; Vishkin, Uzi 48 1994 On binary constraint problems. Zbl 0813.03045 Ladkin, Peter B.; Maddux, Roger D. 41 1994 Linear approximation of shortest superstrings. Zbl 0812.68075 Blum, Avrim; Jiang, Tao; Li, Ming; Tromp, John; Yannakakis, Mihalis 36 1994 Counting networks. Zbl 0813.68050 Aspnes, James; Herlihy, Maurice; Shavit, Nir 26 1994 New approximation algorithms for graph coloring. Zbl 0821.68092 Blum, Avrim 25 1994 On the power of bounded concurrency. I: Finite automata. Zbl 0813.68138 Drusinsky, Doron; Harel, David 23 1994 Equational inference, canonical proofs, and proof orderings. Zbl 0806.68095 Bachmair, Leo; Dershowitz, Nachum 19 1994 Instance complexity. Zbl 0807.68035 Orponen, Pekka; Ko, Ker-I; Schöning, Uwe; Watanabe, Osamu 18 1994 Modular stratification and magic sets for datalog programs with negation. Zbl 0830.68028 Ross, Kenneth A. 16 1994 Learning Boolean formulas. Zbl 0830.68108 Kearns, Michael; Li, Ming; Valiant, Leslie 16 1994 Are wait-free algorithms fast? Zbl 0812.68077 Attiya, Hagit; Lynch, Nancy; Shavit, Nir 15 1994 Mixed integer programming methods for computing nonmonotonic deductive databases. Zbl 0830.68039 Bell, Colin; Nerode, Anil; Ng, Raymond T.; Subrahmanian, V. S. 13 1994 Motion planning in the presence of moving obstacles. Zbl 0812.68115 Reif, John; Sharir, Micha 13 1994 Shortest paths in the plane with polygonal obstacles. Zbl 0814.68129 Storer, James A.; Reif, John H. 12 1994 Probabilistic recurrence relations. Zbl 0830.68046 Karp, Richard M. 11 1994 Average-case analysis of algorithms for matchings and related problems. Zbl 0829.68070 Motwani, Rajeev 10 1994 Faster tree pattern matching. Zbl 0806.68055 Dubiner, Moshe; Galil, Zvi; Magen, Edith 10 1994 The elusive atomic register. Zbl 0806.68025 Singh, Ambuj K.; Anderson, James H.; Gouda, Mohamed G. 10 1994 An analysis of ML typability. Zbl 0806.68016 Kfoury, A. J.; Tiuryn, J.; Urzyczyn, P. 10 1994 Bounds on the time to reach agreement in the presence of timing uncertainty. Zbl 0807.68042 Attiya, Hagit; Dwork, Cynthia; Lynch, Nancy; Stockmeyer, Larry 10 1994 On solving equations and disequations. Zbl 0812.68064 Buntine, Wray L.; Bürckert, Hans-Jürgen 8 1994 Channel routing of multiterminal nets. Zbl 0812.68083 Gao, Shaodi; Kaufmann, Michael 8 1994 Fishspear: A priority queue algorithm. Zbl 0807.68020 Fischer, Michael J.; Paterson, Michael S. 6 1994 On the power of bounded concurrency. II: Pushdown automata. Zbl 0822.68067 Hirst, Tirza; Harel, David 6 1994 Diversity-based inference of finite automata. Zbl 0821.68085 Rivest, Ronald L.; Schapire, Robert E. 6 1994 Computing bounds on steady state availability of repairable computer systems. Zbl 0812.68059 Lui, John C. S.; Muntz, Richard R. 6 1994 Monte Carlo summation and integration applied to multiclass queuing networks. Zbl 0829.68010 Ross, Keith W.; Tsang, Danny H. K.; Wang, Jie 4 1994 The relationship between greedy parsing and symbolwise text compression. Zbl 0812.68071 Bell, Timothy C.; Witten, Ian H. 3 1994 Circumscription with homomorphisms: Solving the equality and counterexample problems. Zbl 0815.68089 Rathmann, Peter K.; Winslett, Marianne; Manasse, Mark 2 1994 Parallel algorithms for evaluating sequences of set-manipulation operations. Zbl 0830.68056 Atallah, Mikhail J.; Goodrich, Michael T.; Kosaraju, S. Rao 2 1994 Tight lower bounds for probabilistic solitude verification on anonymous rings. Zbl 0806.68038 Abrahamson, Karl; Adler, Andrew; Higham, Lisa; Kirkpatrick, David 2 1994 Parallel linear programming in fixed dimension almost surely in constant time. Zbl 0807.90080 Alon, Noga; Megiddo, Nimrod 2 1994 Efficient computation of Fourier inversion for finite groups. Zbl 0832.20027 Rockmore, Daniel N. 2 1994 A single-exponential upper bound for finding shortest paths in three dimensions. Zbl 0814.68079 Reif, John H.; Storer, James A. 1 1994 Optimal algorithms for parallel Givens factorization on a coarse-grained PRAM. Zbl 0802.65024 Cosnard, Michel; Daoudi, El Mostafa 1 1994 Efficient decomposition methods for the analysis of multi-facility blocking models. Zbl 0812.68060 Conway, Adrian E.; Pinsky, Eugene; Tridandapani, Srinivasan 1 1994 A framework for defining logics. Zbl 0778.03004 Harper, Robert; Honsell, Furio; Plotkin, Gordon 222 1993 Constant depth circuits, Fourier transform, and learnability. Zbl 0781.94006 Linial, Nathan; Mansour, Yishay; Nisan, Noam 111 1993 Recontamination does not help to search a graph. Zbl 0768.68048 Lapaugh, Andrea S. 94 1993 Perfectly secure message transmission. Zbl 0774.68017 Dolev, Danny; Dwork, Cynthia; Waarts, Orli; Yung, Moti 91 1993 Atomic snapshots of shared memory. Zbl 0783.68029 Afek, Yehuda; Attiya, Hagit; Dolev, Danny; Gafni, Eli; Merritt, Michael; Shavit, Nir 83 1993 Learning read-once formulas with queries. Zbl 0764.68139 Angluin, Dana; Hellerstein, Lisa; Karpinski, Marek 52 1993 Complexity and algorithms for reasoning about time: A graph-theoretic approach. Zbl 0795.68095 Golumbic, Martin Charles; Shamir, Ron 47 1993 Decidability of bisimulation equivalence for processes generating context-free languages. Zbl 0801.68102 Baeten, J. C. M.; Bergstra, J. A.; Klop, J. W. 41 1993 An algebraic theory of graph reduction. Zbl 0795.68156 Arnborg, Stefan; Courcelle, Bruno; Proskurowski, Andrzej; Seese, Detlef 41 1993 Random walks on weighted graphs and applications to on-line algorithms. Zbl 0785.68071 Coppersmith, Don; Doyle, Peter; Raghavan, Prabhakar; Snir, Marc 30 1993 Knowledge, probability, and adversaries. Zbl 0783.68120 Halpern, Joseph Y.; Tuttle, Mark R. 28 1993 Undecidable optimization problems for database logic programs. Zbl 0785.68021 Gaifman, Haim; Mairson, Harry; Sagiv, Yehoshua; Vardi, Moshe Y. 27 1993 The minimum consistent DFA problem cannot be approximated within any polynomial. Zbl 0774.68084 Pitt, Leonard; Warmuth, Manfred K. 27 1993 Automatic recognition of tractability in inference relations. Zbl 0770.68106 McAllester, David A. 26 1993 Randomized parallel algorithms for backtrack search and branch-and-bound computation. Zbl 0789.68066 Karp, Richard M.; Zhang, Yanjun 18 1993 An algorithm for finding canonical sets of ground rewrite rules in polynomial time. Zbl 0779.68050 Gallier, Jean; Narendran, Paliath; Plaisted, David; Raatz, Stan; Snyder, Wayne 16 1993 Modal nonmonotonic logics: Ranges, characterization, computation. Zbl 0783.68121 Marek, V. Wiktor; Schwarz, Grigori F.; Truszczyński, Mirosław 14 1993 ...and 1443 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 32,051 Authors 116 Ibarra, Oscar H. 94 Kutrib, Martin 80 Jain, Sanjay 76 Epstein, Leah 70 Otto, Friedrich 68 Saurabh, Saket 63 Raynal, Michel 61 Fomin, Fedor V. 55 Aceto, Luca 54 Vardi, Moshe Ya’akov 53 Cordero, Alicia 53 Malcher, Andreas 53 Sharir, Micha 53 Stephan, Frank 53 Torregrosa Sanchez, Juan Ramón 50 Rajsbaum, Sergio 49 Woeginger, Gerhard 47 Ingólfsdóttir, Anna 44 Tarjan, Robert Endre 43 Golovach, Petr A. 43 Wood, Derick 42 Bodlaender, Hans L. 42 Case, John 41 Zehavi, Meirav 40 Argyros, Ioannis Konstantinos 40 Bergstra, Jan A. 40 Book, Ronald Vernon 40 Evans, David John 40 Gottlob, Georg 40 Halpern, Joseph Yehuda 40 Holzer, Markus 40 Strusevich, Vitaly A. 39 Eiter, Thomas 39 Ibaraki, Toshihide 39 Inenaga, Shunsuke 39 Levin, Asaf 39 Okhotin, Alexander 38 Fernau, Henning 38 Lohrey, Markus 38 Montanari, Angelo 37 Chen, Danny Ziyi 37 Engelfriet, Joost 37 Guerraoui, Rachid 37 Iliopoulos, Costas S. 37 Pan, Victor Yakovlevich 37 Peleg, David 36 Goldreich, Oded 36 Meseguer Guaita, José 35 Amir, Amihood 35 Diaconescu, Răzvan 35 Lokshtanov, Daniel 35 Subramani, Krishnan 35 Thilikos, Dimitrios M. 34 Schneider, Carsten 34 Smid, Michiel H. M. 34 Soleymani, Fazlollah 33 Calude, Cristian S. 33 Chen, Jian-er 33 Ésik, Zoltán 33 Galil, Zvi 33 Jansen, Klaus 33 Pelc, Andrzej 33 Reichel, Lothar 33 Wang, Haitao 32 Chan, Timothy Moon-Yew 32 Laporte, Gilbert 32 Narendran, Paliath 32 Rozenberg, Grzegorz 32 Spirakis, Paul G. 31 Behl, Ramandeep 31 Eppstein, David Arthur 31 Inoue, Katsushi 31 Mehlhorn, Kurt 30 Bille, Philip 30 Bozzelli, Laura 30 Chatterjee, Krishnendu 30 Crochemore, Maxime 30 McQuillan, Ian 30 Papadimitriou, Christos Harilaos 30 van Glabbeek, Robert Jan 30 Yang, Boting 29 Agarwal, Pankaj Kumar 29 Bose, Prosenjit K. 29 Culik, Karel II 29 Hemaspaandra, Lane A. 29 Lynch, Nancy Ann 29 Maheshwari, Anil 29 Niedermeier, Rolf 29 Reif, John H. 29 Salomaa, Arto Kustaa 29 Salomaa, Kai T. 29 Tamir, Arie 28 Alon, Noga 28 Arvind, Vikraman 28 Demaine, Erik D. 28 Downey, Rodney Graham 28 Greibach, Sheila A. 28 Kim, Young Ik 28 Kupferman, Orna 28 Lingas, Andrzej ...and 31,951 more Authors all top 5 Cited in 950 Journals 3,267 Theoretical Computer Science 1,287 Information Processing Letters 1,026 Journal of Computer and System Sciences 950 Discrete Applied Mathematics 764 European Journal of Operational Research 743 Information and Computation 701 Algorithmica 559 Artificial Intelligence 405 Computers & Operations Research 359 Acta Informatica 290 Information Sciences 287 International Journal of Foundations of Computer Science 287 Distributed Computing 284 International Journal of Computer Mathematics 271 Mathematical Programming. Series A. Series B 270 Operations Research Letters 269 Applied Mathematics and Computation 267 Journal of Symbolic Computation 266 Journal of Computational and Applied Mathematics 252 Theory of Computing Systems 249 Discrete Mathematics 246 Journal of Automated Reasoning 242 Computers & Mathematics with Applications 230 Linear Algebra and its Applications 228 Annals of Operations Research 222 Mathematical Systems Theory 218 Computing 213 Computational Geometry 212 Annals of Mathematics and Artificial Intelligence 210 Journal of Combinatorial Optimization 188 SIAM Journal on Computing 171 Mathematics of Computation 171 Journal of Discrete Algorithms 163 Networks 163 Numerische Mathematik 154 Discrete & Computational Geometry 149 BIT 137 Real-Time Systems 130 Queueing Systems 129 Logical Methods in Computer Science 123 Computational Complexity 118 Annals of Pure and Applied Logic 117 MSCS. Mathematical Structures in Computer Science 117 Journal of Scheduling 116 Formal Aspects of Computing 112 Numerical Algorithms 110 The Journal of Symbolic Logic 109 Discrete Optimization 107 Pattern Recognition 102 Journal of Computational Physics 102 Theory and Practice of Logic Programming 100 Journal of Complexity 93 Fuzzy Sets and Systems 93 Journal of Global Optimization 93 BIT. Nordisk Tidskrift for Informationsbehandling 88 Calcolo 88 International Journal of Computational Geometry & Applications 87 Journal of Logical and Algebraic Methods in Programming 86 International Journal of Approximate Reasoning 84 Formal Methods in System Design 82 Journal of Optimization Theory and Applications 81 Combinatorica 80 International Journal of Computer & Information Sciences 76 Journal of Combinatorial Theory. Series B 76 The Journal of Logic and Algebraic Programming 74 RAIRO. Informatique Théorique et Applications 70 Journal of Soviet Mathematics 70 Mathematical and Computer Modelling 70 Journal of Cryptology 69 SIAM Journal on Discrete Mathematics 69 Computational Optimization and Applications 65 Automatica 65 Machine Learning 64 Mathematical Programming 64 Random Structures & Algorithms 64 Journal of Applied Non-Classical Logics 62 Applied Numerical Mathematics 62 Journal of Computer Science and Technology 62 Optimization Letters 61 Journal of Mathematical Analysis and Applications 61 RAIRO, Informatique Théorique 61 Studia Logica 59 Journal of Applied Logic 57 Computer Methods in Applied Mechanics and Engineering 57 Cybernetics 57 Applied Mathematical Modelling 57 INFORMS Journal on Computing 56 SIAM Journal on Scientific Computing 55 Kybernetika 55 European Journal of Combinatorics 55 Cybernetics and Systems Analysis 55 International Transactions in Operational Research 54 Journal of Functional Programming 53 Naval Research Logistics 53 International Journal of Production Research 52 Journal of Parallel and Distributed Computing 50 Probability in the Engineering and Informational Sciences 50 ACM Transactions on Computational Logic 49 Mathematics and Computers in Simulation 49 Algorithms ...and 850 more Journals all top 5 Cited in 62 Fields 20,449 Computer science (68-XX) 6,142 Operations research, mathematical programming (90-XX) 3,861 Combinatorics (05-XX) 3,461 Numerical analysis (65-XX) 3,438 Mathematical logic and foundations (03-XX) 1,315 Information and communication theory, circuits (94-XX) 878 Probability theory and stochastic processes (60-XX) 862 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 496 Statistics (62-XX) 479 Linear and multilinear algebra; matrix theory (15-XX) 448 Number theory (11-XX) 416 Biology and other natural sciences (92-XX) 407 Convex and discrete geometry (52-XX) 396 Systems theory; control (93-XX) 340 Group theory and generalizations (20-XX) 290 Order, lattices, ordered algebraic structures (06-XX) 253 Partial differential equations (35-XX) 237 Quantum theory (81-XX) 234 Ordinary differential equations (34-XX) 221 Approximations and expansions (41-XX) 216 Field theory and polynomials (12-XX) 200 Fluid mechanics (76-XX) 190 Category theory; homological algebra (18-XX) 177 Mechanics of deformable solids (74-XX) 165 Calculus of variations and optimal control; optimization (49-XX) 164 Commutative algebra (13-XX) 158 General algebraic systems (08-XX) 136 Algebraic geometry (14-XX) 123 Dynamical systems and ergodic theory (37-XX) 118 Statistical mechanics, structure of matter (82-XX) 114 Integral equations (45-XX) 107 Operator theory (47-XX) 98 Special functions (33-XX) 91 Real functions (26-XX) 85 Functions of a complex variable (30-XX) 85 Integral transforms, operational calculus (44-XX) 83 History and biography (01-XX) 78 Geometry (51-XX) 69 Associative rings and algebras (16-XX) 69 Harmonic analysis on Euclidean spaces (42-XX) 69 General topology (54-XX) 54 General and overarching topics; collections (00-XX) 49 Mechanics of particles and systems (70-XX) 48 Manifolds and cell complexes (57-XX) 43 Difference and functional equations (39-XX) 41 Optics, electromagnetic theory (78-XX) 40 Functional analysis (46-XX) 37 Algebraic topology (55-XX) 37 Geophysics (86-XX) 36 Classical thermodynamics, heat transfer (80-XX) 24 Measure and integration (28-XX) 22 Nonassociative rings and algebras (17-XX) 22 Differential geometry (53-XX) 15 Global analysis, analysis on manifolds (58-XX) 10 Topological groups, Lie groups (22-XX) 10 Sequences, series, summability (40-XX) 9 Relativity and gravitational theory (83-XX) 7 Potential theory (31-XX) 7 Mathematics education (97-XX) 6 Several complex variables and analytic spaces (32-XX) 5 Abstract harmonic analysis (43-XX) 1 Astronomy and astrophysics (85-XX) Citations by Year