Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Deepanshu Kush and Shubhangi Saraf. Near-Optimal Set-Multilinear Formula Lower Bounds. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 15:1-15:33, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{kush_et_al:LIPIcs.CCC.2023.15, author = {Kush, Deepanshu and Saraf, Shubhangi}, title = {{Near-Optimal Set-Multilinear Formula Lower Bounds}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {15:1--15:33}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.15}, URN = {urn:nbn:de:0030-drops-182855}, doi = {10.4230/LIPIcs.CCC.2023.15}, annote = {Keywords: Algebraic Complexity, Set-multilinear, Formula Lower Bounds} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Deepanshu Kush and Shubhangi Saraf. Improved Low-Depth Set-Multilinear Circuit Lower Bounds. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 38:1-38:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{kush_et_al:LIPIcs.CCC.2022.38, author = {Kush, Deepanshu and Saraf, Shubhangi}, title = {{Improved Low-Depth Set-Multilinear Circuit Lower Bounds}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {38:1--38:16}, 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.38}, URN = {urn:nbn:de:0030-drops-166003}, doi = {10.4230/LIPIcs.CCC.2022.38}, annote = {Keywords: algebraic circuit complexity, complexity measure, set-multilinear formulas} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Deepanshu Kush, Aleksandar Nikolov, and Haohua Tang. Near Neighbor Search via Efficient Average Distortion Embeddings. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 50:1-50:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{kush_et_al:LIPIcs.SoCG.2021.50, author = {Kush, Deepanshu and Nikolov, Aleksandar and Tang, Haohua}, title = {{Near Neighbor Search via Efficient Average Distortion Embeddings}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {50:1--50: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.50}, URN = {urn:nbn:de:0030-drops-138490}, doi = {10.4230/LIPIcs.SoCG.2021.50}, annote = {Keywords: Nearest neighbor search, metric space embeddings, average distortion embeddings, locality-sensitive hashing} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, and Srikanth Srinivasan. A #SAT Algorithm for Small Constant-Depth Circuits with PTF Gates. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 8:1-8:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{bajpai_et_al:LIPIcs.ITCS.2019.8, author = {Bajpai, Swapnam and Krishan, Vaibhav and Kush, Deepanshu and Limaye, Nutan and Srinivasan, Srikanth}, title = {{A #SAT Algorithm for Small Constant-Depth Circuits with PTF Gates}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {8:1--8: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.8}, URN = {urn:nbn:de:0030-drops-101010}, doi = {10.4230/LIPIcs.ITCS.2019.8}, annote = {Keywords: SAT, Polynomial Threshold Functions, Constant-depth Boolean Circuits, Linear Decision Trees, Zero-error randomized algorithms} }
Feedback for Dagstuhl Publishing