×
Author ID: tompa.martin Recent zbMATH articles by "Tompa, Martin"
Published as: Tompa, Martin
External Links: MGP
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.

Publications by Year

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 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

Citations by Year