Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Noam Mazor and Rafael Pass. Search-To-Decision Reductions for Kolmogorov Complexity. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 34:1-34:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{mazor_et_al:LIPIcs.CCC.2024.34, author = {Mazor, Noam and Pass, Rafael}, title = {{Search-To-Decision Reductions for Kolmogorov Complexity}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {34:1--34:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.34}, URN = {urn:nbn:de:0030-drops-204308}, doi = {10.4230/LIPIcs.CCC.2024.34}, annote = {Keywords: Kolmogorov complexity, search to decision} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Yaniv Sadeh and Haim Kaplan. Caching Connections in Matchings. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 120:1-120:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{sadeh_et_al:LIPIcs.ICALP.2024.120, author = {Sadeh, Yaniv and Kaplan, Haim}, title = {{Caching Connections in Matchings}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {120:1--120: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.120}, URN = {urn:nbn:de:0030-drops-202639}, doi = {10.4230/LIPIcs.ICALP.2024.120}, annote = {Keywords: Caching, Matchings, Caching in Matchings, Edge Coloring, Online Algorithms} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Micha Sharir and Noam Solomon. On Rich Points and Incidences with Restricted Sets of Lines in 3-Space. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{sharir_et_al:LIPIcs.SoCG.2021.56, author = {Sharir, Micha and Solomon, Noam}, title = {{On Rich Points and Incidences with Restricted Sets of Lines in 3-Space}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {56:1--56:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-184-9}, ISSN = {1868-8969}, year = {2021}, volume = {189}, editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.56}, URN = {urn:nbn:de:0030-drops-138551}, doi = {10.4230/LIPIcs.SoCG.2021.56}, annote = {Keywords: Lines in space, Rich points, Polynomial partitioning, Incidences} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Noam Solomon and Shay Solomon. A Generalized Matching Reconfiguration Problem. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 57:1-57:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{solomon_et_al:LIPIcs.ITCS.2021.57, author = {Solomon, Noam and Solomon, Shay}, title = {{A Generalized Matching Reconfiguration Problem}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {57:1--57: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.57}, URN = {urn:nbn:de:0030-drops-135965}, doi = {10.4230/LIPIcs.ITCS.2021.57}, annote = {Keywords: Dynamic algorithms, graph matching, reconfiguration problem, recourse bound} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, and Srikanth Srinivasan. Schur Polynomials Do Not Have Small Formulas If the Determinant Doesn't. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 14:1-14:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{chaugule_et_al:LIPIcs.CCC.2020.14, author = {Chaugule, Prasad and Kumar, Mrinal and Limaye, Nutan and Mohapatra, Chandra Kanta and She, Adrian and Srinivasan, Srikanth}, title = {{Schur Polynomials Do Not Have Small Formulas If the Determinant Doesn't}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {14:1--14:27}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.14}, URN = {urn:nbn:de:0030-drops-125660}, doi = {10.4230/LIPIcs.CCC.2020.14}, annote = {Keywords: Schur polynomial, Jacobian, Algebraic independence, Generalized Vandermonde determinant, Taylor expansion, Formula complexity, Lower bound} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Micha Sharir and Oleg Zlydenko. Incidences Between Points and Curves with Almost Two Degrees of Freedom. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 66:1-66:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{sharir_et_al:LIPIcs.SoCG.2020.66, author = {Sharir, Micha and Zlydenko, Oleg}, title = {{Incidences Between Points and Curves with Almost Two Degrees of Freedom}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {66:1--66:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-143-6}, ISSN = {1868-8969}, year = {2020}, volume = {164}, editor = {Cabello, Sergio and Chen, Danny Z.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.66}, URN = {urn:nbn:de:0030-drops-122244}, doi = {10.4230/LIPIcs.SoCG.2020.66}, annote = {Keywords: Incidences, Polynomial partition, Degrees of freedom, Infinitely-ruled surfaces, Three dimensions} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Shachar Lovett, Noam Solomon, and Jiapeng Zhang. From DNF Compression to Sunflower Theorems via Regularity. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{lovett_et_al:LIPIcs.CCC.2019.5, author = {Lovett, Shachar and Solomon, Noam and Zhang, Jiapeng}, title = {{From DNF Compression to Sunflower Theorems via Regularity}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {5:1--5:14}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.5}, URN = {urn:nbn:de:0030-drops-108277}, doi = {10.4230/LIPIcs.CCC.2019.5}, annote = {Keywords: DNF sparsification, sunflower conjecture, regular set systems} }
Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)
Chi-Ning Chou, Mrinal Kumar, and Noam Solomon. Hardness vs Randomness for Bounded Depth Arithmetic Circuits. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{chou_et_al:LIPIcs.CCC.2018.13, author = {Chou, Chi-Ning and Kumar, Mrinal and Solomon, Noam}, title = {{Hardness vs Randomness for Bounded Depth Arithmetic Circuits}}, booktitle = {33rd Computational Complexity Conference (CCC 2018)}, pages = {13:1--13:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-069-9}, ISSN = {1868-8969}, year = {2018}, volume = {102}, editor = {Servedio, Rocco A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.13}, URN = {urn:nbn:de:0030-drops-88765}, doi = {10.4230/LIPIcs.CCC.2018.13}, annote = {Keywords: Algebraic Complexity, Polynomial Factorization Circuit Lower Bounds, Polynomial Identity Testing} }
Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)
Luis Barba, Jean Cardinal, John Iacono, Stefan Langerman, Aurélien Ooms, and Noam Solomon. Subquadratic Algorithms for Algebraic Generalizations of 3SUM. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{barba_et_al:LIPIcs.SoCG.2017.13, author = {Barba, Luis and Cardinal, Jean and Iacono, John and Langerman, Stefan and Ooms, Aur\'{e}lien and Solomon, Noam}, title = {{Subquadratic Algorithms for Algebraic Generalizations of 3SUM}}, booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)}, pages = {13:1--13:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-038-5}, ISSN = {1868-8969}, year = {2017}, volume = {77}, editor = {Aronov, Boris and Katz, Matthew J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.13}, URN = {urn:nbn:de:0030-drops-72214}, doi = {10.4230/LIPIcs.SoCG.2017.13}, annote = {Keywords: 3SUM, subquadratic algorithms, general position testing, range searching, dominance reporting, polynomial curves} }
Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)
Micha Sharir and Noam Solomon. Incidences between Points and Lines in Three Dimensions. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 553-568, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{sharir_et_al:LIPIcs.SOCG.2015.553, author = {Sharir, Micha and Solomon, Noam}, title = {{Incidences between Points and Lines in Three Dimensions}}, booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)}, pages = {553--568}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-83-5}, ISSN = {1868-8969}, year = {2015}, volume = {34}, editor = {Arge, Lars and Pach, J\'{a}nos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.553}, URN = {urn:nbn:de:0030-drops-51107}, doi = {10.4230/LIPIcs.SOCG.2015.553}, annote = {Keywords: Combinatorial Geometry, Algebraic Geometry, Incidences, The Polynomial Method} }