Fetching the paper…
Reading the bibliography…
We study the space complexity of the two related fields of differential privacy and adaptive data analysis.
Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: Denning, D.E., Pyle, R., Ganesan, R., Sandhu, R.S., Ashby, V. (eds.) CCS 1993. pp. 62–73. ACM (1993)
1993
Earlier work this paper cites.
Boneh, D., Shaw, J.: Collusion-secure fingerprinting for digital data. IEEE Transactions on Information Theory 44(5), 1897–1905 (1998)
1998
Earlier work this paper cites.
Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A Pseudorandom Generator from any One-way Function. SIAM J. Comput. 28(4), 1364–1396 (1999)
1999
Earlier work this paper cites.
Raz, R., McKenzie, P.: Separation of the monotone NC hierarchy. Comb. 19(3), 403–435 (1999)
1999
Earlier work this paper cites.
Canetti, R., Dodis, Y., Halevi, S., Kushilevitz, E., Sahai, A.: Exposure-resilient functions and all-or-nothing transforms. In: Preneel, B. (ed.) EUROCRYPT 2000. Lecture Notes in Computer Science, vol. 1807, pp. 453–469. Springer (2000)
2000
Earlier work this paper cites.
Goldreich, O.: The Foundations of Cryptography - Volume 1: Basic Techniques. Cambridge University Press (2001)
2001
Earlier work this paper cites.
Woodruff, D.P.: Optimal space lower bounds for all frequency moments. In: Munro, J.I. (ed.) Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January 11-14, 2004. pp. 167–175. SIAM (2004)
2004
Earlier work this paper cites.
Dziembowski, S.: Intrusion-resilience via the bounded-storage model. In: Halevi, S., Rabin, T. (eds.) TCC 2006. vol. 3876, pp. 207–224. Springer (2006)
2006
Earlier work this paper cites.
Unruh, D.: Random oracles and auxiliary input. In: Menezes, A. (ed.) CRYPTO 2007. Lecture Notes in Computer Science, vol. 4622, pp. 205–223. Springer (2007)
2007
Earlier work this paper cites.
Beimel, A., Nissim, K., Omri, E.: Distributed private data analysis: Simultaneously solving how and what. In: CRYPTO. Lecture Notes in Computer Science, vol. 5157, pp. 451–468. Springer (2008)
2008
Earlier work this paper cites.
Dziembowski, S., Pietrzak, K.: Leakage-resilient cryptography. In: FOCS 2008. pp. 293–302. IEEE Computer Society (2008)
2008
Earlier work this paper cites.
Tardos, G.: Optimal probabilistic fingerprint codes. Journal of the ACM (JACM) 55(2), 1–24 (2008)
2008
Earlier work this paper cites.
Dwork, C., Naor, M., Reingold, O., Rothblum, G.N., Vadhan, S.: On the complexity of differentially private data release: efficient algorithms and hardness results. In: Proceedings of the forty-first annual ACM symposium on Theory of computing. pp. 381–390 (2009)
2009
Earlier work this paper cites.
Mironov, I., Pandey, O., Reingold, O., Vadhan, S.P.: Computational differential privacy. In: CRYPTO. Lecture Notes in Computer Science, vol. 5677, pp. 126–142. Springer (2009)
2009
Earlier work this paper cites.
Pietrzak, K.: A leakage-resilient mode of operation. In: Joux, A. (ed.) EUROCRYPT 2009. Lecture Notes in Computer Science, vol. 5479, pp. 462–482. Springer (2009)
2009
Earlier work this paper cites.
Chien, S., Ligett, K., McGregor, A.: Space-efficient estimation of robust statistics and distribution testing. In: Innovations in Computer Science - ICS, Proceedings. pp. 251–265 (2010)
2010
Earlier work this paper cites.
Dwork, C., Naor, M., Pitassi, T., Rothblum, G.N., Yekhanin, S.: Pan-private streaming algorithms. In: ICS. pp. 66–80. Tsinghua University Press (2010)
2010
Earlier work this paper cites.
Dwork, C., Rothblum, G.N., Vadhan, S.P.: Boosting and differential privacy. In: FOCS. pp. 51–60. IEEE Computer Society (2010)
2010
Earlier work this paper cites.
Standaert, F., Pereira, O., Yu, Y., Quisquater, J., Yung, M., Oswald, E.: Leakage resilient cryptography in practice. In: Sadeghi, A., Naccache, D. (eds.) Towards Hardware-Intrinsic Security - Foundations and Practice, pp. 99–134. Information Security and Cryptography, Springer (2010)
2010
Earlier work this paper cites.
Mir, D., Muthukrishnan, S., Nikolov, A., Wright, R.N.: Pan-private algorithms via statistics on sketches. In: Proceedings of the thirtieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. pp. 37–48 (2011)
2011
Earlier work this paper cites.
Blocki, J., Blum, A., Datta, A., Sheffet, O.: The johnson-lindenstrauss transform itself preserves differential privacy. In: FOCS. pp. 410–419. IEEE Computer Society (2012)
2012
Earlier work this paper cites.
Chan, T.H.H., Li, M., Shi, E., Xu, W.: Differentially private continual monitoring of heavy hitters from distributed streams. In: International Symposium on Privacy Enhancing Technologies Symposium. pp. 140–159. Springer (2012)
2012
Earlier work this paper cites.
Bolot, J., Fawaz, N., Muthukrishnan, S., Nikolov, A., Taft, N.: Private decayed predicate sums on streams. In: ICDT. pp. 284–295. ACM (2013)
2013
Earlier work this paper cites.
Ullman, J.: Answering n 2 + o ( 1 ) n^{2+o(1)} counting queries with differential privacy is hard. In: Proceedings of the forty-fifth annual ACM symposium on Theory of computing. pp. 361–370 (2013)
2013
Earlier work this paper cites.
Bun, M., Ullman, J.R., Vadhan, S.P.: Fingerprinting codes and the price of approximate differential privacy. In: STOC. pp. 1–10. ACM (2014)
2014
Earlier work this paper cites.
Göös, M., Pitassi, T.: Communication lower bounds via critical block sensitivity. In: Proceedings of the forty-sixth annual ACM symposium on Theory of computing. pp. 847–856 (2014)
2014
Earlier work this paper cites.
Hardt, M., Ullman, J.R.: Preventing false discovery in interactive data analysis is hard. In: FOCS. pp. 454–463. IEEE Computer Society (2014)
2014
Earlier work this paper cites.
Bun, M., Nissim, K., Stemmer, U., Vadhan, S.P.: Differentially private release and learning of threshold functions. In: FOCS. pp. 634–649. IEEE Computer Society (2015)
2015
Earlier work this paper cites.
Dwork, C., Feldman, V., Hardt, M., Pitassi, T., Reingold, O., Roth, A.: Generalization in adaptive data analysis and holdout reuse. In: NIPS. pp. 2350–2358 (2015)
2015
Earlier work this paper cites.
Dwork, C., Feldman, V., Hardt, M., Pitassi, T., Reingold, O., Roth, A.L.: Preserving statistical validity in adaptive data analysis. In: Proceedings of the forty-seventh annual ACM symposium on Theory of computing. pp. 117–126 (2015)
2015
Earlier work this paper cites.
Göös, M., Lovett, S., Meka, R., Watson, T., Zuckerman, D.: Rectangles Are Nonnegative Juntas. In: Servedio, R.A., Rubinfeld, R. (eds.) STOC 2015. pp. 257–266. ACM (2015)
2015
Cited alongside, same era.
Göös, M., Pitassi, T., Watson, T.: Deterministic communication vs. partition number. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. pp. 1077–1088. IEEE (2015)
2015
Cited alongside, same era.
Steinke, T., Ullman, J.R.: Interactive fingerprinting codes and the hardness of preventing false discovery. In: COLT. JMLR Workshop and Conference Proceedings, vol. 40, pp. 1588–1628. JMLR.org (2015)
2015
Cited alongside, same era.
Bassily, R., Freund, Y.: Typical stability. arXiv preprint arXiv:1604.03336 (2016)
2016
Cited alongside, same era.
Chattopadhyay, A., Filmus, Y., Koroth, S., Meir, O., Pitassi, T.: Query-to-communication lifting for bpp using inner product. In: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2019)
2019
Later among the works it cites.
Chattopadhyay, A., Kouckỳ, M., Loff, B., Mukhopadhyay, S.: Simulation theorems via pseudo-random properties. computational complexity 28(4), 617–659 (2019)
2019
Later among the works it cites.
Diakonikolas, I., Gouleakis, T., Kane, D.M., Rao, S.: Communication and memory efficient testing of discrete distributions. In: Beygelzimer, A., Hsu, D. (eds.) Conference on Learning Theory, COLT. pp. 1070–1106 (2019)
2019
Later among the works it cites.
Kalai, Y.T., Reyzin, L.: A survey of leakage-resilient cryptography. In: Goldreich, O. (ed.) Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, pp. 727–794. ACM (2019)
2019
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cummings, R., Ligett, K., Nissim, K., Roth, A., Wu, Z.S.: Adaptive learning with robust generalization guarantees. In: Conference on Learning Theory. pp. 772–814. PMLR (2016)
2016
Cited alongside, same era.
De Rezende, S.F., Nordström, J., Vinyals, M.: How limited interaction hinders real communication (and what it means for proof and circuit complexity). In: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). pp. 295–304. IEEE (2016)
2016
Cited alongside, same era.
Dwork, C., McSherry, F., Nissim, K., Smith, A.: Calibrating noise to sensitivity in private data analysis. Journal of Privacy and Confidentiality 7(3), 17–51 (2016)
2016
Cited alongside, same era.
Hazay, C., López-Alt, A., Wee, H., Wichs, D.: Leakage-resilient cryptography from minimal assumptions. J. Cryptol. 29(3), 514–551 (2016)
2016
Cited alongside, same era.
Rogers, R., Roth, A., Smith, A., Thakkar, O.: Max-information, differential privacy, and post-selection hypothesis testing. In: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). pp. 487–494. IEEE (2016)
2016
Cited alongside, same era.
Steinhardt, J., Valiant, G., Wager, S.: Memory, communication, and statistical queries. In: Proceedings of the 29th Conference on Learning Theory, COLT. pp. 1490–1516 (2016)
2016
Cited alongside, same era.
Feldman, V., Steinke, T.: Generalization for adaptively-chosen estimators via stable median. In: Conference on Learning Theory. pp. 728–757. PMLR (2017)
2017
Cited alongside, same era.
Kol, G., Raz, R., Tal, A.: Time-space hardness of learning sparse parities. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC. pp. 1067–1080 (2017)
2017
Cited alongside, same era.
Loff, B., Mukhopadhyay, S.: Lifting theorems for equality. In: 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2019)
2019
Later among the works it cites.
Raz, R.: Fast learning requires good memory: A time-space lower bound for parity learning. J. ACM 66(1), 3:1–3:18 (2019)
2019
Later among the works it cites.
Shenfeld, M., Ligett, K.: A necessary and sufficient stability notion for adaptive generalization. In: NeurIPS. pp. 11481–11490 (2019)
2019
Later among the works it cites.
Upadhyay, J.: Sublinear space private algorithms under the sliding window model. In: ICML. Proceedings of Machine Learning Research, vol. 97, pp. 6363–6372. PMLR (2019)
2019
Later among the works it cites.
Bassily, R., Nissim, K., Stemmer, U., Thakurta, A.: Practical locally private heavy hitters. J. Mach. Learn. Res. 21, 16:1–16:42 (2020)
2020
Later among the works it cites.
Dai, W., Tessaro, S., Zhang, X.: Super-linear time-memory trade-offs for symmetric encryption. In: TCC 2020. pp. 335–365 (2020)
2020
Later among the works it cites.
Dodis, Y., Farshim, P., Mazaheri, S., Tessaro, S.: Towards defeating backdoored random oracles: Indifferentiability with bounded adaptivity. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. Lecture Notes in Computer Science, vol. 12552, pp. 241–273. Springer (2020)
2020
Later among the works it cites.
Feldman, V.: Does learning require memorization? a short tale about a long tail. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. pp. 954–959 (2020)
2020
Later among the works it cites.
Fish, B., Reyzin, L., Rubinstein, B.I.P.: Sampling without compromising accuracy in adaptive data analysis. In: ALT. Proceedings of Machine Learning Research, vol. 117, pp. 297–318. PMLR (2020)
2020
Later among the works it cites.
Göös, M., Pitassi, T., Watson, T.: Query-to-communication lifting for bpp. SIAM Journal on Computing 49(4), FOCS17–441 (2020)
2020
Later among the works it cites.
Smith, A.D., Song, S., Thakurta, A.: The flajolet-martin sketch itself preserves differential privacy: Private counting with minimal space. In: NeurIPS (2020)
2020
Later among the works it cites.
Bassily, R., Nissim, K., Smith, A.D., Steinke, T., Stemmer, U., Ullman, J.R.: Algorithmic stability for adaptive data analysis. SIAM J. Comput. 50(3) (2021)
2021
Later among the works it cites.
Brown, G., Bun, M., Feldman, V., Smith, A., Talwar, K.: When is memorization of irrelevant training data necessary for high-accuracy learning? In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. pp. 123–132 (2021)
2021
Later among the works it cites.
Bu, Z., Gopi, S., Kulkarni, J., Lee, Y.T., Shen, H., Tantipongpipat, U.: Fast and memory efficient differentially private-sgd via jl projections. Advances in Neural Information Processing Systems 34, 19680–19691 (2021)
2021
Later among the works it cites.
Chattopadhyay, A., Filmus, Y., Koroth, S., Meir, O., Pitassi, T.: Query-to-communication lifting using low-discrepancy gadgets. SIAM Journal on Computing 50(1), 171–210 (2021)
2021
Later among the works it cites.
Jung, C., Ligett, K., Neel, S., Roth, A., Sharifi-Malvajerdi, S., Shenfeld, M.: A new analysis of differential privacy’s generalization guarantees (invited paper). In: STOC. p. 9. ACM (2021)
2021
Later among the works it cites.
2021
Later among the works it cites.
Pagh, R., Stausholm, N.M.: Efficient differentially private f0 linear sketching. In: ICDT. LIPIcs, vol. 186, pp. 18:1–18:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
2021
Later among the works it cites.
2021
Later among the works it cites.
Upadhyay, J., Upadhyay, S.: A framework for private matrix analysis in sliding window model. In: ICML. Proceedings of Machine Learning Research, vol. 139, pp. 10465–10475. PMLR (2021)
2021
Later among the works it cites.
2021
Later among the works it cites.
2022
Later among the works it cites.
Diakonikolas, I., Kane, D.M., Pensia, A., Pittas, T.: Streaming algorithms for high-dimensional robust statistics. In: International Conference on Machine Learning, ICML. pp. 5061–5117 (2022)
2022
Later among the works it cites.
Kontorovich, A., Sadigurschi, M., Stemmer, U.: Adaptive data analysis with correlated observations. In: ICML. Proceedings of Machine Learning Research, vol. 162, pp. 11483–11498. PMLR (2022)
2022
Later among the works it cites.
Pagh, R., Thorup, M.: Improved utility analysis of private countsketch. CoRR abs/2205.08397 (2022)
2022
Later among the works it cites.