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 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Xi Chen, Yaonan Jin, Tim Randolph, and Rocco A. Servedio. Subset Sum in Time 2^{n/2} / poly(n). In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 39:1-39:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chen_et_al:LIPIcs.APPROX/RANDOM.2023.39, author = {Chen, Xi and Jin, Yaonan and Randolph, Tim and Servedio, Rocco A.}, title = {{Subset Sum in Time 2^\{n/2\} / poly(n)}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {39:1--39:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.39}, URN = {urn:nbn:de:0030-drops-188641}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.39}, annote = {Keywords: Exact algorithms, subset sum, log shaving} }
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 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 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 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, and Sandip Sinha. Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{chen_et_al:LIPIcs.ITCS.2021.20, author = {Chen, Xi and De, Anindya and Lee, Chin Ho and Servedio, Rocco A. and Sinha, Sandip}, title = {{Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {20:1--20: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.20}, URN = {urn:nbn:de:0030-drops-135595}, doi = {10.4230/LIPIcs.ITCS.2021.20}, annote = {Keywords: trace reconstruction} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Frank Ban, Xi Chen, Rocco A. Servedio, and Sandip Sinha. Efficient Average-Case Population Recovery in the Presence of Insertions and Deletions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 44:1-44:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{ban_et_al:LIPIcs.APPROX-RANDOM.2019.44, author = {Ban, Frank and Chen, Xi and Servedio, Rocco A. and Sinha, Sandip}, title = {{Efficient Average-Case Population Recovery in the Presence of Insertions and Deletions}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {44:1--44:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.44}, URN = {urn:nbn:de:0030-drops-112592}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.44}, annote = {Keywords: population recovery, deletion channel, trace reconstruction} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Nader H. Bshouty. Almost Optimal Distribution-Free Junta Testing. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 2:1-2:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bshouty:LIPIcs.CCC.2019.2, author = {Bshouty, Nader H.}, title = {{Almost Optimal Distribution-Free Junta Testing}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {2:1--2:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.2}, URN = {urn:nbn:de:0030-drops-108249}, doi = {10.4230/LIPIcs.CCC.2019.2}, annote = {Keywords: Distribution-free property testing, k-Junta} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Eshan Chattopadhyay, Anindya De, and Rocco A. Servedio. Simple and Efficient Pseudorandom Generators from Gaussian Processes. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 4:1-4:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chattopadhyay_et_al:LIPIcs.CCC.2019.4, author = {Chattopadhyay, Eshan and De, Anindya and Servedio, Rocco A.}, title = {{Simple and Efficient Pseudorandom Generators from Gaussian Processes}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {4:1--4:33}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.4}, URN = {urn:nbn:de:0030-drops-108262}, doi = {10.4230/LIPIcs.CCC.2019.4}, annote = {Keywords: Polynomial threshold functions, Gaussian processes, Johnson-Lindenstrauss, pseudorandom generators} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Amit Levi and Erik Waingarten. Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 52:1-52:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{levi_et_al:LIPIcs.ITCS.2019.52, author = {Levi, Amit and Waingarten, Erik}, title = {{Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {52:1--52: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.52}, URN = {urn:nbn:de:0030-drops-101452}, doi = {10.4230/LIPIcs.ITCS.2019.52}, annote = {Keywords: Property Testing, Juntas, Tolerant Testing, Boolean functions} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Xi Chen, Yu Cheng, and Bo Tang. Well-Supported vs. Approximate Nash Equilibria: Query Complexity of Large Games. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 57:1-57:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{chen_et_al:LIPIcs.ITCS.2017.57, author = {Chen, Xi and Cheng, Yu and Tang, Bo}, title = {{Well-Supported vs. Approximate Nash Equilibria: Query Complexity of Large Games}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {57:1--57:9}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-029-3}, ISSN = {1868-8969}, year = {2017}, volume = {67}, editor = {Papadimitriou, Christos H.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.57}, URN = {urn:nbn:de:0030-drops-81636}, doi = {10.4230/LIPIcs.ITCS.2017.57}, annote = {Keywords: Equilibrium Computation, Query Complexity, Large Games} }
Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Xi Chen, Adam Freilich, Rocco A. Servedio, and Timothy Sun. Sample-Based High-Dimensional Convexity Testing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{chen_et_al:LIPIcs.APPROX-RANDOM.2017.37, author = {Chen, Xi and Freilich, Adam and Servedio, Rocco A. and Sun, Timothy}, title = {{Sample-Based High-Dimensional Convexity Testing}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {37:1--37:20}, 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.37}, URN = {urn:nbn:de:0030-drops-75867}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.37}, annote = {Keywords: Property testing, convexity, sample-based testing} }
Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Xi Chen, Rocco A. Servedio, Li-Yang Tan, and Erik Waingarten. Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 38:1-38:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{chen_et_al:LIPIcs.APPROX-RANDOM.2017.38, author = {Chen, Xi and Servedio, Rocco A. and Tan, Li-Yang and Waingarten, Erik}, title = {{Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {38:1--38:21}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.38}, URN = {urn:nbn:de:0030-drops-75877}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.38}, annote = {Keywords: property testing, linear threshold functions, monotonicity, adaptivity} }
Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, and Jinyu Xie. Settling the Query Complexity of Non-Adaptive Junta Testing. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 26:1-26:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{chen_et_al:LIPIcs.CCC.2017.26, author = {Chen, Xi and Servedio, Rocco A. and Tan, Li-Yang and Waingarten, Erik and Xie, Jinyu}, title = {{Settling the Query Complexity of Non-Adaptive Junta Testing}}, booktitle = {32nd Computational Complexity Conference (CCC 2017)}, pages = {26:1--26:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-040-8}, ISSN = {1868-8969}, year = {2017}, volume = {79}, editor = {O'Donnell, Ryan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.26}, URN = {urn:nbn:de:0030-drops-75283}, doi = {10.4230/LIPIcs.CCC.2017.26}, annote = {Keywords: property testing, juntas, query complexity} }
Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Yijia Chen and Jörg Flum. Some Lower Bounds in Parameterized AC^0. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{chen_et_al:LIPIcs.MFCS.2016.27, author = {Chen, Yijia and Flum, J\"{o}rg}, title = {{Some Lower Bounds in Parameterized AC^0}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {27:1--27:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.27}, URN = {urn:nbn:de:0030-drops-64423}, doi = {10.4230/LIPIcs.MFCS.2016.27}, annote = {Keywords: parameterized AC^0, lower bound, clique, halting problem} }
Feedback for Dagstuhl Publishing