Sotabase

Career

· Percy K. and Vida L. W. Hudson Professor of Computer Science, Columbia University2004–2002
· Professor, Stanford University2002–2003
· Director of Computing Principles Research Department, Avaya Laboratories2001–2002
· Head of Computing Principles Research Department, Bell Laboratories1991–2001
· PhD in Computer Science, Princeton University1979–
· Research Scientist, Bell Laboratories1978–1991
· Diploma in Electrical Engineering, National Technical University of Athens1975–

Publications (251)

Optimization, approximation, and complexity classes
Symposium on the Theory of Computing · 1991
1,995
cited
Principles and methods of testing finite state machines-a survey
Proceedings of the IEEE · 1996
1,365
cited
Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
SIAM journal on computing (Print) · 1984
1,182
cited
On the hardness of approximating minimization problems
JACM · 1994
1,001
cited
On Generating All Maximal Independent Sets
Information Processing Letters · 1988
890
cited
On the Desirability of Acyclic Database Schemes
JACM · 1983
849
cited
How Easy is Local Search?
Journal of computer and system sciences (Print) · 1985
815
cited
Computing the Minimum Fill-in is NP^Complete
1981
778
cited
The Complexity of Multiterminal Cuts
SIAM journal on computing (Print) · 1994
688
cited
Algorithms for Acyclic Database Schemes
Very Large Data Bases Conference · 1981
671
cited
Memory-efficient algorithms for the verification of temporal properties
Formal Methods Syst. Des. · 1990
602
cited
The complexity of probabilistic verification
JACM · 1995
602
cited
Expressing combinatorial optimization problems by linear programs
Symposium on the Theory of Computing · 1991
592
cited
Shortest Paths Without a Map
Theoretical Computer Science · 1989
588
cited
The Node-Deletion Problem for Hereditary Properties is NP-Complete
Journal of computer and system sciences (Print) · 1980
550
cited
Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations
JACM · 2005
527
cited
Towards an architecture-independent analysis of parallel algorithms
Symposium on the Theory of Computing · 1990
522
cited
On the approximability of trade-offs and optimal access of Web sources
Proceedings 41st Annual Symposium on Foundations of Computer Science · 2000
514
cited
Node-and edge-deletion NP-complete problems
Symposium on the Theory of Computing · 1978
507
cited
On the Complexity of Protein Folding
J. Comput. Biol. · 1998
493
cited
Sotabase