Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
John M. Hitchcock and Hadi Shafei. Nonuniform Reductions and NP-Completeness. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 40:1-40:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{hitchcock_et_al:LIPIcs.STACS.2018.40, author = {Hitchcock, John M. and Shafei, Hadi}, title = {{Nonuniform Reductions and NP-Completeness}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {40:1--40:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.40}, URN = {urn:nbn:de:0030-drops-85217}, doi = {10.4230/LIPIcs.STACS.2018.40}, annote = {Keywords: computational complexity, NP-completeness, reducibility, nonuniform complexity} }
Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
John M. Hitchcock and Hadi Shafei. Autoreducibility of NP-Complete Sets. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 42:1-42:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{hitchcock_et_al:LIPIcs.STACS.2016.42, author = {Hitchcock, John M. and Shafei, Hadi}, title = {{Autoreducibility of NP-Complete Sets}}, booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)}, pages = {42:1--42:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-001-9}, ISSN = {1868-8969}, year = {2016}, volume = {47}, editor = {Ollinger, Nicolas and Vollmer, Heribert}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.42}, URN = {urn:nbn:de:0030-drops-57437}, doi = {10.4230/LIPIcs.STACS.2016.42}, annote = {Keywords: computational complexity, NP-completeness, autoreducibility, genericity} }
Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)
John M. Hitchcock and A. Pavan. On the NP-Completeness of the Minimum Circuit Size Problem. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 236-245, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{hitchcock_et_al:LIPIcs.FSTTCS.2015.236, author = {Hitchcock, John M. and Pavan, A.}, title = {{On the NP-Completeness of the Minimum Circuit Size Problem}}, booktitle = {35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)}, pages = {236--245}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-97-2}, ISSN = {1868-8969}, year = {2015}, volume = {45}, editor = {Harsha, Prahladh and Ramalingam, G.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.236}, URN = {urn:nbn:de:0030-drops-56613}, doi = {10.4230/LIPIcs.FSTTCS.2015.236}, annote = {Keywords: Minimum Circuit Size, NP-completeness, truth-table reductions, circuit complexity} }
Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)
Xiaoyang Gu, John M. Hitchcock, and Aduri Pavan. Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 429-440, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{gu_et_al:LIPIcs.STACS.2010.2462, author = {Gu, Xiaoyang and Hitchcock, John M. and Pavan, Aduri}, title = {{Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses}}, booktitle = {27th International Symposium on Theoretical Aspects of Computer Science}, pages = {429--440}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-16-3}, ISSN = {1868-8969}, year = {2010}, volume = {5}, editor = {Marion, Jean-Yves and Schwentick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2462}, URN = {urn:nbn:de:0030-drops-24627}, doi = {10.4230/LIPIcs.STACS.2010.2462}, annote = {Keywords: Computational complexity, NP-completeness} }
Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)
John M. Hitchcock, Aduri Pavan, and N. V. Vinodchandran. Kolmogorov Complexity in Randomness Extraction. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 215-226, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{hitchcock_et_al:LIPIcs.FSTTCS.2009.2320, author = {Hitchcock, John M. and Pavan, Aduri and Vinodchandran, N. V.}, title = {{Kolmogorov Complexity in Randomness Extraction}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {215--226}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-13-2}, ISSN = {1868-8969}, year = {2009}, volume = {4}, editor = {Kannan, Ravi and Narayan Kumar, K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2320}, URN = {urn:nbn:de:0030-drops-23201}, doi = {10.4230/LIPIcs.FSTTCS.2009.2320}, annote = {Keywords: Extractors, Kolmogorov extractors, randomness} }
Feedback for Dagstuhl Publishing