Published in: LIPIcs, Volume 290, 27th International Conference on Database Theory (ICDT 2024)
Sudeepa Roy, Amir Gilad, Yihao Hu, Hanze Meng, Zhengjie Miao, Kristin Stephens-Martinez, and Jun Yang. How Database Theory Helps Teach Relational Queries in Database Education (Invited Talk). In 27th International Conference on Database Theory (ICDT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 290, pp. 2:1-2:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{roy_et_al:LIPIcs.ICDT.2024.2, author = {Roy, Sudeepa and Gilad, Amir and Hu, Yihao and Meng, Hanze and Miao, Zhengjie and Stephens-Martinez, Kristin and Yang, Jun}, title = {{How Database Theory Helps Teach Relational Queries in Database Education}}, booktitle = {27th International Conference on Database Theory (ICDT 2024)}, pages = {2:1--2:9}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-312-6}, ISSN = {1868-8969}, year = {2024}, volume = {290}, editor = {Cormode, Graham and Shekelyan, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.2}, URN = {urn:nbn:de:0030-drops-197841}, doi = {10.4230/LIPIcs.ICDT.2024.2}, annote = {Keywords: Query Debugging, SQL, Relational Algebra, Relational Calculus, Database Education, Boolean Provenance} }
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)
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-dev.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)
Dongrun Cai, Xue Chen, and Pan Peng. Effective Resistances in Non-Expander Graphs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 29:1-29:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{cai_et_al:LIPIcs.ESA.2023.29, author = {Cai, Dongrun and Chen, Xue and Peng, Pan}, title = {{Effective Resistances in Non-Expander Graphs}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {29:1--29:18}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.29}, URN = {urn:nbn:de:0030-drops-186823}, doi = {10.4230/LIPIcs.ESA.2023.29}, annote = {Keywords: Sublinear Time Algorithm, Effective Resistance, Leverage Scores, Matrix Perturbation} }
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-dev.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-dev.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 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Rasmus Kyng. An Almost-Linear Time Algorithm for Maximum Flow and More (Invited Talk). In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{kyng:LIPIcs.ICALP.2023.2, author = {Kyng, Rasmus}, title = {{An Almost-Linear Time Algorithm for Maximum Flow and More}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {2:1--2:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.2}, URN = {urn:nbn:de:0030-drops-180543}, doi = {10.4230/LIPIcs.ICALP.2023.2}, annote = {Keywords: Maximum flow, Minimum cost flow, Data structures, Interior point methods, Convex optimization} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Lijie Chen, Ryan Williams, and Tianqi Yang. Black-Box Constructive Proofs Are Unavoidable. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 35:1-35:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chen_et_al:LIPIcs.ITCS.2023.35, author = {Chen, Lijie and Williams, Ryan and Yang, Tianqi}, title = {{Black-Box Constructive Proofs Are Unavoidable}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {35:1--35:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.35}, URN = {urn:nbn:de:0030-drops-175380}, doi = {10.4230/LIPIcs.ITCS.2023.35}, annote = {Keywords: Circuit lower bounds, natural proofs, probabilistic checkable proofs} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Jason Gaitonde, Yingkai Li, Bar Light, Brendan Lucier, and Aleksandrs Slivkins. Budget Pacing in Repeated Auctions: Regret and Efficiency Without Convergence. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, p. 52:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{gaitonde_et_al:LIPIcs.ITCS.2023.52, author = {Gaitonde, Jason and Li, Yingkai and Light, Bar and Lucier, Brendan and Slivkins, Aleksandrs}, title = {{Budget Pacing in Repeated Auctions: Regret and Efficiency Without Convergence}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {52:1--52:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.52}, URN = {urn:nbn:de:0030-drops-175557}, doi = {10.4230/LIPIcs.ITCS.2023.52}, annote = {Keywords: repeated auctions with budgets, pacing, learning in auctions} }
Published in: OASIcs, Volume 106, 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)
Zuguang Gao, John R. Birge, Richard Li-Yang Chen, and Maurice Cheung. Greedy Algorithms for the Freight Consolidation Problem. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{gao_et_al:OASIcs.ATMOS.2022.4, author = {Gao, Zuguang and Birge, John R. and Chen, Richard Li-Yang and Cheung, Maurice}, title = {{Greedy Algorithms for the Freight Consolidation Problem}}, booktitle = {22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)}, pages = {4:1--4:19}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-259-4}, ISSN = {2190-6807}, year = {2022}, volume = {106}, editor = {D'Emidio, Mattia and Lindner, Niels}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2022.4}, URN = {urn:nbn:de:0030-drops-171086}, doi = {10.4230/OASIcs.ATMOS.2022.4}, annote = {Keywords: Freight consolidation, heuristics, greedy algorithm} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Victor Lecomte, Prasanna Ramakrishnan, and Li-Yang Tan. The Composition Complexity of Majority. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 19:1-19:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{lecomte_et_al:LIPIcs.CCC.2022.19, author = {Lecomte, Victor and Ramakrishnan, Prasanna and Tan, Li-Yang}, title = {{The Composition Complexity of Majority}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {19:1--19:26}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.19}, URN = {urn:nbn:de:0030-drops-165818}, doi = {10.4230/LIPIcs.CCC.2022.19}, annote = {Keywords: computational complexity, circuit lower bounds} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Lijie Chen, Jiatu Li, and Tianqi Yang. Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 23:1-23:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{chen_et_al:LIPIcs.CCC.2022.23, author = {Chen, Lijie and Li, Jiatu and Yang, Tianqi}, title = {{Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {23:1--23:37}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.23}, URN = {urn:nbn:de:0030-drops-165852}, doi = {10.4230/LIPIcs.CCC.2022.23}, annote = {Keywords: Almost universal hash functions, hardness magnification, pseudorandom functions} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Xin Lyu. Improved Pseudorandom Generators for AC⁰ Circuits. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 34:1-34:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{lyu:LIPIcs.CCC.2022.34, author = {Lyu, Xin}, title = {{Improved Pseudorandom Generators for AC⁰ Circuits}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {34:1--34:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.34}, URN = {urn:nbn:de:0030-drops-165963}, doi = {10.4230/LIPIcs.CCC.2022.34}, annote = {Keywords: pseudorandom generators, derandomization, switching Lemmas, AC⁰} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Xue Chen, Kuan Cheng, Xin Li, and Minghui Ouyang. Improved Decoding of Expander Codes. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 43:1-43:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{chen_et_al:LIPIcs.ITCS.2022.43, author = {Chen, Xue and Cheng, Kuan and Li, Xin and Ouyang, Minghui}, title = {{Improved Decoding of Expander Codes}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {43:1--43:3}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.43}, URN = {urn:nbn:de:0030-drops-156394}, doi = {10.4230/LIPIcs.ITCS.2022.43}, annote = {Keywords: Expander Code, Decoding} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Jianer Chen, Qin Huang, Iyad Kanj, Qian Li, and Ge Xia. Streaming Algorithms for Graph k-Matching with Optimal or Near-Optimal Update Time. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 48:1-48:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{chen_et_al:LIPIcs.ISAAC.2021.48, author = {Chen, Jianer and Huang, Qin and Kanj, Iyad and Li, Qian and Xia, Ge}, title = {{Streaming Algorithms for Graph k-Matching with Optimal or Near-Optimal Update Time}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {48:1--48:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-214-3}, ISSN = {1868-8969}, year = {2021}, volume = {212}, editor = {Ahn, Hee-Kap and Sadakane, Kunihiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.48}, URN = {urn:nbn:de:0030-drops-154816}, doi = {10.4230/LIPIcs.ISAAC.2021.48}, annote = {Keywords: streaming algorithms, matching, parameterized algorithms, lower bounds} }
Feedback for Dagstuhl Publishing