Akmal, Shyan; Chen, Lijie; Jin, Ce; Raj, Malvika; Williams, Ryan Improved Merlin-Arthur protocols for central problems in fine-grained complexity. (English) Zbl 07729248 Algorithmica 85, No. 8, 2395-2426 (2023). MSC: 68Wxx 05Cxx PDFBibTeX XMLCite \textit{S. Akmal} et al., Algorithmica 85, No. 8, 2395--2426 (2023; Zbl 07729248) Full Text: DOI
Williams, Ryan The power of constructing bad inputs. (English) Zbl 1512.68111 Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 139, 78-95 (2023). MSC: 68Q17 68Q25 PDFBibTeX XMLCite \textit{R. Williams}, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 139, 78--95 (2023; Zbl 1512.68111) Full Text: Link
Vyas, Nikhil; Williams, R. Ryan Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of #SAT algorithms. (English) Zbl 07680322 Theory Comput. Syst. 67, No. 1, 149-177 (2023). MSC: 68Qxx 94Cxx 68Txx PDFBibTeX XMLCite \textit{N. Vyas} and \textit{R. R. Williams}, Theory Comput. Syst. 67, No. 1, 149--177 (2023; Zbl 07680322) Full Text: DOI
Chapman, Brynmor K.; Williams, R. Ryan Black-box hypotheses and lower bounds. (English) Zbl 07724202 Bonchi, Filippo (ed.) et al., 46th international symposium on mathematical foundations of computer science, MFCS 2021, August 23–27, 2021, Tallinn, Estonia. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 202, Article 29, 22 p. (2021). MSC: 68Qxx PDFBibTeX XMLCite \textit{B. K. Chapman} and \textit{R. R. Williams}, LIPIcs -- Leibniz Int. Proc. Inform. 202, Article 29, 22 p. (2021; Zbl 07724202) Full Text: DOI
Williams, R. Ryan From circuit complexity to faster all-pairs shortest paths. (English) Zbl 1470.05139 SIAM Rev. 63, No. 3, 559-582 (2021). MSC: 05C76 05C82 05C85 68Q25 94C05 68W25 PDFBibTeX XMLCite \textit{R. R. Williams}, SIAM Rev. 63, No. 3, 559--582 (2021; Zbl 1470.05139) Full Text: DOI
Vyas, Nikhil; Williams, Ryan On super strong ETH. (English) Zbl 1512.68115 J. Artif. Intell. Res. (JAIR) 70, 473-495 (2021). MSC: 68Q25 68R07 68T20 68W20 PDFBibTeX XMLCite \textit{N. Vyas} and \textit{R. Williams}, J. Artif. Intell. Res. (JAIR) 70, 473--495 (2021; Zbl 1512.68115) Full Text: DOI
Vyas, Nikhil; Williams, R. Ryan Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of #SAT algorithms. (English) Zbl 07650944 Paul, Christophe (ed.) et al., 37th international symposium on theoretical aspects of computer science, STACS 2020, Montpellier, France, March 10–13, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 154, Article 59, 17 p. (2020). MSC: 68Qxx PDFBibTeX XMLCite \textit{N. Vyas} and \textit{R. R. Williams}, LIPIcs -- Leibniz Int. Proc. Inform. 154, Article 59, 17 p. (2020; Zbl 07650944) Full Text: DOI arXiv
Chan, Timothy M.; Williams, R. Ryan Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky. (English) Zbl 07471487 ACM Trans. Algorithms 17, No. 1, Article No. 2, 14 p. (2021). MSC: 68R10 05C38 05C85 68Q25 PDFBibTeX XMLCite \textit{T. M. Chan} and \textit{R. R. Williams}, ACM Trans. Algorithms 17, No. 1, Article No. 2, 14 p. (2020; Zbl 07471487) Full Text: DOI
Murray, Cody D.; Williams, R. Ryan Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma. (English) Zbl 1494.68096 SIAM J. Comput. 49, No. 5, STOC18-300-STOC18-322 (2020). MSC: 68Q25 68Q06 68Q15 68Q17 PDFBibTeX XMLCite \textit{C. D. Murray} and \textit{R. R. Williams}, SIAM J. Comput. 49, No. 5, STOC18--300-STOC18--322 (2020; Zbl 1494.68096) Full Text: DOI
Chen, Lijie; Mckay, Dylan M.; Murray, Cody D.; Williams, R. Ryan Relations and equivalences between circuit lower bounds and Karp-Lipton theorems. (English) Zbl 07564430 Shpilka, Amir (ed.), 34th computational complexity conference, CCC 2019, New Brunswick, NJ, USA, July 18–20, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 137, Article 30, 21 p. (2019). MSC: 68Q25 PDFBibTeX XMLCite \textit{L. Chen} et al., LIPIcs -- Leibniz Int. Proc. Inform. 137, Article 30, 21 p. (2019; Zbl 07564430) Full Text: DOI
Chen, Lijie; Williams, R. Ryan Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity. (English) Zbl 07564419 Shpilka, Amir (ed.), 34th computational complexity conference, CCC 2019, New Brunswick, NJ, USA, July 18–20, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 137, Article 19, 43 p. (2019). MSC: 68Q25 PDFBibTeX XMLCite \textit{L. Chen} and \textit{R. R. Williams}, LIPIcs -- Leibniz Int. Proc. Inform. 137, Article 19, 43 p. (2019; Zbl 07564419) Full Text: DOI
Mckay, Dylan M.; Williams, Richard Ryan Quadratic time-space lower bounds for computing natural functions with a random oracle. (English) Zbl 07559099 Blum, Avrim (ed.), 10th innovations in theoretical computer science conference, ITCS 2019, January 10–12, 2019, San Diego, CA, USA. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 124, Article 56, 20 p. (2019). MSC: 68Qxx PDFBibTeX XMLCite \textit{D. M. Mckay} and \textit{R. R. Williams}, LIPIcs -- Leibniz Int. Proc. Inform. 124, Article 56, 20 p. (2019; Zbl 07559099) Full Text: DOI
Kane, Daniel M.; Williams, Richard Ryan The orthogonal vectors conjecture for branching programs and formulas. (English) Zbl 07559091 Blum, Avrim (ed.), 10th innovations in theoretical computer science conference, ITCS 2019, January 10–12, 2019, San Diego, CA, USA. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 124, Article 48, 15 p. (2019). MSC: 68Qxx PDFBibTeX XMLCite \textit{D. M. Kane} and \textit{R. R. Williams}, LIPIcs -- Leibniz Int. Proc. Inform. 124, Article 48, 15 p. (2019; Zbl 07559091) Full Text: DOI arXiv
Williams, R. Ryan Some estimated likelihoods for computational complexity. (English) Zbl 1482.68109 Steffen, Bernhard (ed.) et al., Computing and software science. State of the art and perspectives. Cham: Springer. Lect. Notes Comput. Sci. 10000, 9-26 (2019). MSC: 68Q25 68-02 PDFBibTeX XMLCite \textit{R. R. Williams}, Lect. Notes Comput. Sci. 10000, 9--26 (2019; Zbl 1482.68109) Full Text: DOI
McKay, Dylan M.; Murray, Cody D.; Williams, R. Ryan Weak lower bounds on resource-bounded compression imply strong separations of complexity classes. (English) Zbl 1434.68160 Charikar, Moses (ed.) et al., Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC ’19, Phoenix, AZ, USA, June 23–26, 2019. New York, NY: Association for Computing Machinery (ACM). 1215-1225 (2019). MSC: 68Q06 68P30 68Q15 68Q17 68Q30 68W27 PDFBibTeX XMLCite \textit{D. M. McKay} et al., in: Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC '19, Phoenix, AZ, USA, June 23--26, 2019. New York, NY: Association for Computing Machinery (ACM). 1215--1225 (2019; Zbl 1434.68160) Full Text: DOI Link
Chen, Lijie; Williams, Ryan An equivalence class for orthogonal vectors. (English) Zbl 1431.68046 Chan, Timothy M. (ed.), Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms, SODA 2019, San Diego, CA, USA, January 6–9, 2019. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 21-40 (2019). MSC: 68Q25 68P05 68Q17 68W25 PDFBibTeX XMLCite \textit{L. Chen} and \textit{R. Williams}, in: Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms, SODA 2019, San Diego, CA, USA, January 6--9, 2019. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 21--40 (2019; Zbl 1431.68046) Full Text: DOI arXiv
Björklund, Andreas; Kaski, Petteri; Williams, Ryan Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants. (English) Zbl 1430.68032 Algorithmica 81, No. 10, 4010-4028 (2019). MSC: 68P05 11T06 11Y16 15A15 68W30 PDFBibTeX XMLCite \textit{A. Björklund} et al., Algorithmica 81, No. 10, 4010--4028 (2019; Zbl 1430.68032) Full Text: DOI
Williams, Richard Ryan Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials. (English) Zbl 1441.68047 Servedio, Rocco A. (ed.), 33rd computational complexity conference, CCC 2018, June 22–24, 2018, San Diego, California, USA. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 102, Article 6, 24 p. (2018). MSC: 68Q06 68Q17 PDFBibTeX XMLCite \textit{R. R. Williams}, LIPIcs -- Leibniz Int. Proc. Inform. 102, Article 6, 24 p. (2018; Zbl 1441.68047) Full Text: DOI arXiv
Björklund, Andreas; Kaski, Petteri; Williams, Ryan Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants. (English) Zbl 1443.68043 Lokshtanov, Daniel (ed.) et al., 12th international symposium on parameterized and exact computation, IPEC 2017, Vienna, Austria, September 6–8, 2017. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 89, Article 6, 13 p. (2018). MSC: 68P05 11T06 11Y16 15A15 68W30 PDFBibTeX XMLCite \textit{A. Björklund} et al., LIPIcs -- Leibniz Int. Proc. Inform. 89, Article 6, 13 p. (2018; Zbl 1443.68043) Full Text: DOI
Williams, R. Ryan Counting solutions to polynomial systems via reductions. (English) Zbl 1433.68161 Seidel, Raimund (ed.), 1st symposium on simplicity in algorithms. SOSA 2018, January 7–10, 2018, New Orleans, LA, USA. Co-located with the 29th ACM-SIAM symposium on discrete algorithms (SODA 2018). Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. OASIcs – OpenAccess Ser. Inform. 61, Article 6, 15 p. (2018). MSC: 68Q17 11T06 13P15 68Q25 68W20 PDFBibTeX XMLCite \textit{R. R. Williams}, OASIcs -- OpenAccess Ser. Inform. 61, Article 6, 15 p. (2018; Zbl 1433.68161) Full Text: DOI
Murray, Cody; Williams, Ryan Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP. (English) Zbl 1428.68172 Diakonikolas, Ilias (ed.) et al., Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC ’18, Los Angeles, CA, USA, June 25–29, 2018. New York, NY: Association for Computing Machinery (ACM). 890-901 (2018). MSC: 68Q25 68Q06 68Q15 68Q17 PDFBibTeX XMLCite \textit{C. Murray} and \textit{R. Williams}, in: Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC '18, Los Angeles, CA, USA, June 25--29, 2018. New York, NY: Association for Computing Machinery (ACM). 890--901 (2018; Zbl 1428.68172) Full Text: DOI
Williams, Virginia Vassilevska; Williams, R. Ryan Subcubic equivalences between path, matrix, and triangle problems. (English) Zbl 1426.68133 J. ACM 65, No. 5, Article No. 27, 38 p. (2018). MSC: 68Q25 05C22 05C85 15B34 15B36 68R10 PDFBibTeX XMLCite \textit{V. V. Williams} and \textit{R. R. Williams}, J. ACM 65, No. 5, Article No. 27, 38 p. (2018; Zbl 1426.68133) Full Text: DOI
Williams, R. Ryan New algorithms and lower bounds for circuits with linear threshold gates. (English) Zbl 1410.68127 Theory Comput. 14, Paper No. 17, 25 p. (2018). MSC: 68Q05 68Q17 68Q25 68W40 94C10 PDFBibTeX XMLCite \textit{R. R. Williams}, Theory Comput. 14, Paper No. 17, 25 p. (2018; Zbl 1410.68127) Full Text: DOI arXiv
Williams, R. Ryan Faster all-pairs shortest paths via circuit complexity. (English) Zbl 1400.05075 SIAM J. Comput. 47, No. 5, 1965-1985 (2018). MSC: 05C12 05C38 05C20 05C76 05C85 68Q25 PDFBibTeX XMLCite \textit{R. R. Williams}, SIAM J. Comput. 47, No. 5, 1965--1985 (2018; Zbl 1400.05075) Full Text: DOI
Williams, Ryan On the difference between closest, furthest, and orthogonal pairs: nearly-linear vs barely-subquadratic complexity. (English) Zbl 1403.68321 Czumaj, Artur (ed.), Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms, SODA 2018, New Orleans, LA, USA, January 7–10, 2018. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-503-1/ebook). 1207-1215 (2018). MSC: 68U05 68Q25 PDFBibTeX XMLCite \textit{R. Williams}, in: Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms, SODA 2018, New Orleans, LA, USA, January 7--10, 2018. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1207--1215 (2018; Zbl 1403.68321) Full Text: arXiv Link
Murray, Cody D.; Williams, R. Ryan Easiness amplification and uniform circuit lower bounds. (English) Zbl 1440.68129 O’Donnell, Ryan (ed.), 32nd computational complexity conference, CCC 2017, July 6–9, 2017, Riga, Latvia. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 79, Article 8, 21 p. (2017). MSC: 68Q25 68Q06 PDFBibTeX XMLCite \textit{C. D. Murray} and \textit{R. R. Williams}, LIPIcs -- Leibniz Int. Proc. Inform. 79, Article 8, 21 p. (2017; Zbl 1440.68129) Full Text: DOI
Lokshtanov, Daniel; Paturi, Ramamohan; Tamaki, Suguru; Williams, Ryan; Yu, Huacheng Beating brute force for systems of polynomial equations over finite fields. (English) Zbl 1433.11135 Klein, Philip N. (ed.), Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16–19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2190-2202 (2017). MSC: 11T06 11Y16 PDFBibTeX XMLCite \textit{D. Lokshtanov} et al., in: Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16--19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2190--2202 (2017; Zbl 1433.11135) Full Text: DOI
Larsen, Kasper Green; Williams, Ryan Faster online matrix-vector multiplication. (English) Zbl 1410.68409 Klein, Philip N. (ed.), Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16–19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2182-2189 (2017). MSC: 68W27 15B34 65F30 68P05 68Q25 68W20 PDFBibTeX XMLCite \textit{K. G. Larsen} and \textit{R. Williams}, in: Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16--19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2182--2189 (2017; Zbl 1410.68409) Full Text: DOI arXiv
Murray, Cody D.; Williams, R. Ryan On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity. (English) Zbl 1378.68053 Theory Comput. 13, Paper No. 4, 22 p. (2017). MSC: 68Q17 68Q15 94C10 PDFBibTeX XMLCite \textit{C. D. Murray} and \textit{R. R. Williams}, Theory Comput. 13, Paper No. 4, 22 p. (2017; Zbl 1378.68053) Full Text: DOI
Koutis, Ioannis; Williams, Ryan Limits and applications of group algebras for parameterized problems. (English) Zbl 1445.68343 ACM Trans. Algorithms 12, No. 3, Article No. 31, 18 p. (2016). MSC: 68W20 68Q11 68Q27 68R10 68W30 PDFBibTeX XMLCite \textit{I. Koutis} and \textit{R. Williams}, ACM Trans. Algorithms 12, No. 3, Article No. 31, 18 p. (2016; Zbl 1445.68343) Full Text: DOI
Chan, Timothy M.; Williams, Ryan Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky. (English) Zbl 1410.68286 Krauthgamer, Robert (ed.), Proceedings of the 27th annual ACM-SIAM symposium on discrete algorithms, SODA 2016, Arlington, VA, USA, January 10–12, 2016. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1246-1255 (2016). MSC: 68R10 05C38 05C85 68Q25 PDFBibTeX XMLCite \textit{T. M. Chan} and \textit{R. Williams}, in: Proceedings of the 27th annual ACM-SIAM symposium on discrete algorithms, SODA 2016, Arlington, VA, USA, January 10--12, 2016. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1246--1255 (2016; Zbl 1410.68286) Full Text: DOI
Lincoln, Andrea; Williams, Virginia Vassilevska; Wang, Joshua R.; Williams, R. Ryan Deterministic time-space trade-offs for \(k\)-SUM. (English) Zbl 1388.68127 Chatzigiannakis, Ioannis (ed.) et al., 43rd international colloquium on automata, languages, and programming, ICALP 2016, Rome, Italy, July 12–15, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-013-2). LIPIcs – Leibniz International Proceedings in Informatics 55, Article 58, 14 p. (2016). MSC: 68Q25 PDFBibTeX XMLCite \textit{A. Lincoln} et al., LIPIcs -- Leibniz Int. Proc. Inform. 55, Article 58, 14 p. (2016; Zbl 1388.68127) Full Text: DOI arXiv
Williams, Richard Ryan Strong ETH breaks with Merlin and Arthur: short non-interactive proofs of batch evaluation. (English) Zbl 1380.68234 Raz, Ran (ed.), 31st conference on computational complexity, CCC’16, Tokyo, Japan, May 29 – June 1, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-008-8). LIPIcs – Leibniz International Proceedings in Informatics 50, Article 2, 17 p. (2016). MSC: 68Q25 03F20 68Q05 68Q10 68Q17 PDFBibTeX XMLCite \textit{R. R. Williams}, LIPIcs -- Leibniz Int. Proc. Inform. 50, Article 2, 17 p. (2016; Zbl 1380.68234) Full Text: DOI arXiv
Kane, Daniel M.; Williams, Ryan Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. (English) Zbl 1373.68220 Wichs, Daniel (ed.) et al., Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC ’16, Cambridge, MA, USA, June 19–21, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4132-5). 633-643 (2016). MSC: 68Q05 68Q17 94C10 PDFBibTeX XMLCite \textit{D. M. Kane} and \textit{R. Williams}, in: Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC '16, Cambridge, MA, USA, June 19--21, 2016. New York, NY: Association for Computing Machinery (ACM). 633--643 (2016; Zbl 1373.68220) Full Text: DOI arXiv
Abboud, Amir; Hansen, Thomas Dueholm; Williams, Virginia Vassilevska; Williams, Ryan Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made. (English) Zbl 1373.68233 Wichs, Daniel (ed.) et al., Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC ’16, Cambridge, MA, USA, June 19–21, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4132-5). 375-388 (2016). MSC: 68Q17 68Q25 PDFBibTeX XMLCite \textit{A. Abboud} et al., in: Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC '16, Cambridge, MA, USA, June 19--21, 2016. New York, NY: Association for Computing Machinery (ACM). 375--388 (2016; Zbl 1373.68233) Full Text: DOI arXiv
Williams, R. Ryan Natural proofs versus derandomization. (English) Zbl 1339.68101 SIAM J. Comput. 45, No. 2, 497-529 (2016). MSC: 68Q15 03F20 68Q17 94C10 PDFBibTeX XMLCite \textit{R. R. Williams}, SIAM J. Comput. 45, No. 2, 497--529 (2016; Zbl 1339.68101) Full Text: DOI arXiv
Williams, Virginia Vassilevska; Wang, Joshua R.; Williams, Ryan; Yu, Huacheng Finding four-node subgraphs in triangle time. (English) Zbl 1371.05292 Indyk, Piotr (ed.), Proceedings of the 26th annual ACM-SIAM symposium on discrete algorithms, SODA 2015, Portland, San Diego, CA, January 4–6, 2015. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-374-7; 978-1-61197-373-0/ebook). 1671-1680 (2015). MSC: 05C85 68Q25 PDFBibTeX XMLCite \textit{V. V. Williams} et al., in: Proceedings of the 26th annual ACM-SIAM symposium on discrete algorithms, SODA 2015, Portland, San Diego, CA, January 4--6, 2015. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1671--1680 (2015; Zbl 1371.05292) Full Text: DOI
Santhanam, Rahul; Williams, Ryan Beating exhaustive search for quantified Boolean formulas and connections to circuit complexity. (English) Zbl 1371.68123 Indyk, Piotr (ed.), Proceedings of the 26th annual ACM-SIAM symposium on discrete algorithms, SODA 2015, Portland, San Diego, CA, January 4–6, 2015. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-374-7; 978-1-61197-373-0/ebook). 231-241 (2015). MSC: 68Q25 68Q15 68W20 94C10 PDFBibTeX XMLCite \textit{R. Santhanam} and \textit{R. Williams}, in: Proceedings of the 26th annual ACM-SIAM symposium on discrete algorithms, SODA 2015, Portland, San Diego, CA, January 4--6, 2015. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 231--241 (2015; Zbl 1371.68123) Full Text: DOI
Abboud, Amir; Williams, Ryan; Yu, Huacheng More applications of the polynomial method to algorithm design. (English) Zbl 1372.68282 Indyk, Piotr (ed.), Proceedings of the 26th annual ACM-SIAM symposium on discrete algorithms, SODA 2015, Portland, San Diego, CA, January 4–6, 2015. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-374-7; 978-1-61197-373-0/ebook). 218-230 (2015). MSC: 68W01 68Q17 68Q25 68W20 PDFBibTeX XMLCite \textit{A. Abboud} et al., in: Proceedings of the 26th annual ACM-SIAM symposium on discrete algorithms, SODA 2015, Portland, San Diego, CA, January 4--6, 2015. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 218--230 (2015; Zbl 1372.68282) Full Text: DOI
Williams, R. Ryan Thinking algorithmically about impossibility (invited talk). (English) Zbl 1373.68245 Kreutzer, Stephan (ed.), 24th EACSL annual conference and 29th workshop on computer science logic, CSL’15, Berlin, Germany, September 7–10, 2015. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-90-3). LIPIcs – Leibniz International Proceedings in Informatics 41, 14-23 (2015). MSC: 68Q17 68N30 68Q25 68W20 PDFBibTeX XMLCite \textit{R. R. Williams}, LIPIcs -- Leibniz Int. Proc. Inform. 41, 14--23 (2015; Zbl 1373.68245) Full Text: DOI
Chapman, Brynmor; Williams, Ryan The circuit-input game, natural proofs, and testing circuits with data. (English) Zbl 1364.68193 Proceedings of the 6th conference on innovations in theoretical computer science, ITCS’15, Rehovot, Israel, January 11–13, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3333-7). 263-270 (2015). MSC: 68Q05 68Q15 68Q17 91A80 94C10 94C12 PDFBibTeX XMLCite \textit{B. Chapman} and \textit{R. Williams}, in: Proceedings of the 6th conference on innovations in theoretical computer science, ITCS'15, Rehovot, Israel, January 11--13, 2015. New York, NY: Association for Computing Machinery (ACM). 263--270 (2015; Zbl 1364.68193) Full Text: DOI
Buss, Samuel R.; Williams, Ryan Limits on alternation trading proofs for time-space lower bounds. (English) Zbl 1338.68080 Comput. Complexity 24, No. 3, 533-600 (2015). Reviewer: Gregory Loren McColm (Tampa) MSC: 68Q15 68Q17 68Q25 PDFBibTeX XMLCite \textit{S. R. Buss} and \textit{R. Williams}, Comput. Complexity 24, No. 3, 533--600 (2015; Zbl 1338.68080) Full Text: DOI
Williams, Richard Ryan The polynomial method in circuit complexity applied to algorithm design (invited talk). (English) Zbl 1436.68392 Raman, Venkatesh (ed.) et al., 34th international conference on foundation of software technology and theoretical computer science, FSTTCS 2014, New Delhi, India, December 15–17, 2014. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 29, 47-60 (2014). MSC: 68W01 68Q06 PDFBibTeX XMLCite \textit{R. R. Williams}, LIPIcs -- Leibniz Int. Proc. Inform. 29, 47--60 (2014; Zbl 1436.68392) Full Text: DOI
Williams, Ryan Faster decision of first-order graph properties. (English) Zbl 1394.68192 Proceedings of the joint meeting of the twenty-third EACSL annual conference on computer science logic, CSL, and the 2014 29th annual ACM/IEEE symposium on logic in computer science, LICS 2014, Vienna, Austria, July 14–18, 2014. Los Alamitos, CA: IEEE Computer Society (ISBN 978-1-4503-2886-9). Paper No. 80, 6 p. (2014). MSC: 68Q25 03B10 05C85 68R10 PDFBibTeX XMLCite \textit{R. Williams}, in: Proceedings of the joint meeting of the twenty-third EACSL annual conference on computer science logic, CSL, and the 2014 29th annual ACM/IEEE symposium on logic in computer science, LICS 2014, Vienna, Austria, July 14--18, 2014. Los Alamitos, CA: IEEE Computer Society. Paper No. 80, 6 p. (2014; Zbl 1394.68192) Full Text: DOI
Williams, Ryan Algorithms for circuits and circuits for algorithms: connecting the tractable and intractable. (English) Zbl 1373.68246 Jang, Sun Young (ed.) et al., Proceedings of the International Congress of Mathematicians (ICM 2014), Seoul, Korea, August 13–21, 2014. Vol. IV: Invited lectures. Seoul: KM Kyung Moon Sa (ISBN 978-89-6105-807-0/hbk; 978-89-6105-803-2/set). 659-682 (2014). MSC: 68Q17 68Q25 PDFBibTeX XMLCite \textit{R. Williams}, in: Proceedings of the International Congress of Mathematicians (ICM 2014), Seoul, Korea, August 13--21, 2014. Vol. IV: Invited lectures. Seoul: KM Kyung Moon Sa. 659--682 (2014; Zbl 1373.68246)
Williams, Ryan New algorithms and lower bounds for circuits with linear threshold gates. (English) Zbl 1315.68142 Proceedings of the 46th annual ACM symposium on theory of computing, STOC ’14, New York, NY, USA, May 31 – June 3, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2710-7). 194-202 (2014). MSC: 68Q17 68Q15 68W05 94C10 PDFBibTeX XMLCite \textit{R. Williams}, in: Proceedings of the 46th annual ACM symposium on theory of computing, STOC '14, New York, NY, USA, May 31 -- June 3, 2014. New York, NY: Association for Computing Machinery (ACM). 194--202 (2014; Zbl 1315.68142) Full Text: DOI arXiv
Santhanam, Rahul; Williams, Ryan On uniformity and circuit lower bounds. (English) Zbl 1314.68139 Comput. Complexity 23, No. 2, 177-205 (2014). MSC: 68Q15 68Q17 94C10 PDFBibTeX XMLCite \textit{R. Santhanam} and \textit{R. Williams}, Comput. Complexity 23, No. 2, 177--205 (2014; Zbl 1314.68139) Full Text: DOI Link
Abboud, Amir; Lewi, Kevin; Williams, Ryan Losing weight by gaining edges. (English) Zbl 1423.68197 Schulz, Andreas S. (ed.) et al., Algorithms – ESA 2014. 22nd annual European symposium, Wrocław, Poland, September 8–10, 2014. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 8737, 1-12 (2014). MSC: 68Q25 05C22 05C69 68Q17 PDFBibTeX XMLCite \textit{A. Abboud} et al., Lect. Notes Comput. Sci. 8737, 1--12 (2014; Zbl 1423.68197) Full Text: DOI arXiv
Williams, Ryan Nonuniform ACC circuit lower bounds. (English) Zbl 1295.68117 J. ACM 61, No. 1, Article No. 2, 32 p. (2014). MSC: 68Q15 68Q17 68Q25 94C10 PDFBibTeX XMLCite \textit{R. Williams}, J. ACM 61, No. 1, Article No. 2, 32 p. (2014; Zbl 1295.68117) Full Text: DOI
Williams, Ryan Alternation-trading proofs, linear programming, and lower bounds. (English) Zbl 1322.68091 ACM Trans. Comput. Theory 5, No. 2, Article No. 6, 49 p. (2013). MSC: 68Q17 68Q25 90C05 PDFBibTeX XMLCite \textit{R. Williams}, ACM Trans. Comput. Theory 5, No. 2, Article No. 6, 49 p. (2013; Zbl 1322.68091) Full Text: DOI Link
Williams, Ryan Natural proofs versus derandomization. (English) Zbl 1293.68135 Proceedings of the 45th annual ACM symposium on theory of computing, STOC ’13. Palo Alto, CA, USA, June 1–4, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2029-0). 21-30 (2013). MSC: 68Q15 03F20 68Q17 94C10 PDFBibTeX XMLCite \textit{R. Williams}, in: Proceedings of the 45th annual ACM symposium on theory of computing, STOC '13. Palo Alto, CA, USA, June 1--4, 2013. New York, NY: Association for Computing Machinery (ACM). 21--30 (2013; Zbl 1293.68135) Full Text: DOI arXiv
Williams, Ryan Improving exhaustive search implies superpolynomial lower bounds. (English) Zbl 1275.68071 SIAM J. Comput. 42, No. 3, 1218-1244 (2013). MSC: 68Q15 68Q17 PDFBibTeX XMLCite \textit{R. Williams}, SIAM J. Comput. 42, No. 3, 1218--1244 (2013; Zbl 1275.68071) Full Text: DOI
Williams, Virginia Vassilevska; Williams, Ryan Finding, minimizing, and counting weighted subgraphs. (English) Zbl 1275.68080 SIAM J. Comput. 42, No. 3, 831-854 (2013). MSC: 68Q25 68W40 05C85 68Q17 68W05 PDFBibTeX XMLCite \textit{V. V. Williams} and \textit{R. Williams}, SIAM J. Comput. 42, No. 3, 831--854 (2013; Zbl 1275.68080) Full Text: DOI
Lipton, Richard J.; Williams, Ryan Amplifying circuit lower bounds against polynomial time, with applications. (English) Zbl 1286.68170 Comput. Complexity 22, No. 2, 311-343 (2013). MSC: 68Q15 68Q17 PDFBibTeX XMLCite \textit{R. J. Lipton} and \textit{R. Williams}, Comput. Complexity 22, No. 2, 311--343 (2013; Zbl 1286.68170) Full Text: DOI
Williams, Ryan Towards NEXP versus BPP? (English) Zbl 1381.68092 Bulatov, Andrei A. (ed.) et al., Computer science – theory and applications. 8th international computer science symposium in Russia, CSR 2013, Ekaterinburg, Russia, June 25–29, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-38535-3/pbk). Lecture Notes in Computer Science 7913, 174-182 (2013). MSC: 68Q15 68Q17 PDFBibTeX XMLCite \textit{R. Williams}, Lect. Notes Comput. Sci. 7913, 174--182 (2013; Zbl 1381.68092) Full Text: DOI
Bansal, Nikhil; Williams, Ryan Regularity lemmas and combinatorial algorithms. (English) Zbl 1253.68162 Theory Comput. 8, Paper No. 4, 69-94 (2012). MSC: 68Q25 68R05 05C85 68W20 68P05 PDFBibTeX XMLCite \textit{N. Bansal} and \textit{R. Williams}, Theory Comput. 8, Paper No. 4, 69--94 (2012; Zbl 1253.68162) Full Text: DOI
Kim, Eun Jung; Williams, Ryan Improved parameterized algorithms for above average constraint satisfaction. (English) Zbl 1352.68115 Marx, Dániel (ed.) et al., Parameterized and exact computation. 6th international symposium, IPEC 2011, Saarbrücken, Germany, September 6–8, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-28049-8/pbk). Lecture Notes in Computer Science 7112, 118-131 (2012). MSC: 68Q25 68T20 68W40 PDFBibTeX XMLCite \textit{E. J. Kim} and \textit{R. Williams}, Lect. Notes Comput. Sci. 7112, 118--131 (2012; Zbl 1352.68115) Full Text: DOI arXiv
Diehl, Scott; van Melkebeek, Dieter; Williams, Ryan An improved time-space lower bound for tautologies. (English) Zbl 1229.90158 J. Comb. Optim. 22, No. 3, 325-338 (2011). MSC: 90C27 90C60 PDFBibTeX XMLCite \textit{S. Diehl} et al., J. Comb. Optim. 22, No. 3, 325--338 (2011; Zbl 1229.90158) Full Text: DOI
Williams, Ryan Parallelizing time with polynomial circuits. (English) Zbl 1209.68256 Theory Comput. Syst. 48, No. 1, 150-169 (2011). MSC: 68Q05 68Q10 68Q15 94C10 PDFBibTeX XMLCite \textit{R. Williams}, Theory Comput. Syst. 48, No. 1, 150--169 (2011; Zbl 1209.68256) Full Text: DOI
Vassilevska, Virginia; Williams, Ryan; Yuster, Raphael Finding heaviest \(H\)-subgraphs in real weighted graphs, with applications. (English) Zbl 1300.05307 ACM Trans. Algorithms 6, No. 3, Article No. 44, 23 p. (2010). MSC: 05C85 05C50 05C78 68Q25 68R10 PDFBibTeX XMLCite \textit{V. Vassilevska} et al., ACM Trans. Algorithms 6, No. 3, Article No. 44, 23 p. (2010; Zbl 1300.05307) Full Text: DOI
Williams, Ryan Improving exhaustive search implies superpolynomial lower bounds. (English) Zbl 1293.68177 Proceedings of the 42nd annual ACM symposium on theory of computing, STOC ’10. Cambridge, MA, USA, June 5–8, 2010. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-817-9). 231-240 (2010). MSC: 68Q25 68Q15 68Q17 PDFBibTeX XMLCite \textit{R. Williams}, in: Proceedings of the 42nd annual ACM symposium on theory of computing, STOC '10. Cambridge, MA, USA, June 5--8, 2010. New York, NY: Association for Computing Machinery (ACM). 231--240 (2010; Zbl 1293.68177) Full Text: DOI
Pătraşcu, Mihai; Williams, Ryan On the possibility of faster SAT algorithms. (English) Zbl 1288.68135 Charikar, Moses (ed.), Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, TX, USA, January 17–19, 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-0-89871-698-6/CD-ROM). 1065-1075 (2010). MSC: 68Q25 68Q17 03D15 03B05 PDFBibTeX XMLCite \textit{M. Pătraşcu} and \textit{R. Williams}, in: Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, TX, USA, January 17--19, 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1065--1075 (2010; Zbl 1288.68135)
Blocki, Jeremiah; Williams, Ryan Resolving the complexity of some data privacy problems. (English) Zbl 1288.68058 Abramsky, Samson (ed.) et al., Automata, languages and programming. 37th international colloquium, ICALP 2010, Bordeaux, France, July 6–10, 2010. Proceedings, Part II. Berlin: Springer (ISBN 978-3-642-14161-4/pbk). Lecture Notes in Computer Science 6199, 393-404 (2010). MSC: 68P15 68Q17 68Q25 PDFBibTeX XMLCite \textit{J. Blocki} and \textit{R. Williams}, Lect. Notes Comput. Sci. 6199, 393--404 (2010; Zbl 1288.68058) Full Text: DOI arXiv
Bansal, Nikhil; Williams, Ryan Regularity lemmas and combinatorial algorithms. (English) Zbl 1292.05242 2009 IEEE 50th annual symposium on foundations of computer science – FOCS 2009. Proceedings of the symposium, Atlanta, GA, USA, October 24–27, 2009. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-3850-1; 978-1-4244-5116-6/ebook). 745-754 (2009). MSC: 05C85 68Q25 68R05 68W20 68P05 05C69 PDFBibTeX XMLCite \textit{N. Bansal} and \textit{R. Williams}, in: 2009 IEEE 50th annual symposium on foundations of computer science -- FOCS 2009. Proceedings of the symposium, Atlanta, GA, USA, October 24--27, 2009. Los Alamitos, CA: IEEE Computer Society. 745--754 (2009; Zbl 1292.05242) Full Text: DOI
Vassilevska, Virginia; Williams, Ryan; Yuster, Raphael All pairs bottleneck paths and max-min matrix products in truly subcubic time. (English) Zbl 1213.68338 Theory Comput. 5, Paper No. 9, 173-189 (2009). MSC: 68Q25 05C85 68R10 PDFBibTeX XMLCite \textit{V. Vassilevska} et al., Theory Comput. 5, Paper No. 9, 173--189 (2009; Zbl 1213.68338) Full Text: DOI
Diehl, Scott; van Melkebeek, Dieter; Williams, Ryan An improved time-space lower bound for tautologies. (English) Zbl 1248.03078 Ngo, Hung Q. (ed.), Computing and combinatorics. 15th annual international conference, COCOON 2009, Niagara Falls, NY, USA, July 13–15, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-02881-6/pbk). Lecture Notes in Computer Science 5609, 429-438 (2009). MSC: 03F20 68Q17 PDFBibTeX XMLCite \textit{S. Diehl} et al., Lect. Notes Comput. Sci. 5609, 429--438 (2009; Zbl 1248.03078) Full Text: DOI
Koutis, Ioannis; Williams, Ryan Limits and applications of group algebras for parameterized problems. (English) Zbl 1248.68251 Albers, Susanne (ed.) et al., Automata, languages and programming. 36th international colloquium, ICALP 2009, Rhodes, Greece, July 5–12, 2009. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-02926-4/pbk). Lecture Notes in Computer Science 5555, 653-664 (2009). MSC: 68Q25 68W20 PDFBibTeX XMLCite \textit{I. Koutis} and \textit{R. Williams}, Lect. Notes Comput. Sci. 5555, 653--664 (2009; Zbl 1248.68251) Full Text: DOI Link
Williams, R. Ryan Time-space tradeoffs for counting NP solutions modulo integers. (English) Zbl 1149.68034 Comput. Complexity 17, No. 2, 179-219 (2008). MSC: 68Q15 68Q17 PDFBibTeX XMLCite \textit{R. R. Williams}, Comput. Complexity 17, No. 2, 179--219 (2008; Zbl 1149.68034) Full Text: DOI Link
Williams, Ryan Matrix-vector multiplication in sub-quadratic time (some preprocessing required). (English) Zbl 1302.65111 Proceedings of the eighteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2007, New Orleans, LA, USA, January 7–9, 2007. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 978-0-89871-624-5). 995-1001 (2007). MSC: 65F30 65Y20 68Q25 PDFBibTeX XMLCite \textit{R. Williams}, in: Proceedings of the eighteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2007, New Orleans, LA, USA, January 7--9, 2007. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 995--1001 (2007; Zbl 1302.65111)
Vassilevska, Virginia; Williams, Ryan; Woo, Shan Leung Maverick Confronting hardness using a hybrid approach. (English) Zbl 1192.68381 Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, January 22–24, 2006. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 0-89871-605-5). 1-10 (2006). MSC: 68Q25 68Q17 PDFBibTeX XMLCite \textit{V. Vassilevska} et al., in: Proceedings of the seventeenth annual ACM-SIAM symposium on discrete algorithms, SODA 2006, Miami, FL, January 22--24, 2006. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 1--10 (2006; Zbl 1192.68381) Full Text: DOI
Vassilevska, Virginia; Williams, Ryan; Yuster, Raphael Finding the smallest \(H\)-subgraph in real weighted graphs and related problems. (English) Zbl 1223.05302 Bugliesi, Michele (ed.) et al., Automata, languages and programming. 33rd international colloquium, ICALP 2006, Venice, Italy, July 10–14, 2006. Proceedings, Part I. Berlin: Springer (ISBN 978-3-540-35904-3/pbk). Lecture Notes in Computer Science 4051, 262-273 (2006). MSC: 05C85 05C22 68Q25 PDFBibTeX XMLCite \textit{V. Vassilevska} et al., Lect. Notes Comput. Sci. 4051, 262--273 (2006; Zbl 1223.05302) Full Text: DOI
Williams, Ryan On computing \(k\)-CNF formula properties. (English) Zbl 1204.68212 Giunchiglia, Enrico (ed.) et al., Theory and applications of satisfiability testing. 6th international conference, SAT 2003, Santa Margherita Ligure, Italy, May 5–8, 2003. Selected revised papers. Berlin: Springer (ISBN 3-540-20851-8/pbk). Lect. Notes Comput. Sci. 2919, 330-340 (2004). MSC: 68T20 03B05 68Q25 68T05 PDFBibTeX XMLCite \textit{R. Williams}, Lect. Notes Comput. Sci. 2919, 330--340 (2004; Zbl 1204.68212) Full Text: DOI
Williams, Ryan A new algorithm for optimal constraint satisfaction and its implications. (English) Zbl 1098.68120 Díaz, Josep (ed.) et al., Automata, languages and programming. 31st international colloquium, ICALP 2004, Turku, Finland, July 12–16, 2004. Proceedings. Berlin: Springer (ISBN 3-540-22849-7/pbk). Lecture Notes in Computer Science 3142, 1227-1237 (2004). MSC: 68T20 68Q25 PDFBibTeX XMLCite \textit{R. Williams}, Lect. Notes Comput. Sci. 3142, 1227--1237 (2004; Zbl 1098.68120) Full Text: DOI