Luís Antunes



Computational Complexity


  1.   Antunes, L., Fortnow, L., Pinto, A., Souto, A. Low-Depth Witnesses are Easy to Find. Computational Complexity, Vol. 21(3):479-497. 2012. DOI: 10.1007/s00037-011-0025-1.
  2.  L. Antunes, A. Matos, A. Pinto, A. Souto and A. Teixeira, One-way functions using Algorithmic and Classical Information Theories. Theory of Computing Systems, 1:1-10, doi: 10.1007/s00224-012-9418-z
  3.  L. Antunes, A. Souto and A. Teixeira, Robustness of Logical Depth. Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012. Volume 7318 LNCS, 2012, pages 29-34.
  4.  A. Teixeira, A. Matos, L. Antunes, Conditional Rényi Entropies. IEEE Transactions on Information Theory 58(7): 4273-4277 (2012)
  5.  L. Antunes, A. Matos, A. Souto and A. Teixeira, Entropy Measures vs. Algorithmic Information. Entropy Journal, 13(3), 595-611, 2011, MDPI
  6.  L. Antunes and A. Souto, Information Measures for Infinite Sequences . Theoretical Computer Science 41(26-28):2602-2611, Elsevier 2010.
  7.  L. Antunes and L. Fortnow. Worst-case running times for average-case algorithms. In Proceedings of the 24th IEEE Conference on Computational Complexity, pages 298-303. 2009.
  8.  A. Pinto, A. Souto, Armando Matos and L. Antunes. Commitment and Authentication Systems. Designs, Codes & Cryptography. 53(3):175-193, 2009
  9.  L. Antunes, A. Matos, A. Souto and P. Vitanyi. Depth as Randomness deficiency. Theory of Computing Systems, 45(4):724-739, 2009.  
  10.  L. Antunes and L. Fortnow. Sophistication revisited. Theory of Computing Systems, 45(1):150-161, June 2009.
  11.  L. Antunes, S. Laplante, A. Pinto and L. Salvador. Cryptographic Security of Individual Instances. Proc. International Conference on Information Theoretic Security. Lecture Notes in Computer Science. Springer, 2007. To appear.
  12.  L. Antunes, A. Costa, A. Matos and P. Vitanyi. Computational Depth of Infinite Strings Revisited. Proc. CiE 2007, Computation and Logic in the Real World, 2007. 
  13.  L. Antunes, L. Fortnow, A. Pinto and A. Souto. Low-depth witnesses are easy to find. In Proceedings of the 22nd IEEE Conference on Computational Complexity. IEEE, New York, 2007. To appear.
  14.  L. Antunes, L. Fortnow, D. van Melkebeek, and N. Vinodchandran. Computational Depth: Concept and Applications. Special issue for selected papers from the 14th International Symposium on Fundamentals of Computation Theory. Theoretical Computer Science, 354 (3), pp.391-404. 2006.
  15.  L. Antunes and L. Fortnow. Sophistication revisited. In Proceedings of the 30th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science. Springer, 2003.
  16.  L . Antunes, L. Fortnow, and V. Vinodchandran. Using Depth to Capture Average-Case Complexity. In 14th International Symposium on Fundamentals of Computation Theory, Lecture Notes in Computer Science. Springer, Berlin, 2003.
  17.  L. Antunes. Useful Information. PhD thesis, Computer Science Department at the Science Faculty, Oporto University , 2002.
  18.  L. Antunes and Armando B. Matos. The Renyi entropy of an infinite sequence of non-independent symbols. Workshop Advances in AI organized within 10th Portuguese Conference on Artificial Intelligence, EPIA '01, December 2001.
  19.  L . Antunes,   L. Fortnow, and D. van Melkebeek. Computational depth. In Proceedings of the 16th IEEE Conference on Computational Complexity, pages 266-273. IEEE, New York, 2001.