Открытый каталог публикаций OpenAlex 79 документов

• The status of the P versus NP problem
  автор: Lance Fortnow год: 2009 источник: Communications of the ACM тип: статья из журнала
  Полный текстПодробнее
• NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly
  авторы: Harry Buhrman; John M. Hitchcock год: 2008 тип: статья
  Полный текстПодробнее
• Hierarchy Theorems for Probabilistic Polynomial Time
  авторы: Lance Fortnow; Rahul Santhanam год: 2004 тип: статья
  Страница публикацииПодробнее
• Algebrization
  авторы: Scott Aaronson; Avi Wigderson год: 2008 тип: статья
  Страница публикацииПодробнее
• Non-uniform ACC Circuit Lower Bounds
  автор: Ryan Williams год: 2011 тип: статья
  Полный текстПодробнее
• Improving exhaustive search implies superpolynomial lower bounds
  автор: Ryan Williams год: 2010 тип: статья
  Страница публикацииПодробнее
• Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification
  авторы: Russell Impagliazzo; Ragesh Jaiswal; Valentine Kabanets год: 2006 тип: статья
  Страница публикацииПодробнее
• Zero knowledge and circuit minimization
  авторы: Eric Allender; Bireswar Das год: 2017 источник: Information and Computation тип: статья из журнала
  Полный текстПодробнее
• Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
  авторы: Timothy M. Chan; Ryan Williams год: 2015 тип: статья
  Полный текстПодробнее
• Non-Black-Box Worst-Case to Average-Case Reductions within NP
  автор: Shuichi Hirahara год: 2018 тип: статья
  Страница публикацииПодробнее
• Time-space tradeoffs for nondeterministic computation
  авторы: Lance Fortnow; Dieter van Melkebeek год: 2002 тип: статья
  Страница публикацииПодробнее
• On the Limits of Sparsification
  авторы: Rahul Santhanam; Srikanth Srinivasan год: 2012 источник: Lecture notes in computer science тип: глава из книги
  Полный текстПодробнее
• New algorithms and lower bounds for circuits with linear threshold gates
  автор: Ryan Williams год: 2014 тип: статья
  Полный текстПодробнее
• NP with Small Advice
  авторы: Lance Fortnow; Adam R. Klivans год: 2005 тип: статья
  Страница публикацииПодробнее
• Natural proofs versus derandomization
  автор: Ryan Williams год: 2013 тип: статья
  Полный текстПодробнее