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, 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
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
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
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
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, 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, 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 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
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
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, 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
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 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
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
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
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