skip to main content
article

SIGACT news complexity theory column 48

Published: 01 September 2005 Publication History

Abstract

Here is a real gift to the field from David Johnson: After a thirteen year intermission, David is restarting his NP-completeness column. His column will now appear about twice yearly in ACM Transactions on Algorithms. Welcome back David, and thanks! And for those for whom a diet of two per year wont do, meals past can be found at http://www.research.att.com/~dsj/columns.html.

References

[1]
E. Allender. When worlds collide: Derandomization, lower bounds, and Kolmogorov complexity. In Proceedings of the 21st Conference on Foundations of Software Technology and Theoretical Computer Science, pages 1--15. Springer-Verlag, 2001.]]
[2]
K. Ambos-Spies, W. Merkle, J. Reimann, and F. Stephan. Hausdor dimension in exponential time. In Proceedings of the 16th IEEE Conference on Computational Complexity, pages 210--217. IEEE Computer Society, 2001.]]
[3]
K. Ambos-Spies, H.-C. Neis, and S. A. Terwijn. Genericity and measure for exponential time. Theoretical Computer Science, 168(1):3--19, 1996.]]
[4]
K. B. Athreya, J. M. Hitchcock, J. H. Lutz, and E. Mayordomo. E ective strong dimension in algorithmic information and computational complexity. In Proceedings of the 21st Annual Symposium on Theoretical Aspects of Computer Science, pages 632--643. Springer-Verlag, 2004. To appear in SIAM Journal on Computing.]]
[5]
R. Beigel, L. Fortnow, and F. Stephan. In nitely-often autoreducible sets. In Proceedings of the 14th Annual International Symposium on Algorithms and Computation, pages 98--107. Springer-Verlag, 2003.]]
[6]
C. H. Bennett and J. Gill. Relative to a random oracle A, PA ≠ NPA ≠ co-NPA with probability 1. SIAM Journal on Computing, 10:96--113, 1981.]]
[7]
H. Buhrman and D. van Melkebeek. Hard sets are hard to nd. Journal of Computer and System Sciences, 59(2):327--345, 1999.]]
[8]
J. Cai and J. Hartmanis. On Hausdor and topological dimensions of the Kolmogorov complexity of the real line. Journal of Computer and Systems Sciences, 49:605--619, 1994.]]
[9]
J. J. Dai, J. I. Lathrop, J. H. Lutz, and E. Mayordomo. Finite-state dimension. Theoretical Computer Science, 310(1-3):1--33, 2004.]]
[10]
J. L. Doob. Regularity properties of certain families of chance variables. Transactions of the American Mathematical Society, 47:455--486, 1940.]]
[11]
R. Downey and D. Hirschfeldt. Algorithmic randomness and complexity. Book draft, 2005.]]
[12]
G. A. Edgar. Measure, Topology, and Fractal Geometry. Springer-Verlag, 1990.]]
[13]
G. A. Edgar. Integral, Probability, and Fractal Measures. Springer-Verlag, 1998.]]
[14]
K. Falconer. The Geometry of Fractal Sets. Cambridge University Press, 1985.]]
[15]
K. Falconer. Techniques in Fractal Geometry. John Wiley & Sons, 1997.]]
[16]
K. Falconer. Fractal Geometry: Mathematical Foundations and Applications. John Wiley & Sons, second edition, 2003.]]
[17]
H. Federer. Geometric Measure Theory. Springer-Verlag, 1969.]]
[18]
L. Fortnow. Personal communication, 2001.]]
[19]
L. Fortnow and J. H. Lutz. Prediction and dimension. Journal of Computer and System Sciences, 70(4):570--589, 2005.]]
[20]
C. Gla er, M. Ogihara, A. Pavan, A. Selman, and L. Zhang. Autoreducibility, mitoticity, and immunity. In Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science. Springer-Verlag, 2005.]]
[21]
X. Gu. A note on dimensions of polynomial size circuits. Technical Report TR04-047, Electronic Colloquium on Computational Complexity, 2004.]]
[22]
F. Hausdor. Dimension und au eres Ma. Mathematische Annalen, 79:157--179, 1919.]]
[23]
S. W. Hawking. Chronology protection conjecture. Physical Review D, 46(2):603--611, 1992.]]
[24]
J. M. Hitchcock. MAX3SAT is exponentially hard to approximate if NP has positive dimension. Theoretical Computer Science, 289(1):861--869, 2002.]]
[25]
J. M. Hitchcock. Effective Fractal Dimension: Foundations and Applications. PhD thesis, Iowa State University, 2003.]]
[26]
J. M. Hitchcock. Fractal dimension and logarithmic loss unpredictability. Theoretical Computer Science, 304(1-3):431--441, 2003.]]
[27]
J. M. Hitchcock. Hausdor dimension and oracle constructions. Technical Report TR04-072, Electronic Colloquium on Computational Complexity, 2004.]]
[28]
J. M. Hitchcock. Small spans in scaled dimension. SIAM Journal on Computing, 34(1):170--194, 2004.]]
[29]
J. M. Hitchcock, M. Lopez-Valdes, and E. Mayordomo. Scaled dimension and the Kolmogorov complexity of Turing-hard sets. In Proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science, pages 476--487. Springer-Verlag, 2004.]]
[30]
J. M. Hitchcock and J. H. Lutz. Why computational complexity requires stricter martingales. In Proceedings of the 29th International Colloquium on Automata, Languages, and Programming, pages 549--560. Springer-Verlag, 2002. To appear in Theory of Computing Systems.]]
[31]
J. M. Hitchcock, J. H. Lutz, and E. Mayordomo. Scaled dimension and nonuniform complexity. Journal of Computer and System Sciences, 69(2):97--122, 2004.]]
[32]
J. M. Hitchcock and A. Pavan. Hardness hypotheses, derandomization, and circuit complexity. In Proceedings of the 24th Conference on Foundations of Software Technology and Theoretical Computer Science, pages 336--347. Springer-Verlag, 2004.]]
[33]
J. M. Hitchcock and A. Pavan. Resource-bounded strong dimension versus resource-bounded category. Information Processing Letters, 95(3):377--381, 2005.]]
[34]
J. M. Hitchcock, A. Pavan, and N. V. Vinodchandran. Partial bi-immunity, scaled dimension, and NP-completeness. Manuscript, 2005.]]
[35]
J. M. Hitchcock and N. V. Vinodchandran. Dimension, entropy rates, and compression. In Proceedings of the 19th IEEE Conference on Computational Complexity, pages 174--183. IEEE Computer Society, 2004.]]
[36]
R. Impagliazzo and P. Moser. A zero-one law for RP. In Proceedings of the 18th IEEE Conference on Computational Complexity, pages 43--47. IEEE Computer Society, 2003.]]
[37]
R. Impagliazzo and A. Wigderson. Randomness vs. time: Derandomization under a uniform assumption. Journal of Computer and System Sciences, 63:672--688, 2001.]]
[38]
D. W. Juedes and J. H. Lutz. The complexity and distribution of hard problems. SIAM Journal on Computing, 24(2):279--295, 1995.]]
[39]
D. W. Juedes and J. H. Lutz. Completeness and weak completeness under polynomial-size circuits. Information and Computation, 125(1):13--31, 1996.]]
[40]
J. Kobler and W. Lindner. On the resource bounded measure of P/poly. In Proceedings of the 13th IEEE Conference on Computational Complexity, pages 182--185. IEEE Computer Society, 1998.]]
[41]
J. Kobler, U. Schoning, and J. Toran. On counting and approximation. Acta Informatica, 26:363--379, 1989.]]
[42]
P. Levy. Proprietes asymptotiques des sommes de variables independantes ou enchainees. Journal des mathématiques pures et appliquées. Series 9, 14(4):347--402, 1935.]]
[43]
P. Levy. Théorie de l'Addition des Variables Aleatoires. Gauthier-Villars, 1937 (second edition 1954).]]
[44]
W. Lindner. On the polynomial time bounded measure of one-truth-table degrees and p-selectivity. Diplomarbeit, Technische Universitat Berlin, 1993.]]
[45]
M. Lopez-Valdes and E. Mayordomo. Dimension is compression. In Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science. Springer-Verlag, 2005. To appear.]]
[46]
J. H. Lutz. Category and measure in complexity classes. SIAM Journal on Computing, 19(6):1100--1131, 1990.]]
[47]
J. H. Lutz. Almost everywhere high nonuniform complexity. Journal of Computer and System Sciences, 44(2):220--258, 1992.]]
[48]
J. H. Lutz. The quantitative structure of exponential time. In L. A. Hemaspaandra and A. L. Selman, editors, Complexity Theory Retrospective II, pages 225--254. Springer-Verlag, 1997.]]
[49]
J. H. Lutz. Resource-bounded measure. In Proceedings of the 13th IEEE Conference on Computational Complexity, pages 236--248. IEEE Computer Society, 1998.]]
[50]
J. H. Lutz. Dimension in complexity classes. In Proceedings of the Fifteenth Annual IEEE Conference on Computational Complexity, pages 158--169. IEEE Computer Society, 2000.]]
[51]
J. H. Lutz. Gales and the constructive dimension of individual sequences. In Proceedings of the 27th International Colloquium on Automata, Languages, and Programming, pages 902--913. Springer-Verlag, 2000. Revised as {53}.]]
[52]
J. H. Lutz. Dimension in complexity classes. SIAM Journal on Computing, 32(5):1236--1259, 2003.]]
[53]
J. H. Lutz. The dimensions of individual strings and sequences. Information and Computation, 187(1):49--79, 2003.]]
[54]
J. H. Lutz and E. Mayordomo. Cook versus Karp-Levin: Separating completeness notions if NP is not small. Theoretical Computer Science, 164(1-2):141--163, 1996.]]
[55]
J. H. Lutz and E. Mayordomo. Twelve problems in resource-bounded measure. Bulletin of the European Association for Theoretical Computer Science, 68:64--80, 1999. Also in Current Trends in Theoretical Computer Science: Entering the 21st Century, pages 83--101, World Scienti c Publishing, 2001.]]
[56]
P. Martin-Lof. The de nition of random sequences. Information and Control, 9:602--619, 1966.]]
[57]
P. Matilla. Geometry of Sets and Measures in Euclidean Spaces: Fractals and rectifiability. Cambridge University Press, 1995.]]
[58]
E. Mayordomo. Contributions to the study of resource-bounded measure. PhD thesis, Universitat Politecnica de Catalunya, 1994.]]
[59]
E. Mayordomo. A Kolmogorov complexity characterization of constructive Hausdor dimension. Information Processing Letters, 84(1):1--3, 2002.]]
[60]
P. Moser. Derandomization and Quantitative Complexity. PhD thesis, Universite de Geneve, 2004.]]
[61]
P. Moser. Generic density and small span theorem. In Proceedings of the 15th International Symposium on Fundamentals of Computation Theory. Springer-Verlag, 2005. To appear.]]
[62]
P. Moser. Martingale families and dimension in P. Technical Report TR05-045, Electronic Colloquium on Computational Complexity, 2005.]]
[63]
C. A. Rogers. Hausdorff Measures. Cambridge University Press, 1998. Originally published in 1970.]]
[64]
B. Ya. Ryabko. Algorithmic approach to the prediction problem. Problems of Information Transmission, 29:186--193, 1993.]]
[65]
B. Ya. Ryabko. The complexity and e ectiveness of prediction problems. Journal of Complexity, 10:281--295, 1994.]]
[66]
C. P. Schnorr. Klassi kation der Zufallsgesetze nach Komplexitat und Ordnung. Z. Wahrscheinlichkeitstheorie verw. Geb., 16:1--21, 1970.]]
[67]
C. P. Schnorr. A uni ed approach to the de nition of random sequences. Mathematical Systems Theory, 5:246--258, 1971.]]
[68]
C. P. Schnorr. Zufalligkeit und Wahrscheinlichkeit. Lecture Notes in Mathematics, 218, 1971.]]
[69]
C. P. Schnorr. Process complexity and e ective random tests. Journal of Computer and System Sciences, 7:376--388, 1973.]]
[70]
R. Shaltiel and C. Umans. Pseudorandomness for approximate counting and sampling. In Proceedings of the 20th IEEE Conference on Computational Complexity, pages 212--226. IEEE Computer Society, 2005.]]
[71]
C. E. Shannon. The synthesis of two-terminal switching circuits. Bell System Technical Journal, 28:59--98, 1949.]]
[72]
L. Staiger. A tight upper bound on Kolmogorov complexity and uniformly optimal prediction. Theory of Computing Systems, 31:215--29, 1998.]]
[73]
L. J. Stockmeyer. On approximation algorithms for #P. SIAM Journal on Computing, 14:849--861, 1985.]]
[74]
D. Sullivan. Entropy, Hausdor measures old and new, and limit sets of geometrically nite Kleinian groups. Acta Mathematica, 153:259--277, 1984.]]
[75]
C. Tricot. Two de nitions of fractional dimension. Mathematical Proceedings of the Cambridge Philosophical Society, 91:57--74, 1982.]]
[76]
D. van Melkebeek. The zero-one law holds for BPP. Theoretical Computer Science, 244(1-2):283--288, 2000.]]
[77]
J. Ville. Étude Critique de la Notion de Collectif. Gauthier-Villars, Paris, 1939.]]

