Document Open Access Logo

Some Lower Bounds in Parameterized AC^0

Authors Yijia Chen, Jörg Flum

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.27.pdf
  • Filesize: 0.56 MB
  • 14 pages

Document Identifiers

Author Details

Yijia Chen
Jörg Flum

Cite AsGet BibTex

Yijia Chen and Jörg Flum. Some Lower Bounds in Parameterized AC^0. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.MFCS.2016.27

Abstract

We demonstrate some lower bounds for parameterized problems via parameterized classes corresponding to the classical AC^0. Among others, we derive such a lower bound for all fpt-approximations of the parameterized clique problem and for a parameterized halting problem, which recently turned out to link problems of computational complexity, descriptive complexity, and proof theory. To show the first lower bound, we prove a strong AC^0 version of the planted clique conjecture: AC^0-circuits asymptotically almost surely can not distinguish between a random graph and this graph with a randomly planted clique of any size <= n^xi (where 0 <= xi < 1).
Keywords
  • parameterized AC^0
  • lower bound
  • clique
  • halting problem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. M. Ajtai. Σ¹₁ formulae on finite structures. Annals of Pure and Applied Logic, 24(3):1-48, 1983. Google Scholar
  2. N. Alon, M. Krivelevich, and B. Sudakov. Finding a large hidden clique in a random graph. Random Struct. Algorithms, 13(3-4):457-466, 1998. Google Scholar
  3. M. Bannach, C. Stockhusen, and T. Tantau. Fast parallel fixed-parameter algorithms via color coding. In 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, September 16-18, 2015, Patras, Greece, pages 224-235, 2015. Google Scholar
  4. D. A. Mix Barrington, N. Immerman, and H. Straubing. On uniformity within NC¹. Journal of Computer and System Sciences, 41(3):274-306, 1990. Google Scholar
  5. P. Beame. A Switching Lemma Primer. Technical Report, University of Washington, 1984. Google Scholar
  6. P. Beame, R. Impagliazzo, and T. Pitassi. Improved depth lower bounds for small distance connectivity. Computational Complexity, 7(4):325-345, 1998. Google Scholar
  7. J. Chen, X. Huang, I. A. Kanj, and G. Xia. Linear FPT reductions and computational lower bounds. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, STOC 2004, IL, USA, June 13-16, 2004, pages 212-221, 2004. Google Scholar
  8. Y. Chen and J. Flum. A logic for PTIME and a parameterized halting problem. In Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, LICS 2009, 11-14 August 2009, Los Angeles, CA, USA, pages 397-406, 2009. Google Scholar
  9. Y. Chen and J. Flum. From almost optimal algorithms to logics for complexity classes via listings and a halting problem. Journal of the ACM, 59(4):17, 2012. Google Scholar
  10. Y. Chen, M. Grohe, and M. Grüber. On parameterized approximability. Electronic Colloquium on Computational Complexity (ECCC), 14(106), 2007. Google Scholar
  11. M. Elberfeld, C. Stockhusen, and T. Tantau. On the space and circuit complexity of parameterized problems: Classes and completeness. Algorithmica, 71(3):661-701, 2015. Google Scholar
  12. J. Flum and M. Grohe. Describing parameterized complexity classes. Information and Computation, 187(2):291-319, 2003. Google Scholar
  13. M. L. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17(1):13-27, 1984. Google Scholar
  14. S. Ginsburg and E.H. Spanier. Semigroups, Presburger fomulas, and languages. Pacific Journal of Mathematics, 16:285-296, 1966. Google Scholar
  15. M. Grohe, S. Kreutzer, and S. Siebertz. Deciding first-order properties of nowhere dense graphs. In Proceedings of the 46th Annual ACM Symposium on the Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 89-98, 2014. Google Scholar
  16. Y. Gurevich. Logic and the challenge of computer science. In Current trends in Theoetical computer Science, Computer Science Press, pages 1-57, 1988. Google Scholar
  17. M. Jerrum. Large cliques elude the metropolis process. Random Structures and Algorithms, 3(4):347-360, 1992. Google Scholar
  18. L. Kučera. Expected complexity of graph partitioning problems. Discrete Applied Mathematics, 57(2-3):193-212, 1995. Google Scholar
  19. A. Nash, J. B. Remmel, and V. Vianu. PTIME queries revisited. In Database Theory - ICDT 2005, 10th International Conference, Edinburgh, UK, January 5-7, 2005, Proceedings, volume 3363 of Lecture Notes in Computer Science, pages 274-288. Springer, 2005. Google Scholar
  20. B. Rossman. On the constant-depth complexity of k-clique. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC 2008, Victoria, British Columbia, Canada, pages 721-730, 2008. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact