19992022

Research activity per year

If you made any changes in Pure these will be visible here soon.

Search results

  • Conference contribution

    On the complexity of Boolean functions in different characteristics

    Gopalan, P., Lovett, S. & Shpilka, A., 2009, Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009. p. 173-183 11 p. 5231259. (Proceedings of the Annual IEEE Conference on Computational Complexity).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • On the degree of univariate polynomials over the integers

    Cohen, G., Shpilka, A. & Tal, A., 2012, ITCS 2012 - Innovations in Theoretical Computer Science Conference. p. 409-427 19 p. (ITCS 2012 - Innovations in Theoretical Computer Science Conference).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • On the minimal fourier degree of symmetric Boolean functions

    Shpilka, A. & Tal, A., 2011, Proceedings - 26th Annual IEEE Conference on Computational Complexity, CCC 2011. p. 200-209 10 p. 5959809. (Proceedings of the Annual IEEE Conference on Computational Complexity).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • On the performance of reed-muller codes with respect to random errors and erasures

    Sberlo, O. & Shpilka, A., 2020, 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020. Chawla, S. (ed.). Association for Computing Machinery, p. 1357-1376 20 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2020-January).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • On the relation between polynomial identity testing and finding variable disjoint factors

    Shpilka, A. & Volkovich, I., 2010, Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings. PART 1 ed. p. 408-419 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6198 LNCS, no. PART 1).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • On the structure of boolean functions with small spectral norm

    Shpilka, A., Tal, A. & Volk, B. L., 2014, ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science. Association for Computing Machinery, p. 37-47 11 p. (ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • On the structure of cubic and quartic polynomials

    Haramaty, E. & Shpilka, A., 2010, STOC'10 - Proceedings of the 2010 ACM International Symposium on Theory of Computing. p. 331-340 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • On ε-biased generators in NC0

    Mossel, E., Shpilka, A. & Trevisan, L., 2003, Proceedings - 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003. IEEE Computer Society, p. 136-145 10 p. 1238188. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2003-January).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • Optimal testing of multivariate polynomials over small prime fields

    Haramaty, E., Shpilka, A. & Sudan, M., 2011, Proceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011. p. 629-637 9 p. 6108224. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • Polynomial Time Deterministic Identity Testing Algorithm for Σ[3]ΠΣΠ[2] Circuits via Edelstein–Kelly Type Theorem for Quadratic Polynomials

    Peleg, S. & Shpilka, A., 15 Jun 2021, STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Khuller, S. & Williams, V. V. (eds.). Association for Computing Machinery, p. 259-271 13 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • Proof complexity lower bounds from algebraic circuit complexity

    Forbes, M. A., Shpilka, A., Tzameret, I. & Wigderson, A., 1 May 2016, 31st Conference on Computational Complexity, CCC 2016. Raz, R. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 32:1-32:17 (Leibniz International Proceedings in Informatics, LIPIcs; vol. 50).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • Pseudorandom generators for CC0[p] and the fourier spectrum of low-degree polynomials over finite fields

    Lovett, S., Mukhopadhyay, P. & Shpilka, A., 2010, Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010. IEEE Computer Society, p. 695-704 10 p. 5671338. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs

    Forbes, M. A. & Shpilka, A., 2013, Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013. p. 243-252 10 p. 6686160. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • Read-once polynomial identity testing

    Shpilka, A. & Volkovich, I., 2008, STOC'08: Proceedings of the 2008 ACM Symposium on Theory of Computing. Association for Computing Machinery (ACM), p. 507-516 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • Recent results on polynomial identity testing

    Shpilka, A., 2011, Computer Science - Theory and Applications - 6th International Computer Science Symposium in Russia, CSR 2011, Proceedings. p. 397-400 4 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6651 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • Reconstruction of generalized Depth-3 arithmetic circuits with bounded top fan-in

    Karnin, Z. S. & Shpilka, A., 2009, Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009. p. 274-285 12 p. 5231339. (Proceedings of the Annual IEEE Conference on Computational Complexity).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • Reed-muller codes for random erasures and errors

    Abbe, E., Shpilka, A. & Wigderson, A., 14 Jun 2015, STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 297-306 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. 14-17-June-2015).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • Reed Solomon Codes Against Adversarial Insertions and Deletions

    Con, R., Shpilka, A. & Tamo, I., 2022, 2022 IEEE International Symposium on Information Theory, ISIT 2022. Institute of Electrical and Electronics Engineers Inc., p. 2940-2945 6 p. (IEEE International Symposium on Information Theory - Proceedings; vol. 2022-June).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • Robust Sylvester-Gallai Type Theorem for Quadratic Polynomials

    Peleg, S. & Shpilka, A., 1 Jun 2022, 38th International Symposium on Computational Geometry, SoCG 2022. Goaoc, X. & Kerber, M. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 43. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 224).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • Strong lower bounds for approximating distribution support size and the distinct elements problem

    Raskhodnikova, S., Ron, D., Shpilka, A. & Smith, A., 2007, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007. p. 559-569 11 p. 4389525. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • Subexponential size hitting sets for bounded depth multilinear formulas

    Oliveira, R., Shpilka, A. & Volk, B. L., 1 Jun 2015, 30th Conference on Computational Complexity, CCC 2015. Zuckerman, D. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 304-322 19 p. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 33).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • Succinct hitting sets and barriers to proving algebraic circuits lower bounds

    Forbes, M. A., Shpilka, A. & Volk, B. L., 19 Jun 2017, STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. McKenzie, P., King, V. & Hatami, H. (eds.). Association for Computing Machinery, p. 653-664 12 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F128415).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • Sylvester-Gallai type theorems for quadratic polynomials

    Shpilka, A., 23 Jun 2019, STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Charikar, M. & Cohen, E. (eds.). Association for Computing Machinery, p. 1203-1214 12 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • Symmetric LDPC codes are not necessarily locally testable

    Ben-Sasson, E., Maatouk, G., Shpilka, A. & Sudan, M., 2011, Proceedings - 26th Annual IEEE Conference on Computational Complexity, CCC 2011. p. 55-65 11 p. 5959821. (Proceedings of the Annual IEEE Conference on Computational Complexity).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • Testing equivalence of polynomials under shifts

    Dvir, Z., De Oliveira, R. M. & Shpilka, A., 2014, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings. PART 1 ed. Springer Verlag, p. 417-428 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8572 LNCS, no. PART 1).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • Testing fourier dimensionality and sparsity

    Gopalan, P., O'Donnell, R., Servedio, R. A., Shpilka, A. & Wimmer, K., 2009, Automata, Languages and Programming - 36th International Colloquium, ICALP 2009, Proceedings. PART 1 ed. p. 500-512 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5555 LNCS, no. PART 1).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • Tight lower bounds for 2-query LCCs over finite fields

    Bhattacharyya, A., Dvir, Z., Shpilka, A. & Saraf, S., 2011, Proceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011. p. 638-647 10 p. 6108225. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • Towards dimension expanders over finite fields

    Dvir, Z. & Shpilka, A., 2008, Proceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008. p. 304-310 7 p. 4558832. (Proceedings of the Annual IEEE Conference on Computational Complexity).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • Editorial

    Preface

    Shpilka, A., 1 Jul 2019, In: Leibniz International Proceedings in Informatics, LIPIcs. 137

    Research output: Contribution to journalEditorial