LCS/AI Lab Timeline

Group: Theory Group

Group Index  >  Lab for Computer Science  >  Theory Group  >  Algorithms Group
Group Index  >  Lab for Computer Science  >  Theory Group  >  Complexity Theory
Group Index  >  Lab for Computer Science  >  Theory Group  >  Computation and Biology  (2 events)
Group Index  >  Lab for Computer Science  >  Theory Group  >  Cryptography and Information Security  (2 events)
Group Index  >  Lab for Computer Science  >  Theory Group  >  Scientific Computing Group
Group Index  >  Lab for Computer Science  >  Theory Group  >  Semantics
Group Index  >  Lab for Computer Science  >  Theory Group  >  Theory of Distributed Systems  (7 events)

Page: 1 2 (54 events)

Year	Event
1955	Convolutional coding Category:  Information Theory
1964	Complexity of recursive functions Categories:  Mathematics of Computation, Complexity
1967	Computation: Finite and Infinite Machines published
1968	Finite-state Models for Logical Machines published
1972	Continuations
1972	Inherently Complex Problems
1973	The Polynomial-time Hierarchy
1974	Complexity of Logics of Arithmetic
1975	Primes are in NP
1975	Universal codeword sets
1976	Dynamic Logic
1976	Probabilistic primality test
1976	Rabin wins Turing Award Categories:  Awards and Prizes, Mathematics of Computation
1977	Denotational Semantics published
1977	Linear-time string matching
1978	RSA -- the first public key cryptosystem
1979	Computational Complexity of Multivariate Polynomials
1980	Communication costs of computation
1980	Randomized finite-field
1981	Retiming of digital circuits
1981	Area-Efficient VLSI Computation wins first ACM Doctoral Thesis Award competition. Category:  Awards and Prizes
1981	Lower bounds to VLSI costs
1981	Mental poker
1982	Combinatorial Optimization: Algorithms and Complexity published
1982	Models of lambda calculus
1982	Perfect Pseudo-Random Generation
1982	Probabilistic Encryption
1983	How to Construct Random Functions
1984	Decision Procedure for the Theory of Real Numbers
1984	First hard subclass of Boolean circuits
1984	Provably good VLSI layout
1984	Secure Digital Signatures
1984	Wafer-scale systolic arrays
1985	Fat-tree universal interconnection network
1985	Verifiable Secret Sharing

Page: 1 2 (54 events)