Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Aleksandar Nikolov and Haohua Tang. General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 85:1-85:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{nikolov_et_al:LIPIcs.ITCS.2024.85, author = {Nikolov, Aleksandar and Tang, Haohua}, title = {{General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {85:1--85:23}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.85}, URN = {urn:nbn:de:0030-drops-196133}, doi = {10.4230/LIPIcs.ITCS.2024.85}, annote = {Keywords: differential privacy, mean estimation, unbiased estimator, instance optimality} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Toniann Pitassi, Morgan Shirley, and Adi Shraibman. The Strength of Equality Oracles in Communication. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 89:1-89:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{pitassi_et_al:LIPIcs.ITCS.2023.89, author = {Pitassi, Toniann and Shirley, Morgan and Shraibman, Adi}, title = {{The Strength of Equality Oracles in Communication}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {89:1--89:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.89}, URN = {urn:nbn:de:0030-drops-175927}, doi = {10.4230/LIPIcs.ITCS.2023.89}, annote = {Keywords: Factorization norm, blocky rank, Merlin-Arthur} }
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-dev.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 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Lily Li and Aleksandar Nikolov. On the Computational Complexity of Linear Discrepancy. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 69:1-69:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{li_et_al:LIPIcs.ESA.2020.69, author = {Li, Lily and Nikolov, Aleksandar}, title = {{On the Computational Complexity of Linear Discrepancy}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {69:1--69:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.69}, URN = {urn:nbn:de:0030-drops-129352}, doi = {10.4230/LIPIcs.ESA.2020.69}, annote = {Keywords: discrepancy theory, linear discrepancy, rounding, NP-hardness} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Nima Anari and Thuy-Duong Vuong. An Extension of Plücker Relations with Applications to Subdeterminant Maximization. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 56:1-56:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{anari_et_al:LIPIcs.APPROX/RANDOM.2020.56, author = {Anari, Nima and Vuong, Thuy-Duong}, title = {{An Extension of Pl\"{u}cker Relations with Applications to Subdeterminant Maximization}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {56:1--56:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-164-1}, ISSN = {1868-8969}, year = {2020}, volume = {176}, editor = {Byrka, Jaros{\l}aw and Meka, Raghu}, 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.2020.56}, URN = {urn:nbn:de:0030-drops-126596}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.56}, annote = {Keywords: Pl\"{u}cker relations, determinant maximization, local search, exchange property, discrete concavity, discrepancy} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Andrey Boris Khesin, Aleksandar Nikolov, and Dmitry Paramonov. Preconditioning for the Geometric Transportation Problem. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{khesin_et_al:LIPIcs.SoCG.2019.15, author = {Khesin, Andrey Boris and Nikolov, Aleksandar and Paramonov, Dmitry}, title = {{Preconditioning for the Geometric Transportation Problem}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {15:1--15:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-104-7}, ISSN = {1868-8969}, year = {2019}, volume = {129}, editor = {Barequet, Gill and Wang, Yusu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.15}, URN = {urn:nbn:de:0030-drops-104190}, doi = {10.4230/LIPIcs.SoCG.2019.15}, annote = {Keywords: Earth Mover Distance, Transportation Problem, Minimum Cost Flow} }
Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)
Assimakis Kattis and Aleksandar Nikolov. Lower Bounds for Differential Privacy from Gaussian Width. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 45:1-45:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{kattis_et_al:LIPIcs.SoCG.2017.45, author = {Kattis, Assimakis and Nikolov, Aleksandar}, title = {{Lower Bounds for Differential Privacy from Gaussian Width}}, booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)}, pages = {45:1--45:16}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.45}, URN = {urn:nbn:de:0030-drops-72368}, doi = {10.4230/LIPIcs.SoCG.2017.45}, annote = {Keywords: differential privacy, convex geometry, lower bounds, sample complexity} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Daniel Dadush, Shashwat Garg, Shachar Lovett, and Aleksandar Nikolov. Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 28:1-28:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{dadush_et_al:LIPIcs.APPROX-RANDOM.2016.28, author = {Dadush, Daniel and Garg, Shashwat and Lovett, Shachar and Nikolov, Aleksandar}, title = {{Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {28:1--28:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-018-7}, ISSN = {1868-8969}, year = {2016}, volume = {60}, editor = {Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris}, 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.2016.28}, URN = {urn:nbn:de:0030-drops-66512}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.28}, annote = {Keywords: Discrepancy, Vector Balancing, Convex Geometry} }
Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)
Jirí Matoušek and Aleksandar Nikolov. Combinatorial Discrepancy for Boxes via the gamma_2 Norm. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{matousek_et_al:LIPIcs.SOCG.2015.1, author = {Matou\v{s}ek, Jir{\'\i} and Nikolov, Aleksandar}, title = {{Combinatorial Discrepancy for Boxes via the gamma\underline2 Norm}}, booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)}, pages = {1--15}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.1}, URN = {urn:nbn:de:0030-drops-51091}, doi = {10.4230/LIPIcs.SOCG.2015.1}, annote = {Keywords: discrepancy theory, range counting, factorization norms} }
Feedback for Dagstuhl Publishing