Consequences of the provability of N P ? P/poly, The Journal of Symbolic Logic, vol.72, issue.4, pp.1353-1371, 2007. ,
The relative efficiency of propositional proof systems, The Journal of Symbolic Logic, vol.44, issue.1, pp.36-50, 1979. ,
Hierarchy Theorems for Probabilistic Polynomial Time, 45th Annual IEEE Symposium on Foundations of Computer Science, pp.316-324, 2004. ,
DOI : 10.1109/FOCS.2004.33
Recent work on hierarchies for semantic classes, SIGACT News, vol.37, issue.3, pp.36-54, 2006. ,
A Complete Public-Key Cryptosystem, Groups ??? Complexity ??? Cryptology, vol.1, issue.1, pp.1-12, 2009. ,
DOI : 10.1515/GCC.2009.1
URL : https://hal.archives-ouvertes.fr/hal-00714336
On Robust Combiners for Oblivious Transfer and Other Primitives, Proc. of EUROCRYPT-2005, 2005. ,
DOI : 10.1007/11426639_6
Structural complexity of AvgBPP, Proceedings of 4th International Computer Science Symposium in Russia, pp.155-166, 2009. ,
Abstract, The Journal of Symbolic Logic, vol.1130, issue.03, pp.1063-1079, 1989. ,
DOI : 10.1016/0304-3975(85)90144-6
Universal sequential search problems. Problems of Information Transmission, pp.265-266, 1973. ,
On Optimal Algorithms and Optimal Proof Systems, Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science, pp.361-372, 1999. ,
DOI : 10.1007/3-540-49116-3_51
Speedup for natural problems and coNP?=NP, Electronic Colloquium on Computational Complexity, 2009. ,
Randomized algorithms, 1995. ,
On Heuristic Time Hierarchies, Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), pp.347-358, 2007. ,
DOI : 10.1109/CCC.2007.20
On reducibility and symmetry of disjoint NP pairs, Theoretical Computer Science, vol.295, pp.1-3323, 2003. ,
On provably disjoint NP-pairs, BRICS Report Series, vol.1, issue.36, 1994. ,
DOI : 10.7146/brics.v1i36.21607