Document Open Access Logo

Limits of Preprocessing

Authors Yuval Filmus, Yuval Ishai, Avi Kaplan, Guy Kindler

PDF

File

Thumbnail PDF
PDF
LIPIcs.CCC.2020.17.pdf
  • Filesize: 0.57 MB
  • 22 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
  • Theory of computation → Communication complexity
  • Theory of computation → Circuit complexity
Keywords
  • circuit
  • communication complexity
  • IPPP
  • preprocessing
  • PRF
  • simultaneous messages

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

It is a classical result that the inner product function cannot be computed by an AC⁰ circuit [Merrick L. Furst et al., 1981; Miklós Ajtai, 1983; Johan Håstad, 1986]. It is conjectured that this holds even if we allow arbitrary preprocessing of each of the two inputs separately. We prove this conjecture when the preprocessing of one of the inputs is limited to output n + n/(log^{ω(1)} n) bits. Our methods extend to many other functions, including pseudorandom functions, and imply a (weak but nontrivial) limitation on the power of encoding inputs in low-complexity cryptography. Finally, under cryptographic assumptions, we relate the question of proving variants of the main conjecture with the question of learning AC⁰ under simple input distributions.

Cite As Get BibTex

Yuval Filmus, Yuval Ishai, Avi Kaplan, and Guy Kindler. Limits of Preprocessing. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 17:1-17:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.CCC.2020.17

Author Details

Yuval Filmus
  • Technion - Israel Institute of Technology, Haifa, Israel
Yuval Ishai
  • Technion - Israel Institute of Technology, Haifa, Israel
Avi Kaplan
  • Technion - Israel Institute of Technology, Haifa, Israel
Guy Kindler
  • Hebrew University of Jerusalem, Jerusalem, Israel

Funding

  • Filmus, Yuval: Supported by the European Union’s Horizon 2020 research and innovation programme under grant agreement No 802020-ERC-HARMONIC.
  • Ishai, Yuval: Supported by ERC Project NTSC (742754), NSF-BSF grant 2015782, BSF grant 2018393, and a grant from the Ministry of Science and Technology, Israel and Department of Science and Technology, Government of India.
  • Kaplan, Avi: Supported by the European Union’s Horizon 2020 research and innovation programme under grant agreement No 802020-ERC-HARMONIC, and ERC Project NTSC (742754).

Acknowledgements

We thank Andrej Bogdanov, Mika Göös, Sajin Koroth, Dinesh Krishnamoorthy, Srikanth Srinivasan, and anonymous reviewers for helpful discussions, comments, and pointers.

