Edit Profile (opens in new tab) Tompa, Martin Co-Author Distance Author ID: tompa.martin Published as: Tompa, Martin External Links: MGP Documents Indexed: 28 Publications since 1978 1 Further Contribution Co-Authors: 25 Co-Authors with 21 Joint Publications 1,593 Co-Co-Authors all top 5 Co-Authors 8 single-authored 7 Borodin, Allan B. 5 Ruzzo, Walter L. 3 Beame, Paul W. 3 Raghavan, Prabhakar 2 Cook, Stephen Arthur 2 Dymond, Patrick W. 2 Fagin, Ronald 2 Fischer, Michael J. 2 Lynch, Nancy Ann 2 Manber, Udi 2 Simon, Janos 2 Tiwari, Prasoon 1 Alon, Noga 1 Angluin, Dana 1 Bloniarz, Peter A. 1 Brent, Richard Peirce 1 Brown, Donna J. 1 Buss, Jonathan F. 1 Carlson, David A. 1 Chandra, Ashok K. 1 Chazelle, Bernard 1 Colbourn, Charles J. 1 Coppersmith, Don 1 Cypher, A. 1 DeMillo, Richard Allan 1 Dobkin, David P. 1 Ehrig, Hartmut 1 Fich, Faith Ellen 1 Filotti, I. S. 1 Frederickson, Greg N. 1 Guibas, Leonidas John 1 Heintz, Joos 1 Hoffmann, Christoph M. 1 Hong, Jiawei 1 Hopcroft, John Edward H. 1 Ibarra, Oscar H. 1 Ja’Ja’, Joseph F. 1 Johnson, Donald B. 1 Joseph, Deborah 1 Kannan, Ravindran 1 Karp, Richard Manning 1 Kirkpatrick, David G. 1 Kung, H. T. 1 Lam, Tak-Wah 1 Leininger, Brian S. 1 Lichtenstein, David 1 Ling, Alan Chi Hung 1 Lipton, Richard Jay 1 Lloyd, Errol L. 1 Mahr, Bernd 1 Mayer, Jack N. 1 Meyer, Albert Ronald 1 Miller, Gary Lee 1 Miller, Raymond E. 1 Mirkowska, Grazyna 1 Overmars, Mark H. 1 Parikh, Rohit 1 Paterson, Mike S. 1 Paul, Wolfgang Jakob 1 Pippenger, Nicholas J. 1 Plaisted, David Alan 1 Pratt, Vaughan R. 1 Reif, John H. 1 Reingold, Edward Martin 1 Sadri, Fereidoon 1 Savage, John E. 1 Schnorr, Claus Peter 1 Seiferas, Joel I. 1 Spirakis, Paul G. 1 Storer, James A. 1 Strong, H. Raymond 1 Supowit, Kenneth J. 1 Tarjan, Robert Endre 1 Toueg, Sam 1 Ukkonen, Esko 1 Ullman, Jeffrey David 1 Van Leeuwen, Jan 1 Venkateswaran, H. 1 Woll, Heather 1 Yan, Peiyuan 1 Yao, Frances F. 1 Yap, Chee-Keng 1 Young, Paul R. all top 5 Serials 8 Journal of Computer and System Sciences 7 SIAM Journal on Computing 3 Information and Computation 2 Information Processing Letters 2 Journal of the Association for Computing Machinery 1 Discrete Applied Mathematics 1 Journal of Symbolic Computation 1 SIAM Journal on Discrete Mathematics 1 Journal of Cryptology all top 5 Fields 25 Computer science (68-XX) 7 Information and communication theory, circuits (94-XX) 4 Mathematical logic and foundations (03-XX) 4 Combinatorics (05-XX) 3 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 2 Number theory (11-XX) 2 Field theory and polynomials (12-XX) 1 General and overarching topics; collections (00-XX) 1 Probability theory and stochastic processes (60-XX) 1 Operations research, mathematical programming (90-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 26 Publications have been cited 338 times in 296 Documents Cited by ▼ Year ▼ How to share a secret with cheaters. Zbl 0659.94008 Tompa, Martin; Woll, Heather 52 1988 Space-bounded hierarchies and probabilistic computations. Zbl 0573.68021 Ruzzo, Walter L.; Simon, Janos; Tompa, Martin 38 1984 Two applications of inductive counting for complementation problems. Zbl 0678.68031 Borodin, Allan; Cook, Stephen A.; Dymond, Patrick W.; Ruzzo, Walter L.; Tompa, Martin 35 1989 A time-space tradeoff for sorting on non-oblivious machines. Zbl 0462.68011 Borodin, Allan; Fischer, Michael J.; Kirkpatrick, David G.; Lynch, Nancy A.; Tompa, Martin 25 1981 Time-space tradeoffs for computing functions, using connectivity properties of their circuits. Zbl 0435.68034 Tompa, Martin 22 1980 Speedups of deterministic machines by synchronous parallel machines. Zbl 0589.68040 Dymond, Patrick W.; Tompa, Martin 18 1985 A new pebble game that characterizes parallel complexity classes. Zbl 0678.68047 Venkateswaran, H.; Tompa, Martin 15 1989 Decreasing the nesting depth of expressions involving square roots. Zbl 0574.12001 Borodin, Allan; Fagin, Ronald; Hopcrofts, John E.; Tompa, Martin 15 1985 The effect of number of Hamiltonian paths on the complexity of a vertex- coloring problem. Zbl 0537.68067 Manber, Udi; Tompa, Martin 13 1984 Time-space tradeoffs for computing functions, using connectivity properties of their circuits. Zbl 1282.68145 Tompa, Martin 12 1978 The complexity of problems on probabilistic, nondeterministic, and alternating decision trees. Zbl 0631.68044 Manber, Udi; Tompa, Martin 11 1985 A direct version of Shamir and Snir’s lower bounds on monotone circuit depth. Zbl 0795.68102 Tiwari, Prasoon; Tompa, Martin 10 1994 Two familiar transitive closure algorithms which admit no polynomial time, sublinear space implementations. Zbl 0478.68045 Tompa, Martin 9 1982 Parallel graph algorithms that are efficient on average. Zbl 0684.68049 Coppersmith, Don; Raghavan, Prabhakar; Tompa, Martin 8 1989 Lower bounds on the length of universal traversal sequences. Zbl 0754.68061 Borodin, Allan; Ruzzo, Walter L.; Tompa, Martin 8 1992 The parallel complexity of exponentiating polynomials over finite fields. Zbl 0652.68032 Fich, Faith E.; Tompa, Martin 8 1988 An extension of Savitch’s theorem to small space bounds. Zbl 0457.68040 Tompa, Martin 6 1981 Lower bounds on universal traversal sequences based on chains of length five. Zbl 0835.68053 Buss, Jonathan; Tompa, Martin 5 1995 Time-space tradeoffs for undirected graph traversal by graph automata. Zbl 0872.68067 Beame, Paul; Borodin, Allan; Raghavan, Prabhakar; Ruzzo, Walter L.; Tompa, Martin 5 1996 An optimal solution to a wire-routing problem. Zbl 0468.94020 Tompa, Martin 5 1981 Corrigendum to “Time-space tradeoffs for computing functions, using connectivity properties of their circuits”. Zbl 0465.68020 Tompa, Martin 4 1981 Lower bounds on universal traversal sequences for cycles and other low degree graphs. Zbl 0760.68038 Tompa, Martin 4 1992 The complexity of short two-person games. Zbl 0742.90089 Chandra, Ashok K.; Tompa, Martin 4 1990 Communication-space tradeoffs for unrestricted protocols. Zbl 0809.68078 Beame, Paul; Tompa, Martin; Yan, Peiyuan 3 1994 A time-space tradeoff for undirected graph traversal by walking automata. Zbl 0928.68085 Beame, Paul; Borodin, Allan; Raghavan, Prabhakar; Ruzzo, Walter L.; Tompa, Martin 2 1999 Zero knowledge interactive proofs of knowledge. Zbl 0725.68089 Tompa, Martin 1 1988 A time-space tradeoff for undirected graph traversal by walking automata. Zbl 0928.68085 Beame, Paul; Borodin, Allan; Raghavan, Prabhakar; Ruzzo, Walter L.; Tompa, Martin 2 1999 Time-space tradeoffs for undirected graph traversal by graph automata. Zbl 0872.68067 Beame, Paul; Borodin, Allan; Raghavan, Prabhakar; Ruzzo, Walter L.; Tompa, Martin 5 1996 Lower bounds on universal traversal sequences based on chains of length five. Zbl 0835.68053 Buss, Jonathan; Tompa, Martin 5 1995 A direct version of Shamir and Snir’s lower bounds on monotone circuit depth. Zbl 0795.68102 Tiwari, Prasoon; Tompa, Martin 10 1994 Communication-space tradeoffs for unrestricted protocols. Zbl 0809.68078 Beame, Paul; Tompa, Martin; Yan, Peiyuan 3 1994 Lower bounds on the length of universal traversal sequences. Zbl 0754.68061 Borodin, Allan; Ruzzo, Walter L.; Tompa, Martin 8 1992 Lower bounds on universal traversal sequences for cycles and other low degree graphs. Zbl 0760.68038 Tompa, Martin 4 1992 The complexity of short two-person games. Zbl 0742.90089 Chandra, Ashok K.; Tompa, Martin 4 1990 Two applications of inductive counting for complementation problems. Zbl 0678.68031 Borodin, Allan; Cook, Stephen A.; Dymond, Patrick W.; Ruzzo, Walter L.; Tompa, Martin 35 1989 A new pebble game that characterizes parallel complexity classes. Zbl 0678.68047 Venkateswaran, H.; Tompa, Martin 15 1989 Parallel graph algorithms that are efficient on average. Zbl 0684.68049 Coppersmith, Don; Raghavan, Prabhakar; Tompa, Martin 8 1989 How to share a secret with cheaters. Zbl 0659.94008 Tompa, Martin; Woll, Heather 52 1988 The parallel complexity of exponentiating polynomials over finite fields. Zbl 0652.68032 Fich, Faith E.; Tompa, Martin 8 1988 Zero knowledge interactive proofs of knowledge. Zbl 0725.68089 Tompa, Martin 1 1988 Speedups of deterministic machines by synchronous parallel machines. Zbl 0589.68040 Dymond, Patrick W.; Tompa, Martin 18 1985 Decreasing the nesting depth of expressions involving square roots. Zbl 0574.12001 Borodin, Allan; Fagin, Ronald; Hopcrofts, John E.; Tompa, Martin 15 1985 The complexity of problems on probabilistic, nondeterministic, and alternating decision trees. Zbl 0631.68044 Manber, Udi; Tompa, Martin 11 1985 Space-bounded hierarchies and probabilistic computations. Zbl 0573.68021 Ruzzo, Walter L.; Simon, Janos; Tompa, Martin 38 1984 The effect of number of Hamiltonian paths on the complexity of a vertex- coloring problem. Zbl 0537.68067 Manber, Udi; Tompa, Martin 13 1984 Two familiar transitive closure algorithms which admit no polynomial time, sublinear space implementations. Zbl 0478.68045 Tompa, Martin 9 1982 A time-space tradeoff for sorting on non-oblivious machines. Zbl 0462.68011 Borodin, Allan; Fischer, Michael J.; Kirkpatrick, David G.; Lynch, Nancy A.; Tompa, Martin 25 1981 An extension of Savitch’s theorem to small space bounds. Zbl 0457.68040 Tompa, Martin 6 1981 An optimal solution to a wire-routing problem. Zbl 0468.94020 Tompa, Martin 5 1981 Corrigendum to “Time-space tradeoffs for computing functions, using connectivity properties of their circuits”. Zbl 0465.68020 Tompa, Martin 4 1981 Time-space tradeoffs for computing functions, using connectivity properties of their circuits. Zbl 0435.68034 Tompa, Martin 22 1980 Time-space tradeoffs for computing functions, using connectivity properties of their circuits. Zbl 1282.68145 Tompa, Martin 12 1978 all cited Publications top 5 cited Publications all top 5 Cited by 467 Authors 7 Stinson, Douglas Robert 6 Allender, Eric W. 5 Chakraborty, Sankardeep 5 Raman, Venkatesh 5 Satti, Srinivasa Rao 5 Savage, John E. 5 Tompa, Martin 5 Wigderson, Avi 4 Carlson, David A. 4 Gál, Anna 4 Grigor’ev, Dmitriĭ Yur’evich 4 Jenner, Birgit 4 Lange, Klaus-Jörn 4 Nisan, Noam 4 Tiwari, Prasoon 4 Venkateswaran, H. 3 Àlvarez, Carme 3 Alwen, Joël 3 Balcázar, José Luis 3 Blundo, Carlo 3 Borodin, Allan B. 3 de Rezende, Susanna F. 3 De Santis, Alfredo 3 Dymond, Patrick W. 3 Harn, Lein 3 Holzer, Markus 3 Jang, Jing-Tang 3 Landau, Susan 3 Lohrey, Markus 3 Macarie, Ioan I. 3 Nordström, Jakob 3 Paterson, Maura Beth 3 Patt-Shamir, Boaz 3 Ruzzo, Walter L. 3 Sakurai, Kouichi 3 Smolensky, Roman 3 Vollmer, Heribert 3 von zur Gathen, Joachim 3 Yukna, Stasys P. 2 Adhikari, Avishek 2 Ajtai, Miklós 2 Alon, Noga 2 Biswas, Arindam 2 Blocki, Jeremiah 2 Chandra, Ashok K. 2 Chen, Jian-er 2 Damm, Carsten 2 de Keijzer, Bart 2 Feige, Uriel 2 Fraigniaud, Pierre 2 Harutyunyan, Ararat 2 Hertrampf, Ulrich 2 Horng, Gwoboa 2 Ibarra, Oscar H. 2 Ilcinkas, David 2 Ioannidis, Stavros D. 2 Jiao, Jia 2 Kalyanasundaram, Bala 2 Karpinski, Marek 2 Kirsig, Bernd 2 Komarath, Balagopal 2 Krebs, Andreas 2 Kutrib, Martin 2 Loui, Michael C. 2 Mahajan, Meena 2 Malod, Guillaume 2 Meir, Or 2 Mukherjee, Anish 2 Naor, Moni 2 Obana, Satoshi 2 Ogata, Wakaha 2 Ostrovsky, Rafail 2 Padró, Carles 2 Pandurangan, Gopal 2 Papakonstantinou, Periklis A. 2 Pelc, Andrzej 2 Peleg, David 2 Reidys, Christian Michael 2 Reinhardt, Klaus 2 Robere, Robert 2 Rossman, Benjamin 2 Sarma M. N., Jayalal 2 Saurabh, Saket 2 Sawlani, Saurabh 2 Schnitger, Georg 2 Sengupta, Rimli 2 Sudborough, Ivan Hal 2 Vaccaro, Ugo 2 Ventre, Carmine 2 Williams, Richard Ryan 2 Wilson, Christopher B. 2 Yamakami, Tomoyuki 2 Yanbe, Akio 2 Yehudayoff, Amir 1 Abelson, Harold 1 Adamatzky, Andrew I. 1 Aehlig, Klaus 1 Aggarwal, Alok 1 Al-Shuhail, Abdullatif 1 Aldaz, Mikel ...and 367 more Authors all top 5 Cited in 63 Serials 39 Theoretical Computer Science 32 Journal of Computer and System Sciences 20 Information Processing Letters 14 Information and Computation 14 Computational Complexity 10 Designs, Codes and Cryptography 7 Mathematical Systems Theory 6 Discrete Applied Mathematics 5 Theory of Computing Systems 4 Combinatorica 4 Journal of Symbolic Computation 4 Algorithmica 3 Discrete Mathematics 3 Journal of Complexity 3 International Journal of Foundations of Computer Science 3 RAIRO. Informatique Théorique et Applications 3 Cryptography and Communications 2 The Mathematical Intelligencer 2 Applied Mathematics and Computation 2 BIT 2 Computing 2 SIAM Journal on Computing 2 Journal of the American Mathematical Society 2 SIAM Journal on Discrete Mathematics 2 RAIRO. Theoretical Informatics and Applications 2 Mathematical Biosciences and Engineering 2 Logical Methods in Computer Science 1 Acta Informatica 1 International Journal of Mathematical Education in Science and Technology 1 Journal of Mathematical Analysis and Applications 1 Mathematics of Computation 1 Information Sciences 1 Journal of Graph Theory 1 Journal of Soviet Mathematics 1 Kybernetika 1 European Journal of Combinatorics 1 Advances in Applied Mathematics 1 SIAM Journal on Algebraic and Discrete Methods 1 Annals of Pure and Applied Logic 1 Mathematical and Computer Modelling 1 Journal of Cryptology 1 Random Structures & Algorithms 1 International Journal of Computational Geometry & Applications 1 International Journal of Computer Mathematics 1 Pattern Recognition 1 Distributed Computing 1 Archive for Mathematical Logic 1 Combinatorics, Probability and Computing 1 Finite Fields and their Applications 1 The Bulletin of Symbolic Logic 1 Monte Carlo Methods and Applications 1 Annals of Mathematics and Artificial Intelligence 1 Journal of Combinatorial Optimization 1 Wuhan University Journal of Natural Sciences (WUJNS) 1 Nexus Network Journal 1 International Journal of Applied Mathematics and Computer Science 1 Journal of Systems Science and Complexity 1 Journal of Mathematical Cryptology 1 European Journal of Pure and Applied Mathematics 1 Advances and Applications in Discrete Mathematics 1 Groups, Complexity, Cryptology 1 Science China. Mathematics 1 GEM - International Journal on Geomathematics all top 5 Cited in 24 Fields 229 Computer science (68-XX) 79 Information and communication theory, circuits (94-XX) 50 Combinatorics (05-XX) 25 Mathematical logic and foundations (03-XX) 11 Number theory (11-XX) 11 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 7 Operations research, mathematical programming (90-XX) 5 Field theory and polynomials (12-XX) 3 Commutative algebra (13-XX) 3 Convex and discrete geometry (52-XX) 2 Linear and multilinear algebra; matrix theory (15-XX) 2 Group theory and generalizations (20-XX) 2 Geometry (51-XX) 2 Probability theory and stochastic processes (60-XX) 2 Quantum theory (81-XX) 1 General and overarching topics; collections (00-XX) 1 Order, lattices, ordered algebraic structures (06-XX) 1 Real functions (26-XX) 1 Special functions (33-XX) 1 Numerical analysis (65-XX) 1 Geophysics (86-XX) 1 Biology and other natural sciences (92-XX) 1 Systems theory; control (93-XX) 1 Mathematics education (97-XX) Citations by Year