Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Vladimir Braverman, Joel Manning, Zhiwei Steven Wu, and Samson Zhou. Private Data Stream Analysis for Universal Symmetric Norm Estimation. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 45:1-45:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{braverman_et_al:LIPIcs.APPROX/RANDOM.2023.45, author = {Braverman, Vladimir and Manning, Joel and Wu, Zhiwei Steven and Zhou, Samson}, title = {{Private Data Stream Analysis for Universal Symmetric Norm Estimation}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {45:1--45:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.45}, URN = {urn:nbn:de:0030-drops-188701}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.45}, annote = {Keywords: Differential privacy, norm estimation} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Jeremiah Blocki, Elena Grigorescu, Tamalika Mukherjee, and Samson Zhou. How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 59:1-59:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{blocki_et_al:LIPIcs.APPROX/RANDOM.2023.59, author = {Blocki, Jeremiah and Grigorescu, Elena and Mukherjee, Tamalika and Zhou, Samson}, title = {{How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {59:1--59:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.59}, URN = {urn:nbn:de:0030-drops-188849}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.59}, annote = {Keywords: Differential privacy, approximation algorithms} }
Published in: LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)
Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Jelani Nelson, and Samson Zhou. Differentially Private Aggregation via Imperfect Shuffling. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 17:1-17:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{ghazi_et_al:LIPIcs.ITC.2023.17, author = {Ghazi, Badih and Kumar, Ravi and Manurangsi, Pasin and Nelson, Jelani and Zhou, Samson}, title = {{Differentially Private Aggregation via Imperfect Shuffling}}, booktitle = {4th Conference on Information-Theoretic Cryptography (ITC 2023)}, pages = {17:1--17:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-271-6}, ISSN = {1868-8969}, year = {2023}, volume = {267}, editor = {Chung, Kai-Min}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.17}, URN = {urn:nbn:de:0030-drops-183453}, doi = {10.4230/LIPIcs.ITC.2023.17}, annote = {Keywords: Differential privacy, private summation, shuffle model} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Sepideh Mahabadi, David P. Woodruff, and Samson Zhou. Adaptive Sketches for Robust Regression with Importance Sampling. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 31:1-31:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{mahabadi_et_al:LIPIcs.APPROX/RANDOM.2022.31, author = {Mahabadi, Sepideh and Woodruff, David P. and Zhou, Samson}, title = {{Adaptive Sketches for Robust Regression with Importance Sampling}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {31:1--31:21}, 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.31}, URN = {urn:nbn:de:0030-drops-171531}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.31}, annote = {Keywords: Streaming algorithms, stochastic optimization, importance sampling} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Michael Kapralov, Amulya Musipatla, Jakab Tardos, David P. Woodruff, and Samson Zhou. Noisy Boolean Hidden Matching with Applications. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 91:1-91:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{kapralov_et_al:LIPIcs.ITCS.2022.91, author = {Kapralov, Michael and Musipatla, Amulya and Tardos, Jakab and Woodruff, David P. and Zhou, Samson}, title = {{Noisy Boolean Hidden Matching with Applications}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {91:1--91:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.91}, URN = {urn:nbn:de:0030-drops-156876}, doi = {10.4230/LIPIcs.ITCS.2022.91}, annote = {Keywords: Boolean Hidden Matching, Lower Bounds, Communication Complexity, Streaming Algorithms} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Rikhav Shah and Sandeep Silwal. Smoothed Analysis of the Condition Number Under Low-Rank Perturbations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 40:1-40:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{shah_et_al:LIPIcs.APPROX/RANDOM.2021.40, author = {Shah, Rikhav and Silwal, Sandeep}, title = {{Smoothed Analysis of the Condition Number Under Low-Rank Perturbations}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {40:1--40:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.40}, URN = {urn:nbn:de:0030-drops-147332}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.40}, annote = {Keywords: Smoothed analysis, condition number, low rank noise} }
Published in: LIPIcs, Volume 199, 2nd Conference on Information-Theoretic Cryptography (ITC 2021)
Jeremiah Blocki, Seunghoon Lee, and Samson Zhou. On the Security of Proofs of Sequential Work in a Post-Quantum World. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 22:1-22:27, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{blocki_et_al:LIPIcs.ITC.2021.22, author = {Blocki, Jeremiah and Lee, Seunghoon and Zhou, Samson}, title = {{On the Security of Proofs of Sequential Work in a Post-Quantum World}}, booktitle = {2nd Conference on Information-Theoretic Cryptography (ITC 2021)}, pages = {22:1--22:27}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-197-9}, ISSN = {1868-8969}, year = {2021}, volume = {199}, editor = {Tessaro, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2021.22}, URN = {urn:nbn:de:0030-drops-143415}, doi = {10.4230/LIPIcs.ITC.2021.22}, annote = {Keywords: Proof of Sequential Work, Parallel Quantum Random Oracle Model, Lower Bounds} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
David P. Woodruff and Samson Zhou. Separations for Estimating Large Frequency Moments on Data Streams. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 112:1-112:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{woodruff_et_al:LIPIcs.ICALP.2021.112, author = {Woodruff, David P. and Zhou, Samson}, title = {{Separations for Estimating Large Frequency Moments on Data Streams}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {112:1--112:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.112}, URN = {urn:nbn:de:0030-drops-141810}, doi = {10.4230/LIPIcs.ICALP.2021.112}, annote = {Keywords: streaming algorithms, frequency moments, random order, lower bounds} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Yuichi Yoshida and Samson Zhou. Sensitivity Analysis of the Maximum Matching Problem. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 58:1-58:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{yoshida_et_al:LIPIcs.ITCS.2021.58, author = {Yoshida, Yuichi and Zhou, Samson}, title = {{Sensitivity Analysis of the Maximum Matching Problem}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {58:1--58: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.58}, URN = {urn:nbn:de:0030-drops-135979}, doi = {10.4230/LIPIcs.ITCS.2021.58}, annote = {Keywords: Sensitivity analysis, maximum matching, graph algorithms} }
Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)
Jeremiah Blocki, Shubhang Kulkarni, and Samson Zhou. On Locally Decodable Codes in Resource Bounded Channels. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 16:1-16:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{blocki_et_al:LIPIcs.ITC.2020.16, author = {Blocki, Jeremiah and Kulkarni, Shubhang and Zhou, Samson}, title = {{On Locally Decodable Codes in Resource Bounded Channels}}, booktitle = {1st Conference on Information-Theoretic Cryptography (ITC 2020)}, pages = {16:1--16:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-151-1}, ISSN = {1868-8969}, year = {2020}, volume = {163}, editor = {Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.16}, URN = {urn:nbn:de:0030-drops-121216}, doi = {10.4230/LIPIcs.ITC.2020.16}, annote = {Keywords: Locally Decodable Codes, Resource Bounded Channels} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Jeremiah Blocki, Seunghoon Lee, and Samson Zhou. Approximating Cumulative Pebbling Cost Is Unique Games Hard. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 13:1-13:27, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{blocki_et_al:LIPIcs.ITCS.2020.13, author = {Blocki, Jeremiah and Lee, Seunghoon and Zhou, Samson}, title = {{Approximating Cumulative Pebbling Cost Is Unique Games Hard}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {13:1--13:27}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.13}, URN = {urn:nbn:de:0030-drops-116983}, doi = {10.4230/LIPIcs.ITCS.2020.13}, annote = {Keywords: Cumulative Pebbling Cost, Approximation Algorithm, Unique Games Conjecture, \gamma-Extreme Depth Robust Graph, Superconcentrator, Memory-Hard Function} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Mohammad Hassan Ameri, Jeremiah Blocki, and Samson Zhou. Computationally Data-Independent Memory Hard Functions. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 36:1-36:28, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{ameri_et_al:LIPIcs.ITCS.2020.36, author = {Ameri, Mohammad Hassan and Blocki, Jeremiah and Zhou, Samson}, title = {{Computationally Data-Independent Memory Hard Functions}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {36:1--36:28}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.36}, URN = {urn:nbn:de:0030-drops-117214}, doi = {10.4230/LIPIcs.ITCS.2020.36}, annote = {Keywords: Computationally Data-Independent Memory Hard Function, Cumulative Memory Complexity, Dynamic Pebbling Game} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Vladimir Braverman, Harry Lang, Enayat Ullah, and Samson Zhou. Improved Algorithms for Time Decay Streams. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 27:1-27:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{braverman_et_al:LIPIcs.APPROX-RANDOM.2019.27, author = {Braverman, Vladimir and Lang, Harry and Ullah, Enayat and Zhou, Samson}, title = {{Improved Algorithms for Time Decay Streams}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {27:1--27:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.27}, URN = {urn:nbn:de:0030-drops-112429}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.27}, annote = {Keywords: Streaming algorithms, approximation algorithms, facility location and clustering} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Grigory Yaroslavtsev and Samson Zhou. Approximate F_2-Sketching of Valuation Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 69:1-69:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{yaroslavtsev_et_al:LIPIcs.APPROX-RANDOM.2019.69, author = {Yaroslavtsev, Grigory and Zhou, Samson}, title = {{Approximate F\underline2-Sketching of Valuation Functions}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {69:1--69:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.69}, URN = {urn:nbn:de:0030-drops-112848}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.69}, annote = {Keywords: Sublinear algorithms, linear sketches, approximation algorithms} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Kaave Hosseini, Shachar Lovett, and Grigory Yaroslavtsev. Optimality of Linear Sketching Under Modular Updates. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{hosseini_et_al:LIPIcs.CCC.2019.13, author = {Hosseini, Kaave and Lovett, Shachar and Yaroslavtsev, Grigory}, title = {{Optimality of Linear Sketching Under Modular Updates}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {13:1--13:17}, 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.13}, URN = {urn:nbn:de:0030-drops-108355}, doi = {10.4230/LIPIcs.CCC.2019.13}, annote = {Keywords: communication complexity, linear sketching, streaming algorithm} }
Feedback for Dagstuhl Publishing