Cited By

View all
  • (2014)Effective dimension in some general metric spacesElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.143.6143(67-75)Online publication date: 29-Mar-2014
  • (2013)High-confidence predictions under adversarial uncertaintyACM Transactions on Computation Theory10.1145/2493252.24932575:3(1-18)Online publication date: 22-Aug-2013
  • (2012)High-confidence predictions under adversarial uncertaintyProceedings of the 3rd Innovations in Theoretical Computer Science Conference10.1145/2090236.2090237(1-10)Online publication date: 8-Jan-2012
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM SIGACT News
ACM SIGACT News  Volume 36, Issue 3
September 2005
102 pages
ISSN:0163-5700
DOI:10.1145/1086649
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 2005
Published in SIGACT Volume 36, Issue 3

Check for updates

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 15 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2014)Effective dimension in some general metric spacesElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.143.6143(67-75)Online publication date: 29-Mar-2014
  • (2013)High-confidence predictions under adversarial uncertaintyACM Transactions on Computation Theory10.1145/2493252.24932575:3(1-18)Online publication date: 22-Aug-2013
  • (2012)High-confidence predictions under adversarial uncertaintyProceedings of the 3rd Innovations in Theoretical Computer Science Conference10.1145/2090236.2090237(1-10)Online publication date: 8-Jan-2012
  • (2011)Mass problems associated with effectively closed setsTohoku Mathematical Journal10.2748/tmj/132588627863:4Online publication date: 1-Jan-2011
  • (2011)Dimension, Halfspaces, and the Density of Hard SetsTheory of Computing Systems10.1007/s00224-010-9288-149:3(601-614)Online publication date: 1-Oct-2011
  • (2009)A characterization of constructive dimension†Mathematical Logic Quarterly10.1002/malq.20071008755:2(185-200)Online publication date: 20-Jan-2009
  • (2008)Scaled Dimension and the Kolmogorov Complexity of Turing-Hard SetsTheory of Computing Systems10.1007/s00224-007-9013-x43:3(471-497)Online publication date: 1-Dec-2008
  • (2007)Dimension, halfspaces, and the density of hard setsProceedings of the 13th annual international conference on Computing and Combinatorics10.5555/2394650.2394665(129-139)Online publication date: 16-Jul-2007
  • (2007)Dimension, Halfspaces, and the Density of Hard SetsComputing and Combinatorics10.1007/978-3-540-73545-8_15(129-139)Online publication date: 2007
  • (2006)Dimension, entropy rates, and compressionJournal of Computer and System Sciences10.1016/j.jcss.2005.10.00272:4(760-782)Online publication date: 1-Jun-2006
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media