Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Ce Jin. An Improved FPTAS for 0-1 Knapsack. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 76:1-76:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{jin:LIPIcs.ICALP.2019.76, author = {Jin, Ce}, title = {{An Improved FPTAS for 0-1 Knapsack}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {76:1--76:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.76}, URN = {urn:nbn:de:0030-drops-106527}, doi = {10.4230/LIPIcs.ICALP.2019.76}, annote = {Keywords: approximation algorithms, knapsack, subset sum} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Daniel M. Kane and Richard Ryan Williams. The Orthogonal Vectors Conjecture for Branching Programs and Formulas. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 48:1-48:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{kane_et_al:LIPIcs.ITCS.2019.48, author = {Kane, Daniel M. and Williams, Richard Ryan}, title = {{The Orthogonal Vectors Conjecture for Branching Programs and Formulas}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {48:1--48:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.48}, URN = {urn:nbn:de:0030-drops-101418}, doi = {10.4230/LIPIcs.ITCS.2019.48}, annote = {Keywords: fine-grained complexity, orthogonal vectors, branching programs, symmetric functions, Boolean formulas} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Dylan M. McKay and Richard Ryan Williams. Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 56:1-56:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{mckay_et_al:LIPIcs.ITCS.2019.56, author = {McKay, Dylan M. and Williams, Richard Ryan}, title = {{Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {56:1--56:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.56}, URN = {urn:nbn:de:0030-drops-101493}, doi = {10.4230/LIPIcs.ITCS.2019.56}, annote = {Keywords: branching programs, random oracles, time-space tradeoffs, lower bounds, SAT, counting complexity} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Richard Ryan Williams. Lower Bounds by Algorithm Design: A Progress Report (Invited Paper). In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, p. 4:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{williams:LIPIcs.ICALP.2018.4, author = {Williams, Richard Ryan}, title = {{Lower Bounds by Algorithm Design: A Progress Report}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {4:1--4:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.4}, URN = {urn:nbn:de:0030-drops-90088}, doi = {10.4230/LIPIcs.ICALP.2018.4}, annote = {Keywords: circuit complexity, satisfiability, derandomization} }
Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)
Richard Ryan Williams. Limits on Representing Boolean Functions by Linear Combinations of Simple Functions: Thresholds, ReLUs, and Low-Degree Polynomials. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 6:1-6:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{williams:LIPIcs.CCC.2018.6, author = {Williams, Richard Ryan}, title = {{Limits on Representing Boolean Functions by Linear Combinations of Simple Functions: Thresholds, ReLUs, and Low-Degree Polynomials}}, booktitle = {33rd Computational Complexity Conference (CCC 2018)}, pages = {6:1--6:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-069-9}, ISSN = {1868-8969}, year = {2018}, volume = {102}, editor = {Servedio, Rocco A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.6}, URN = {urn:nbn:de:0030-drops-88846}, doi = {10.4230/LIPIcs.CCC.2018.6}, annote = {Keywords: linear threshold functions, lower bounds, neural networks, low-degree polynomials} }
Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)
Richard Ryan Williams. Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 2:1-2:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{williams:LIPIcs.CCC.2016.2, author = {Williams, Richard Ryan}, title = {{Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation}}, booktitle = {31st Conference on Computational Complexity (CCC 2016)}, pages = {2:1--2:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-008-8}, ISSN = {1868-8969}, year = {2016}, volume = {50}, editor = {Raz, Ran}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.2}, URN = {urn:nbn:de:0030-drops-58307}, doi = {10.4230/LIPIcs.CCC.2016.2}, annote = {Keywords: counting complexity, exponential-time hypothesis, interactive proofs, Merlin-Arthur games} }
Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Richard Ryan Williams. The Polynomial Method in Circuit Complexity Applied to Algorithm Design (Invited Talk). In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 47-60, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)
@InProceedings{williams:LIPIcs.FSTTCS.2014.47, author = {Williams, Richard Ryan}, title = {{The Polynomial Method in Circuit Complexity Applied to Algorithm Design}}, booktitle = {34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)}, pages = {47--60}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-77-4}, ISSN = {1868-8969}, year = {2014}, volume = {29}, editor = {Raman, Venkatesh and Suresh, S. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.47}, URN = {urn:nbn:de:0030-drops-48328}, doi = {10.4230/LIPIcs.FSTTCS.2014.47}, annote = {Keywords: algorithm design, circuit complexity, polynomial method} }
Feedback for Dagstuhl Publishing