References

  1. Miklós Ajtai. Σ^1_1-formulae on finite structures. Ann. Pure Appl. Logic, 24(1):1-48, 1983. URL: https://doi.org/10.1016/0168-0072(83)90038-6.
  2. Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, and Alon Rosen. Candidate weak pseudorandom functions in AC⁰ ∘ MOD₂. In Innovations in Theoretical Computer Science, ITCS'14, Princeton, NJ, USA, January 12-14, 2014, pages 251-260, 2014. URL: https://doi.org/10.1145/2554797.2554821.
  3. Josh Alman and R. Ryan Williams. Probabilistic rank and matrix rigidity. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 641-652, 2017. URL: https://doi.org/10.1145/3055399.3055484.
  4. László Babai, Peter Frankl, and Janos Simon. Complexity classes in communication complexity theory (preliminary version). In 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27-29 October 1986, pages 337-347, 1986. URL: https://doi.org/10.1109/SFCS.1986.15.
  5. László Babai, Anna Gál, Peter G. Kimmel, and Satyanarayana V. Lokam. Communication complexity of simultaneous messages. SIAM J. Comput., 33(1):137-166, 2003. URL: https://doi.org/10.1137/S0097539700375944.
  6. Abhishek Banerjee, Chris Peikert, and Alon Rosen. Pseudorandom functions and lattices. In Advances in Cryptology - EUROCRYPT 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15-19, 2012. Proceedings, pages 719-737, 2012. URL: https://doi.org/10.1007/978-3-642-29011-4_42.
  7. Avrim Blum, Merrick L. Furst, Jeffrey C. Jackson, Michael J. Kearns, Yishay Mansour, and Steven Rudich. Weakly learning DNF and characterizing statistical query learning using fourier analysis. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal, Québec, Canada, pages 253-262. ACM, 1994. URL: https://doi.org/10.1145/195058.195147.
  8. Andrej Bogdanov, Yuval Ishai, and Akshayaram Srinivasan. Unconditionally secure computation against low-complexity leakage. In Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2019, Proceedings, Part II, volume 11693 of Lecture Notes in Computer Science, pages 387-416, 2019. URL: https://doi.org/10.1007/978-3-030-26951-7_14.
  9. Andrej Bogdanov and Alon Rosen. Pseudorandom functions: Three decades later. In Tutorials on the Foundations of Cryptography, pages 79-158. Springer, Cham, 2017. URL: https://doi.org/10.1007/978-3-319-57048-8_3.
  10. Dan Boneh, Yuval Ishai, Alain Passelègue, Amit Sahai, and David J. Wu. Exploring crypto dark matter: - new simple PRF candidates and their applications. In Theory of Cryptography - 16th International Conference, TCC 2018, Panaji, India, November 11-14, 2018, Proceedings, Part II, volume 11240 of Lecture Notes in Computer Science, pages 699-729, 2018. URL: https://doi.org/10.1007/978-3-030-03810-6_25.
  11. Arkadev Chattopadhyay and Rahul Santhanam. Lower bounds on interactive compressibility by constant-depth circuits. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 619-628, 2012. URL: https://doi.org/10.1109/FOCS.2012.74.
  12. Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, and Ning Xie. AC⁰ ∘ MOD₂ lower bounds for the boolean inner product. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 35:1-35:14, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.35.
  13. Amit Daniely, Nati Linial, and Shai Shalev-Shwartz. From average case complexity to improper learning complexity. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 441-448, 2014. URL: https://doi.org/10.1145/2591796.2591820.
  14. Ning Ding, Yanli Ren, and Dawu Gu. PAC learning depth-3 AC⁰ circuits of bounded top fanin. In International Conference on Algorithmic Learning Theory, ALT 2017, 15-17 October 2017, Kyoto University, Kyoto, Japan, pages 667-680, 2017. URL: http://proceedings.mlr.press/v76/ding17a.html.
  15. Bella Dubrov and Yuval Ishai. On the randomness complexity of efficient sampling. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pages 711-720, 2006. URL: https://doi.org/10.1145/1132516.1132615.
  16. Zeev Dvir and Benjamin Edelman. Matrix rigidity and the croot-lev-pach lemma. CoRR, abs/1708.01646, 2017. URL: http://arxiv.org/abs/1708.01646.
  17. Merrick L. Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. In 22nd Annual Symposium on Foundations of Computer Science, Nashville, Tennessee, USA, 28-30 October 1981, pages 260-270, 1981. URL: https://doi.org/10.1109/SFCS.1981.35.
  18. Edgar N. Gilbert. A comparison of signalling alphabets. The Bell system technical journal, 31(3):504-522, 1952. Google Scholar
  19. Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. J. ACM, 33(4):792-807, 1986. URL: https://doi.org/10.1145/6490.6503.
  20. Mika Göös, Toniann Pitassi, and Thomas Watson. The landscape of communication complexity classes. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 86:1-86:15, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.86.
  21. Robert M. Gray. Entropy and information theory. Springer Science &Business Media, 2011. Google Scholar
  22. Johan Håstad. Almost optimal lower bounds for small depth circuits. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA, pages 6-20, 1986. URL: https://doi.org/10.1145/12130.12132.
  23. Michael J. Kearns. Efficient noise-tolerant learning from statistical queries. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, pages 392-401. ACM, 1993. URL: https://doi.org/10.1145/167088.167200.
  24. Nathan Linial, Yishay Mansour, and Noam Nisan. Constant depth circuits, fourier transform, and learnability. In 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989, pages 574-579, 1989. URL: https://doi.org/10.1109/SFCS.1989.63537.
  25. Pavel Pudlák, Vojtech Rödl, and Petr Savický. Graph complexity. Acta Inf., 25(5):515-535, 1988. URL: https://doi.org/10.1007/BF00279952.
  26. Alexander A. Razborov. On rigid matrices. preprint, 1989. Google Scholar
  27. Guy N. Rothblum. How to compute under AC⁰ leakage without secure hardware. In Advances in Cryptology - CRYPTO 2012 - 32nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012. Proceedings, volume 7417 of Lecture Notes in Computer Science, pages 552-569, 2012. URL: https://doi.org/10.1007/978-3-642-32009-5_32.
  28. Rocco A. Servedio and Emanuele Viola. On a special case of rigidity. Electronic Colloquium on Computational Complexity (ECCC), 19:144, 2012. URL: http://eccc.hpi-web.de/report/2012/144.
  29. Avishay Tal. The bipartite formula complexity of inner-product is quadratic. Electronic Colloquium on Computational Complexity (ECCC), 23:181, 2016. URL: http://eccc.hpi-web.de/report/2016/181.
  30. Avishay Tal. Tight bounds on the fourier spectrum of AC⁰. In 32nd Computational Complexity Conference, CCC 2017, July 6-9, 2017, Riga, Latvia, volume 79 of LIPIcs, pages 15:1-15:31, 2017. URL: https://doi.org/10.4230/LIPIcs.CCC.2017.15.
  31. Salil P. Vadhan. On learning vs. refutation. In Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017, pages 1835-1848, 2017. URL: http://proceedings.mlr.press/v65/vadhan17a.html.
  32. Leslie G. Valiant. A theory of the learnable. In Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1984, Washington, DC, USA, pages 436-445, 1984. URL: https://doi.org/10.1145/800057.808710.
  33. R. R. Varshamov. Estimate of the number of signals in error correcting codes. Docklady Akad. Nauk, SSSR, 117:739-741, 1957. Google Scholar
  34. Emanuele Viola. Extractors for circuit sources. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 220-229, 2011. URL: https://doi.org/10.1109/FOCS.2011.20.
  35. Henning Wunderlich. On a theorem of razborov. Computational Complexity, 21(3):431-477, 2012. URL: https://doi.org/10.1007/s00037-011-0021-5.
  36. Andrew Chi-Chih Yao. Some complexity questions related to distributive computing (preliminary report). In Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1979, Atlanta, Georgia, USA, pages 209-213, 1979. URL: https://doi.org/10.1145/800135.804414.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact