Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Shuangle Li, Bingkai Lin, and Yuwei Liu. Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems Under ETH. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 107:1-107:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{li_et_al:LIPIcs.ICALP.2024.107, author = {Li, Shuangle and Lin, Bingkai and Liu, Yuwei}, title = {{Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems Under ETH}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {107:1--107:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.107}, URN = {urn:nbn:de:0030-drops-202500}, doi = {10.4230/LIPIcs.ICALP.2024.107}, annote = {Keywords: Nearest Codeword Problem, Hardness of Approximations, Fine-grained Complexity, Parameterized Complexity, Minimum Distance Problem, Shortest Vector Problem} }
Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)
Dror Chawin and Ishay Haviv. Nearly Orthogonal Sets over Finite Fields. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 39:1-39:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chawin_et_al:LIPIcs.SoCG.2024.39, author = {Chawin, Dror and Haviv, Ishay}, title = {{Nearly Orthogonal Sets over Finite Fields}}, booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)}, pages = {39:1--39:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-316-4}, ISSN = {1868-8969}, year = {2024}, volume = {293}, editor = {Mulzer, Wolfgang and Phillips, Jeff M.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.39}, URN = {urn:nbn:de:0030-drops-199848}, doi = {10.4230/LIPIcs.SoCG.2024.39}, annote = {Keywords: Nearly orthogonal sets, Finite fields} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Ishay Haviv. The Chromatic Number of Kneser Hypergraphs via Consensus Division. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 60:1-60:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{haviv:LIPIcs.ITCS.2024.60, author = {Haviv, Ishay}, title = {{The Chromatic Number of Kneser Hypergraphs via Consensus Division}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {60:1--60:17}, 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.60}, URN = {urn:nbn:de:0030-drops-195883}, doi = {10.4230/LIPIcs.ITCS.2024.60}, annote = {Keywords: Kneser hypergraphs, consensus division, the complexity classes PPA-p} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Ishay Haviv. On Finding Constrained Independent Sets in Cycles. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 73:1-73:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{haviv:LIPIcs.ICALP.2023.73, author = {Haviv, Ishay}, title = {{On Finding Constrained Independent Sets in Cycles}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {73:1--73:16}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.73}, URN = {urn:nbn:de:0030-drops-181254}, doi = {10.4230/LIPIcs.ICALP.2023.73}, annote = {Keywords: Schrijver graph, Kneser graph, Stable sets, PPA-completeness} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Dror Chawin and Ishay Haviv. Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chawin_et_al:LIPIcs.STACS.2023.20, author = {Chawin, Dror and Haviv, Ishay}, title = {{Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {20:1--20:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.20}, URN = {urn:nbn:de:0030-drops-176724}, doi = {10.4230/LIPIcs.STACS.2023.20}, annote = {Keywords: hardness of approximation, graph coloring, orthogonality dimension, minrank, index coding} }
Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Ishay Haviv. A Fixed-Parameter Algorithm for the Schrijver Problem. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{haviv:LIPIcs.IPEC.2022.16, author = {Haviv, Ishay}, title = {{A Fixed-Parameter Algorithm for the Schrijver Problem}}, booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)}, pages = {16:1--16:16}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.16}, URN = {urn:nbn:de:0030-drops-173721}, doi = {10.4230/LIPIcs.IPEC.2022.16}, annote = {Keywords: Schrijver graph, Kneser graph, Fixed-parameter tractability} }
Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Ishay Haviv and Michal Parnas. On the Binary and Boolean Rank of Regular Matrices. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{haviv_et_al:LIPIcs.MFCS.2022.56, author = {Haviv, Ishay and Parnas, Michal}, title = {{On the Binary and Boolean Rank of Regular Matrices}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {56:1--56:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-256-3}, ISSN = {1868-8969}, year = {2022}, volume = {241}, editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.56}, URN = {urn:nbn:de:0030-drops-168545}, doi = {10.4230/LIPIcs.MFCS.2022.56}, annote = {Keywords: Binary rank, Boolean rank, Regular matrices, Non-deterministic communication complexity, Biclique partition number, Chromatic number} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Ishay Haviv. A Fixed-Parameter Algorithm for the Kneser Problem. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 72:1-72:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{haviv:LIPIcs.ICALP.2022.72, author = {Haviv, Ishay}, title = {{A Fixed-Parameter Algorithm for the Kneser Problem}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {72:1--72:18}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.72}, URN = {urn:nbn:de:0030-drops-164139}, doi = {10.4230/LIPIcs.ICALP.2022.72}, annote = {Keywords: Kneser graph, Fixed-parameter tractability, Agreeable Set} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Alexander Golovnev and Ishay Haviv. The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{golovnev_et_al:LIPIcs.CCC.2021.8, author = {Golovnev, Alexander and Haviv, Ishay}, title = {{The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {8:1--8:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.8}, URN = {urn:nbn:de:0030-drops-142829}, doi = {10.4230/LIPIcs.CCC.2021.8}, annote = {Keywords: Orthogonality dimension, minrank, rigidity, hardness of approximation, circuit complexity, chromatic number, Kneser graphs} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Ishay Haviv. The Complexity of Finding Fair Independent Sets in Cycles. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{haviv:LIPIcs.ITCS.2021.4, author = {Haviv, Ishay}, title = {{The Complexity of Finding Fair Independent Sets in Cycles}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {4:1--4:14}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.4}, URN = {urn:nbn:de:0030-drops-135431}, doi = {10.4230/LIPIcs.ITCS.2021.4}, annote = {Keywords: Fair independent sets in cycles, the complexity class \{PPA\}, Schrijver graphs} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Ishay Haviv. Approximating the Orthogonality Dimension of Graphs and Hypergraphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{haviv:LIPIcs.MFCS.2019.39, author = {Haviv, Ishay}, title = {{Approximating the Orthogonality Dimension of Graphs and Hypergraphs}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {39:1--39:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.39}, URN = {urn:nbn:de:0030-drops-109836}, doi = {10.4230/LIPIcs.MFCS.2019.39}, annote = {Keywords: orthogonal representations of hypergraphs, orthogonality dimension, hardness of approximation, Kneser and Schrijver graphs, semidefinite programming} }
Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Ishay Haviv. On Minrank and the Lovász Theta Function. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{haviv:LIPIcs.APPROX-RANDOM.2018.13, author = {Haviv, Ishay}, title = {{On Minrank and the Lov\'{a}sz Theta Function}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)}, pages = {13:1--13:15}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.13}, URN = {urn:nbn:de:0030-drops-94170}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.13}, annote = {Keywords: Minrank, Theta Function, Shannon capacity, Multivariate polynomials, Higher incidence matrices} }
Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Ishay Haviv. On Minrank and Forbidden Subgraphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 42:1-42:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{haviv:LIPIcs.APPROX-RANDOM.2018.42, author = {Haviv, Ishay}, title = {{On Minrank and Forbidden Subgraphs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)}, pages = {42:1--42:14}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.42}, URN = {urn:nbn:de:0030-drops-94461}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.42}, annote = {Keywords: Minrank, Forbidden subgraphs, Shannon capacity, Circuit Complexity} }
Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)
Ishay Haviv and Oded Regev. The List-Decoding Size of Fourier-Sparse Boolean Functions. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 58-71, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{haviv_et_al:LIPIcs.CCC.2015.58, author = {Haviv, Ishay and Regev, Oded}, title = {{The List-Decoding Size of Fourier-Sparse Boolean Functions}}, booktitle = {30th Conference on Computational Complexity (CCC 2015)}, pages = {58--71}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-81-1}, ISSN = {1868-8969}, year = {2015}, volume = {33}, editor = {Zuckerman, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.58}, URN = {urn:nbn:de:0030-drops-50600}, doi = {10.4230/LIPIcs.CCC.2015.58}, annote = {Keywords: Fourier-sparse functions, list-decoding, learning theory, property testing} }