Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, and Rocco A. Servedio. Testing Intersecting and Union-Closed Families. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 33:1-33:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chen_et_al:LIPIcs.ITCS.2024.33, author = {Chen, Xi and De, Anindya and Li, Yuhao and Nadimpalli, Shivam and Servedio, Rocco A.}, title = {{Testing Intersecting and Union-Closed Families}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {33:1--33:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.33}, URN = {urn:nbn:de:0030-drops-195610}, doi = {10.4230/LIPIcs.ITCS.2024.33}, annote = {Keywords: Sublinear algorithms, property testing, computational complexity, monotonicity, intersecting families, union-closed families} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Pavel Hubáček, Erfan Khaniki, and Neil Thapen. TFNP Intersections Through the Lens of Feasible Disjunction. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 63:1-63:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{hubacek_et_al:LIPIcs.ITCS.2024.63, author = {Hub\'{a}\v{c}ek, Pavel and Khaniki, Erfan and Thapen, Neil}, title = {{TFNP Intersections Through the Lens of Feasible Disjunction}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {63:1--63:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.63}, URN = {urn:nbn:de:0030-drops-195917}, doi = {10.4230/LIPIcs.ITCS.2024.63}, annote = {Keywords: TFNP, feasible disjunction, proof complexity, TFNP intersection classes} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Yuhao Li, William Pires, and Robert Robere. Intersection Classes in TFNP and Proof Complexity. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 74:1-74:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{li_et_al:LIPIcs.ITCS.2024.74, author = {Li, Yuhao and Pires, William and Robere, Robert}, title = {{Intersection Classes in TFNP and Proof Complexity}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {74:1--74:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.74}, URN = {urn:nbn:de:0030-drops-196023}, doi = {10.4230/LIPIcs.ITCS.2024.74}, annote = {Keywords: TFNP, Proof Complexity, Intersection Classes} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Jiawei Li. Total NP Search Problems with Abundant Solutions. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 75:1-75:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{li:LIPIcs.ITCS.2024.75, author = {Li, Jiawei}, title = {{Total NP Search Problems with Abundant Solutions}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {75:1--75:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.75}, URN = {urn:nbn:de:0030-drops-196031}, doi = {10.4230/LIPIcs.ITCS.2024.75}, annote = {Keywords: TFNP, Pigeonhole Principle} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Jingxun Liang, Zhihao Gavin Tang, Yixuan Even Xu, Yuhao Zhang, and Renfei Zhou. On the Perturbation Function of Ranking and Balance for Weighted Online Bipartite Matching. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 80:1-80:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{liang_et_al:LIPIcs.ESA.2023.80, author = {Liang, Jingxun and Tang, Zhihao Gavin and Xu, Yixuan Even and Zhang, Yuhao and Zhou, Renfei}, title = {{On the Perturbation Function of Ranking and Balance for Weighted Online Bipartite Matching}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {80:1--80:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.80}, URN = {urn:nbn:de:0030-drops-187334}, doi = {10.4230/LIPIcs.ESA.2023.80}, annote = {Keywords: Online Matching, AdWords, Ranking, Water-Filling} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Enze Sun, Zonghan Yang, and Yuhao Zhang. Improved Algorithms for Online Rent Minimization Problem Under Unit-Size Jobs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 97:1-97:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{sun_et_al:LIPIcs.ESA.2023.97, author = {Sun, Enze and Yang, Zonghan and Zhang, Yuhao}, title = {{Improved Algorithms for Online Rent Minimization Problem Under Unit-Size Jobs}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {97:1--97:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.97}, URN = {urn:nbn:de:0030-drops-187500}, doi = {10.4230/LIPIcs.ESA.2023.97}, annote = {Keywords: Online Algorithm, Scheduling, Machine Minimization, Rent Minimization} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Xi Chen, Yuhao Li, and Mihalis Yannakakis. Reducing Tarski to Unique Tarski (In the Black-Box Model). In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 21:1-21:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{chen_et_al:LIPIcs.CCC.2023.21, author = {Chen, Xi and Li, Yuhao and Yannakakis, Mihalis}, title = {{Reducing Tarski to Unique Tarski (In the Black-Box Model)}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {21:1--21:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-282-2}, ISSN = {1868-8969}, year = {2023}, volume = {264}, editor = {Ta-Shma, Amnon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.21}, URN = {urn:nbn:de:0030-drops-182919}, doi = {10.4230/LIPIcs.CCC.2023.21}, annote = {Keywords: Tarski fixed point, Query complexity, TFNP} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Xiangyu Guo, Kelin Luo, Shi Li, and Yuhao Zhang. Minimizing the Maximum Flow Time in the Online Food Delivery Problem. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 33:1-33:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{guo_et_al:LIPIcs.ISAAC.2022.33, author = {Guo, Xiangyu and Luo, Kelin and Li, Shi and Zhang, Yuhao}, title = {{Minimizing the Maximum Flow Time in the Online Food Delivery Problem}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {33:1--33:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-258-7}, ISSN = {1868-8969}, year = {2022}, volume = {248}, editor = {Bae, Sang Won and Park, Heejin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.33}, URN = {urn:nbn:de:0030-drops-173181}, doi = {10.4230/LIPIcs.ISAAC.2022.33}, annote = {Keywords: Online algorithm, Capacitated Vehicle Routing, Flow Time Optimization} }
Feedback for Dagstuhl Publishing