Two theorems on random polynomial time, 19th Annual Symposium on Foundations of Computer Science (sfcs 1978), pp.75-83, 1978. ,
DOI : 10.1109/SFCS.1978.37
Structural Complexity I. Number 11 in EATCS monographs on theoretical computer science, 1988. ,
Nonuniform lower bounds for exponential time classes, 20th symposium on Mathematical Foundations of Computer Science, pp.159-168, 1995. ,
DOI : 10.1007/3-540-60246-1_122
Circuit-size lower bounds and non-reducibility to sparse sets, Information and Control, vol.55, issue.1-3, pp.40-56, 1982. ,
DOI : 10.1016/S0019-9958(82)90382-5
Turing machines that take advice, Enseignement Mathématique, vol.28, pp.191-209, 1982. ,
Combinatorial foundations of information theory and the calculus of probabilities, Russian Mathematical Surveys, vol.38, issue.4, pp.29-40, 1983. ,
DOI : 10.1070/RM1983v038n04ABEH004203
Resource bounded symmetry of information revisited, Earlier version in 29th Symposium on the Mathematical Foundations of Computer Science, pp.386-405, 2004. ,
DOI : 10.1016/j.tcs.2005.07.017
An introduction to Kolmogorov complexity and its applications . Graduate texts in computer science, 1997. ,
On Symmetry of Information and Polynomial Time Invertibility, Information and Computation, vol.121, issue.1, pp.14-22, 1995. ,
DOI : 10.1006/inco.1995.1120
Hardness vs randomness, Journal of Computer and System Sciences, vol.49, issue.2, pp.149-167, 1994. ,
DOI : 10.1016/S0022-0000(05)80043-1
Kolmogorov Complexity and Derandomization, 2004. ,
A note on the circuit complexity of PP, Electronic Colloquium on Computational Complexity, 2004. ,
DOI : 10.1016/j.tcs.2005.07.032
THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS, Russian Mathematical Surveys, vol.25, issue.6, pp.83-124, 1970. ,
DOI : 10.1070/RM1970v025n06ABEH001269