Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Hamed Hatami, Pooya Hatami, William Pires, Ran Tao, and Rosie Zhao. Lower Bound Methods for Sign-Rank and Their Limitations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 22:1-22:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{hatami_et_al:LIPIcs.APPROX/RANDOM.2022.22, author = {Hatami, Hamed and Hatami, Pooya and Pires, William and Tao, Ran and Zhao, Rosie}, title = {{Lower Bound Methods for Sign-Rank and Their Limitations}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {22:1--22:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.22}, URN = {urn:nbn:de:0030-drops-171445}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.22}, annote = {Keywords: Average Margin, Communication complexity, margin complexity, monochromatic rectangle, Sign-rank, Unbounded-error communication complexity, VC-dimension} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, and Ran Tao. Further Collapses in TFNP. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 33:1-33:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{goos_et_al:LIPIcs.CCC.2022.33, author = {G\"{o}\"{o}s, Mika and Hollender, Alexandros and Jain, Siddhartha and Maystre, Gilbert and Pires, William and Robere, Robert and Tao, Ran}, title = {{Further Collapses in TFNP}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {33:1--33:15}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.33}, URN = {urn:nbn:de:0030-drops-165954}, doi = {10.4230/LIPIcs.CCC.2022.33}, annote = {Keywords: TFNP, PPAD, PLS, EOPL} }
Feedback for Dagstuhl Publishing