Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Chi-Ning Chou, Peter J. Love, Juspreet Singh Sandhu, and Jonathan Shi. Limitations of Local Quantum Algorithms on Random MAX-k-XOR and Beyond. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 41:1-41:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{chou_et_al:LIPIcs.ICALP.2022.41, author = {Chou, Chi-Ning and Love, Peter J. and Sandhu, Juspreet Singh and Shi, Jonathan}, title = {{Limitations of Local Quantum Algorithms on Random MAX-k-XOR and Beyond}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {41:1--41:20}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.41}, URN = {urn:nbn:de:0030-drops-163822}, doi = {10.4230/LIPIcs.ICALP.2022.41}, annote = {Keywords: Quantum Algorithms, Spin Glasses, Hardness of Approximation, Local Algorithms, Concentration Inequalities, Overlap Gap Property} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, and Ruizhe Zhang. Quantum Meets the Minimum Circuit Size Problem. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 47:1-47:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{chia_et_al:LIPIcs.ITCS.2022.47, author = {Chia, Nai-Hui and Chou, Chi-Ning and Zhang, Jiayu and Zhang, Ruizhe}, title = {{Quantum Meets the Minimum Circuit Size Problem}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {47:1--47:16}, 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.47}, URN = {urn:nbn:de:0030-drops-156433}, doi = {10.4230/LIPIcs.ITCS.2022.47}, annote = {Keywords: Quantum Computation, Quantum Complexity, Minimum Circuit Size Problem} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Chi-Ning Chou, Zhixian Lei, and Preetum Nakkiran. Tracking the l_2 Norm with Constant Update Time. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chou_et_al:LIPIcs.APPROX-RANDOM.2019.2, author = {Chou, Chi-Ning and Lei, Zhixian and Nakkiran, Preetum}, title = {{Tracking the l\underline2 Norm with Constant Update Time}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {2:1--2:15}, 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.2}, URN = {urn:nbn:de:0030-drops-112175}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.2}, annote = {Keywords: Streaming algorithms, Sketching algorithms, Tracking, CountSketch} }
Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang. Online Makespan Minimization: The Power of Restart. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{huang_et_al:LIPIcs.APPROX-RANDOM.2018.14, author = {Huang, Zhiyi and Kang, Ning and Tang, Zhihao Gavin and Wu, Xiaowei and Zhang, Yuhao}, title = {{Online Makespan Minimization: The Power of Restart}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)}, pages = {14:1--14: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.14}, URN = {urn:nbn:de:0030-drops-94182}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.14}, annote = {Keywords: Online Scheduling, Makespan Minimization, Identical Machines} }
Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Ning Chen. On Computing Pareto Stable Assignments. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 384-395, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
@InProceedings{chen:LIPIcs.STACS.2012.384, author = {Chen, Ning}, title = {{On Computing Pareto Stable Assignments}}, booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)}, pages = {384--395}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-35-4}, ISSN = {1868-8969}, year = {2012}, volume = {14}, editor = {D\"{u}rr, Christoph and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.384}, URN = {urn:nbn:de:0030-drops-34042}, doi = {10.4230/LIPIcs.STACS.2012.384}, annote = {Keywords: Algorithm, stable matching, Pareto efficiency} }
Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)
Arnab Bhattacharyya, Victor Chen, Madhu Sudan, and Ning Xie. Testing Linear-Invariant Non-Linear Properties. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 135-146, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{bhattacharyya_et_al:LIPIcs.STACS.2009.1823, author = {Bhattacharyya, Arnab and Chen, Victor and Sudan, Madhu and Xie, Ning}, title = {{Testing Linear-Invariant Non-Linear Properties}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {135--146}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1823}, URN = {urn:nbn:de:0030-drops-18235}, doi = {10.4230/LIPIcs.STACS.2009.1823}, annote = {Keywords: } }
Feedback for Dagstuhl Publishing