Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Soh Kumabe and Yuichi Yoshida. Average Sensitivity of the Knapsack Problem. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 75:1-75:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{kumabe_et_al:LIPIcs.ESA.2022.75, author = {Kumabe, Soh and Yoshida, Yuichi}, title = {{Average Sensitivity of the Knapsack Problem}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {75:1--75:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.75}, URN = {urn:nbn:de:0030-drops-170136}, doi = {10.4230/LIPIcs.ESA.2022.75}, annote = {Keywords: Average Sensitivity, Knapsack Problem, FPRAS} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Nathaniel Harms and Yuichi Yoshida. Downsampling for Testing and Learning in Product Distributions. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 71:1-71:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{harms_et_al:LIPIcs.ICALP.2022.71, author = {Harms, Nathaniel and Yoshida, Yuichi}, title = {{Downsampling for Testing and Learning in Product Distributions}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {71:1--71:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.71}, URN = {urn:nbn:de:0030-drops-164123}, doi = {10.4230/LIPIcs.ICALP.2022.71}, annote = {Keywords: property testing, learning, monotonicity, halfspaces, intersections of halfspaces, polynomial threshold functions} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, and Yuichi Yoshida. One-Tape Turing Machine and Branching Program Lower Bounds for MCSP. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 23:1-23:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{cheraghchi_et_al:LIPIcs.STACS.2021.23, author = {Cheraghchi, Mahdi and Hirahara, Shuichi and Myrisiotis, Dimitrios and Yoshida, Yuichi}, title = {{One-Tape Turing Machine and Branching Program Lower Bounds for MCSP}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {23:1--23:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.23}, URN = {urn:nbn:de:0030-drops-136681}, doi = {10.4230/LIPIcs.STACS.2021.23}, annote = {Keywords: Minimum Circuit Size Problem, Kolmogorov Complexity, One-Tape Turing Machines, Branching Programs, Lower Bounds, Pseudorandom Generators, Hitting Set Generators} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Omri Ben-Eliezer, Eldar Fischer, Amit Levi, and Yuichi Yoshida. Ordered Graph Limits and Their Applications. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 42:1-42:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{beneliezer_et_al:LIPIcs.ITCS.2021.42, author = {Ben-Eliezer, Omri and Fischer, Eldar and Levi, Amit and Yoshida, Yuichi}, title = {{Ordered Graph Limits and Their Applications}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {42:1--42:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.42}, URN = {urn:nbn:de:0030-drops-135815}, doi = {10.4230/LIPIcs.ITCS.2021.42}, annote = {Keywords: graph limits, ordered graph, graphon, cut distance, removal lemma} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Yuichi Yoshida and Samson Zhou. Sensitivity Analysis of the Maximum Matching Problem. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 58:1-58:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{yoshida_et_al:LIPIcs.ITCS.2021.58, author = {Yoshida, Yuichi and Zhou, Samson}, title = {{Sensitivity Analysis of the Maximum Matching Problem}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {58:1--58:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.58}, URN = {urn:nbn:de:0030-drops-135979}, doi = {10.4230/LIPIcs.ITCS.2021.58}, annote = {Keywords: Sensitivity analysis, maximum matching, graph algorithms} }
Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Richard Santiago and Yuichi Yoshida. Weakly Submodular Function Maximization Using Local Submodularity Ratio. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 64:1-64:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{santiago_et_al:LIPIcs.ISAAC.2020.64, author = {Santiago, Richard and Yoshida, Yuichi}, title = {{Weakly Submodular Function Maximization Using Local Submodularity Ratio}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {64:1--64:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.64}, URN = {urn:nbn:de:0030-drops-134082}, doi = {10.4230/LIPIcs.ISAAC.2020.64}, annote = {Keywords: weakly submodular, non-monotone, local submodularity ratio} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Noah Fleming and Yuichi Yoshida. Distribution-Free Testing of Linear Functions on ℝⁿ. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 22:1-22:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{fleming_et_al:LIPIcs.ITCS.2020.22, author = {Fleming, Noah and Yoshida, Yuichi}, title = {{Distribution-Free Testing of Linear Functions on \mathbb{R}ⁿ}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {22:1--22:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.22}, URN = {urn:nbn:de:0030-drops-117076}, doi = {10.4230/LIPIcs.ITCS.2020.22}, annote = {Keywords: Property Testing, Distribution-Free Testing, Linearity Testing} }
Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Amit Levi and Yuichi Yoshida. Sublinear-Time Quadratic Minimization via Spectral Decomposition of Matrices. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 17:1-17:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{levi_et_al:LIPIcs.APPROX-RANDOM.2018.17, author = {Levi, Amit and Yoshida, Yuichi}, title = {{Sublinear-Time Quadratic Minimization via Spectral Decomposition of Matrices}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)}, pages = {17:1--17:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-085-9}, ISSN = {1868-8969}, year = {2018}, volume = {116}, editor = {Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.17}, URN = {urn:nbn:de:0030-drops-94210}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.17}, annote = {Keywords: Qudratic function minimization, Approximation Algorithms, Matrix spectral decomposition, Graph limits} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Tasuku Soma and Yuichi Yoshida. A New Approximation Guarantee for Monotone Submodular Function Maximization via Discrete Convexity. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 99:1-99:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{soma_et_al:LIPIcs.ICALP.2018.99, author = {Soma, Tasuku and Yoshida, Yuichi}, title = {{A New Approximation Guarantee for Monotone Submodular Function Maximization via Discrete Convexity}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {99:1--99:14}, 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.99}, URN = {urn:nbn:de:0030-drops-91033}, doi = {10.4230/LIPIcs.ICALP.2018.99}, annote = {Keywords: Submodular Function, Approximation Algorithm, Discrete Convex Analysis} }
Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Chien-Chung Huang, Naonori Kakimura, and Yuichi Yoshida. Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 11:1-11:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{huang_et_al:LIPIcs.APPROX-RANDOM.2017.11, author = {Huang, Chien-Chung and Kakimura, Naonori and Yoshida, Yuichi}, title = {{Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {11:1--11:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-044-6}, ISSN = {1868-8969}, year = {2017}, volume = {81}, editor = {Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.11}, URN = {urn:nbn:de:0030-drops-75602}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.11}, annote = {Keywords: submodular functions, single-pass streaming, multiple-pass streaming, constant approximation} }
Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Suguru Tamaki and Yuichi Yoshida. Robust Approximation of Temporal CSP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 419-432, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)
@InProceedings{tamaki_et_al:LIPIcs.APPROX-RANDOM.2014.419, author = {Tamaki, Suguru and Yoshida, Yuichi}, title = {{Robust Approximation of Temporal CSP}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {419--432}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-74-3}, ISSN = {1868-8969}, year = {2014}, volume = {28}, editor = {Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.419}, URN = {urn:nbn:de:0030-drops-47135}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.419}, annote = {Keywords: constraint satisfaction, maximum satisfiability, approximation algorithm, hardness of approximation, infinite domain} }
Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Yoichi Iwata and Yuichi Yoshida. Exact and Approximation Algorithms for the Maximum Constraint Satisfaction Problem over the Point Algebra. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 127-138, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2013)
@InProceedings{iwata_et_al:LIPIcs.STACS.2013.127, author = {Iwata, Yoichi and Yoshida, Yuichi}, title = {{Exact and Approximation Algorithms for the Maximum Constraint Satisfaction Problem over the Point Algebra}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {127--138}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-50-7}, ISSN = {1868-8969}, year = {2013}, volume = {20}, editor = {Portier, Natacha and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.127}, URN = {urn:nbn:de:0030-drops-39282}, doi = {10.4230/LIPIcs.STACS.2013.127}, annote = {Keywords: Constraint Satisfaction Problems, Point Algebra, Exact Algorithms, Approximation Algorithms} }
Feedback for Dagstuhl Publishing