LIPIcs, Volume 149
ISAAC 2019, December 8-11, 2019, Shanghai University of Finance and Economics, Shanghai, China
Editors: Pinyan Lu and Guochuan Zhang
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Yumou Fei, Leslie Ann Goldberg, and Pinyan Lu. Two-State Spin Systems with Negative Interactions. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 45:1-45:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{fei_et_al:LIPIcs.ITCS.2024.45, author = {Fei, Yumou and Goldberg, Leslie Ann and Lu, Pinyan}, title = {{Two-State Spin Systems with Negative Interactions}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {45:1--45:13}, 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.45}, URN = {urn:nbn:de:0030-drops-195739}, doi = {10.4230/LIPIcs.ITCS.2024.45}, annote = {Keywords: Approximate Counting, Spin Systems, #P-Hardness, Randomized Algorithms} }
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 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Yaonan Jin, Pinyan Lu, and Tao Xiao. Learning Reserve Prices in Second-Price Auctions. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 75:1-75:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{jin_et_al:LIPIcs.ITCS.2023.75, author = {Jin, Yaonan and Lu, Pinyan and Xiao, Tao}, title = {{Learning Reserve Prices in Second-Price Auctions}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {75:1--75: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.75}, URN = {urn:nbn:de:0030-drops-175780}, doi = {10.4230/LIPIcs.ITCS.2023.75}, annote = {Keywords: Revenue Maximization, Sample Complexity, Anonymous Reserve} }
Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
YuMing Du, QingYun Zhang, JunZhou Xu, ShunGen Zhang, Chao Liao, ZhiHuai Chen, ZhiBo Sun, ZhouXing Su, JunWen Ding, Chen Wu, PinYan Lu, and ZhiPeng Lv. PACE Solver Description: Hust-Solver - A Heuristic Algorithm of Directed Feedback Vertex Set Problem. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 29:1-29:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{du_et_al:LIPIcs.IPEC.2022.29, author = {Du, YuMing and Zhang, QingYun and Xu, JunZhou and Zhang, ShunGen and Liao, Chao and Chen, ZhiHuai and Sun, ZhiBo and Su, ZhouXing and Ding, JunWen and Wu, Chen and Lu, PinYan and Lv, ZhiPeng}, title = {{PACE Solver Description: Hust-Solver - A Heuristic Algorithm of Directed Feedback Vertex Set Problem}}, booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)}, pages = {29:1--29:3}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-260-0}, ISSN = {1868-8969}, year = {2022}, volume = {249}, editor = {Dell, Holger and Nederlof, Jesper}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.29}, URN = {urn:nbn:de:0030-drops-173855}, doi = {10.4230/LIPIcs.IPEC.2022.29}, annote = {Keywords: directed feedback vertex set, local search, simulated annealing, set covering} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Jin-Yi Cai, Tianyu Liu, Pinyan Lu, and Jing Yu. Approximability of the Eight-Vertex Model. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{cai_et_al:LIPIcs.CCC.2020.4, author = {Cai, Jin-Yi and Liu, Tianyu and Lu, Pinyan and Yu, Jing}, title = {{Approximability of the Eight-Vertex Model}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {4:1--4:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.4}, URN = {urn:nbn:de:0030-drops-125564}, doi = {10.4230/LIPIcs.CCC.2020.4}, annote = {Keywords: Approximate complexity, the eight-vertex model, Markov chain Monte Carlo} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@Proceedings{lu_et_al:LIPIcs.ISAAC.2019, title = {{LIPIcs, Volume 149, ISAAC'19, Complete Volume}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019}, URN = {urn:nbn:de:0030-drops-116417}, doi = {10.4230/LIPIcs.ISAAC.2019}, annote = {Keywords: Theory of computation; Models of computation; Computational complexity and cryptography; Randomness, geometry and discrete structures; Theory and algorithms for application domains; Design and analysis of algorithms} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{lu_et_al:LIPIcs.ISAAC.2019.0, author = {Lu, Pinyan and Zhang, Guochuan}, title = {{Front Matter, Table of Contents, Preface, Symposium Organization}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {0:i--0:xvi}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.0}, URN = {urn:nbn:de:0030-drops-114967}, doi = {10.4230/LIPIcs.ISAAC.2019.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Symposium Organization} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Yixin Cao, Zhifeng Wang, Guozhen Rong, and Jianxin Wang. Graph Searches and Their End Vertices. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{cao_et_al:LIPIcs.ISAAC.2019.1, author = {Cao, Yixin and Wang, Zhifeng and Rong, Guozhen and Wang, Jianxin}, title = {{Graph Searches and Their End Vertices}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {1:1--1:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.1}, URN = {urn:nbn:de:0030-drops-114973}, doi = {10.4230/LIPIcs.ISAAC.2019.1}, annote = {Keywords: maximum cardinality search, (lexicographic) breadth-first search, (lexicographic) depth-first search, chordal graph, weighted clique graph, end vertex} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Nader H. Bshouty. Lower Bound for Non-Adaptive Estimation of the Number of Defective Items. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 2:1-2:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bshouty:LIPIcs.ISAAC.2019.2, author = {Bshouty, Nader H.}, title = {{Lower Bound for Non-Adaptive Estimation of the Number of Defective Items}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {2:1--2:9}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.2}, URN = {urn:nbn:de:0030-drops-114983}, doi = {10.4230/LIPIcs.ISAAC.2019.2}, annote = {Keywords: Group Testing, Estimation, Defective Items} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Kazuya Haraguchi and Hiroshi Nagamochi. A Polynomial-Delay Algorithm for Enumerating Connectors Under Various Connectivity Conditions. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{haraguchi_et_al:LIPIcs.ISAAC.2019.3, author = {Haraguchi, Kazuya and Nagamochi, Hiroshi}, title = {{A Polynomial-Delay Algorithm for Enumerating Connectors Under Various Connectivity Conditions}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {3:1--3:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.3}, URN = {urn:nbn:de:0030-drops-114990}, doi = {10.4230/LIPIcs.ISAAC.2019.3}, annote = {Keywords: Graph with itemsets, Enumeration, Polynomial-delay algorithms, Connectors} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Philip Bille, Paweł Gawrychowski, Inge Li Gørtz, Gad M. Landau, and Oren Weimann. Top Tree Compression of Tries. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bille_et_al:LIPIcs.ISAAC.2019.4, author = {Bille, Philip and Gawrychowski, Pawe{\l} and G{\o}rtz, Inge Li and Landau, Gad M. and Weimann, Oren}, title = {{Top Tree Compression of Tries}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {4:1--4:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.4}, URN = {urn:nbn:de:0030-drops-115000}, doi = {10.4230/LIPIcs.ISAAC.2019.4}, annote = {Keywords: pattern matching, tree compression, top trees, pointer machine} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Ahad N. Zehmakan. Two Phase Transitions in Two-Way Bootstrap Percolation. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{zehmakan:LIPIcs.ISAAC.2019.5, author = {Zehmakan, Ahad N.}, title = {{Two Phase Transitions in Two-Way Bootstrap Percolation}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {5:1--5:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.5}, URN = {urn:nbn:de:0030-drops-115017}, doi = {10.4230/LIPIcs.ISAAC.2019.5}, annote = {Keywords: bootstrap percolation, cellular automata, phase transition, d-dimensional torus, r-threshold model, biased majority} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Moses Ganardi, Danny Hucke, Markus Lohrey, and Tatiana Starikovskaya. Sliding Window Property Testing for Regular Languages. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{ganardi_et_al:LIPIcs.ISAAC.2019.6, author = {Ganardi, Moses and Hucke, Danny and Lohrey, Markus and Starikovskaya, Tatiana}, title = {{Sliding Window Property Testing for Regular Languages}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {6:1--6:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.6}, URN = {urn:nbn:de:0030-drops-115023}, doi = {10.4230/LIPIcs.ISAAC.2019.6}, annote = {Keywords: Streaming algorithms, approximation algorithms, regular languages} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Isaac Goldstein, Moshe Lewenstein, and Ely Porat. On the Hardness of Set Disjointness and Set Intersection with Bounded Universe. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 7:1-7:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{goldstein_et_al:LIPIcs.ISAAC.2019.7, author = {Goldstein, Isaac and Lewenstein, Moshe and Porat, Ely}, title = {{On the Hardness of Set Disjointness and Set Intersection with Bounded Universe}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {7:1--7:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.7}, URN = {urn:nbn:de:0030-drops-115036}, doi = {10.4230/LIPIcs.ISAAC.2019.7}, annote = {Keywords: set disjointness, set intersection, 3SUM, space-time tradeoff, conditional lower bounds} }
Feedback for Dagstuhl Publishing