1

Michael Alekhnovich , Samuel R. Buss , Shlomo Moran , Toniann Pitassi, Minimum Propositional Proof Length is NP-Hard to Linearly Approximate, Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science, p.176-184, August 24-28, 1998

2

Piotr Berman , Marek Karpinski , Lawrence L. Larmore , Wojciech Plandowski , Wojciech Rytter, On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts, Proceedings of the 8th Annual Symposium on Combinatorial Pattern Matching, p.40-51, June 30-July 02, 1997

3

Anne Condon , Joan Feigenbaum , Carsten Lund , Peter Shor, Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.305-314, May 16-18, 1993, San Diego, California, United States  [doi>10.1145/167088.167190]

4

Hana Galperin , Avi Wigderson, Succinct representations of graphs, Information and Control, v.56 n.3, p.183-198, March 1983  [doi>10.1016/S0019-9958(83)80004-7]

5

Venkatesan Guruswami , Madhu Sudan, List decoding of error-correcting codes, 2001

6

Venkatesan Guruswami , Madhu Sudan, List decoding algorithms for certain concatenated codes, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.181-190, May 21-23, 2000, Portland, Oregon, United States  [doi>10.1145/335305.335327]

7

Edith Hemaspaandra , Gerd Wechsung, The Minimization Problem for Boolean Formulas, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.575, October 19-22, 1997

8

M. A. Kiwi, C. Lund, A. Russell, D. A. Spielman, and R. Sundaram. Alternation in interaction. In Structure in Complexity Theory Conference, pages 294-303, 1994.

9

K.-I. Ko and C.-L. Lin. On the complexity of min-max optimization problems and their approximation. In D.-Z. Du and P. M. Pardalos, editors, Minimax and Applications, pages 219-239. Kluwer Academic Publishers, Boston, 1995.

10

K.-I. Ko and C.-L. Lin. On the longest circuit in an alterable digraph. Journal of Global Optimization, 7:279-295, 1995.

11

K.-I. Ko and W.-G. Tzeng. Three ∑p2-complete Problems in Computational Learning Theory. Computational Complexity, 1:269-310, 1991.

12

A. R. Meyer and L. J. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. In 13th Annual Symposium on Switching and Automata Theory, pages 125-129, The University of Maryland, 25-27 Oct. 1972. IEEE.

13

Elchanan Mossel , Christopher Umans, On the Complexity of Approximating the VC Dimension, Proceedings of the 16th Annual Conference on Computational Complexity, p.220, June 18-21, 2001

14

Christos H. Papadimitriou , Mihalis Yannakakis, On limited nondeterminism and the complexity of the V-C dimension, Journal of Computer and System Sciences, v.53 n.2, p.161-170, Oct. 1996  [doi>10.1006/jcss.1996.0058]

15

Marcus Schaefer, Deciding the Vapnik-Ccaron;ervonenkis dimension is S^p3 -complete, Journal of Computer and System Sciences, v.58 n.1, p.177-182, Feb. 1999  [doi>10.1006/jcss.1998.1602]

16

R. Shaltiel. Recent developments in explicit constructions of extractors. BEATCS Computational Complexity Column, 77, June 2002.

17

Aravind Srinivasan , David Zuckerman, Computing with Very Weak Random Sources, SIAM Journal on Computing, v.28 n.4, p.1433-1459, Aug. 1999  [doi>10.1137/S009753979630091X]

18

Amnon Ta-Shma , Christopher Umans , David Zuckerman, Loss-less condensers, unbalanced expanders, and extractors, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.143-152, July 2001, Hersonissos, Greece  [doi>10.1145/380752.380790]

19

T. Tantau. A note on the complexity of the reachability problem for tournaments. Technical Report TR01-092, ECCC, Nov. 2001.

20

Christopher Umans, The Minimum Equivalent DNF Problem and Shortest Implicants, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.556, November 08-11, 1998

21

Christopher Umans, Hardness of Approximating Minimization Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.465, October 17-18, 1999

22

Christopher Umans, On the Complexity and Inapproximability of Shortest Implicant Problems, Proceedings of the 26th International Colloquium on Automata, Languages and Programming, p.687-696, July 11-15, 1999

23

Christopher Matthew Umans , Christos H. Papadimitriou, Approximability and completeness in the polynomial hierarchy, 2000

24

Christopher Umans, The minimum equivalent DNF problem and shortest implicants, Journal of Computer and System Sciences, v.63 n.4, p.597-611, December 2001  [doi>10.1006/jcss.2001.1775]

25

Klaus W. Wagner, The complexity of combinatorial problems with succinct input representation, Acta Informatica, v.23 n.3, p.325-356, June 1986  [doi>10.1007/BF00289117]

Lane A. Hemaspaandra: colleagues