SIGACT news complexity theory column 38
Author:
Open Access
- 1 December 2002
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGACT News
- Vol. 33 (4) , 22-36
Abstract
No abstract availableThis publication has 14 references indexed in Scilit:
- The Minimum Equivalent DNF Problem and Shortest ImplicantsJournal of Computer and System Sciences, 2001
- Loss-less condensers, unbalanced expanders, and extractors2001
- Deciding the Vapnik–Červonenkis Dimension is∑p3-completeJournal of Computer and System Sciences, 1999
- Computing with Very Weak Random SourcesSIAM Journal on Computing, 1999
- On the complexity of pattern matching for highly compressed two-dimensional texts1997
- On Limited Nondeterminism and the Complexity of the V-C DimensionJournal of Computer and System Sciences, 1996
- On the longest circuit in an alterable digraphJournal of Global Optimization, 1995
- Three ? P 2 -complete problems in computational learning theorycomputational complexity, 1991
- The complexity of combinatorial problems with succinct input representationActa Informatica, 1986
- Succinct representations of graphsInformation and Control, 1983