19992022

Research activity per year

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

Search results

  • 2022

    Lower Bounds on Stabilizer Rank

    Peleg, S., Volk, B. L. & Shpilka, A., 1 Jan 2022, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022. Braverman, M. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 110. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 215).

    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

  • 2021

    Hitting sets and reconstruction for dense orbits in VPe and ΣΠΣ circuits

    Medini, D. & Shpilka, A., 1 Jul 2021, 36th Computational Complexity Conference, CCC 2021. Kabanets, V. (ed.). Dagstuhl, Germany: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 19:1-19:27 19. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 200).

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

  • Learnability Can Be Independent of Set Theory (Invited Paper)

    Ben-David, S., Hrubes, P., Moran, S., Shpilka, A. & Yehudayoff, A., 2021, Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. New York, NY, USA: Association for Computing Machinery, p. 11 1 p. (STOC 2021).

    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

  • 2020

    A generalized Sylvester-Gallai type theorem for quadratic polynomials

    Peleg, S. & Shpilka, A., 1 Jul 2020, 35th Computational Complexity Conference, CCC 2020. Saraf, S. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 8. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 169).

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

  • Explicit and Efficient Constructions of Coding Schemes for the Binary Deletion Channel

    Con, R. & Shpilka, A., Jun 2020, 2020 IEEE International Symposium on Information Theory, ISIT 2020 - Proceedings. Institute of Electrical and Electronics Engineers Inc., p. 84-89 6 p. 9173977. (IEEE International Symposium on Information Theory - Proceedings; vol. 2020-June).

    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

  • 2019

    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

  • 2018

    A PSPACE construction of a hitting set for the closure of small algebraic circuits

    Forbes, M. A. & Shpilka, A., 20 Jun 2018, STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Henzinger, M., Kempe, D. & Diakonikolas, I. (eds.). Association for Computing Machinery, p. 87-99 13 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

  • 2017

    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

  • 2016

    Efficiently decoding Reed-Muller codes from random errors

    Saptharishi, R., Shpilka, A. & Volk, B. L., 19 Jun 2016, STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. Mansour, Y. & Wichs, D. (eds.). Association for Computing Machinery, p. 227-235 9 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. 19-21-June-2016).

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

  • Identity testing and lower bounds for read-k oblivious algebraic branching programs

    Anderson, M., Forbes, M. A., Saptharishi, R., Shpilka, A. & Volk, B. L., 1 May 2016, 31st Conference on Computational Complexity, CCC 2016. Raz, R. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 30:1-30:25 (Leibniz International Proceedings in Informatics, LIPIcs; vol. 50).

    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

  • 2015

    Compressing and Teaching for Low VC-Dimension

    Moran, S., Shpilka, A., Wigderson, A. & Yehudayoff, A., 11 Dec 2015, Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015. IEEE Computer Society, p. 40-51 12 p. 7354386. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2015-December).

    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

  • 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

  • 2014

    Approximate nonnegative rank is equivalent to the smooth rectangle bound

    Kol, G., Moran, S., Shpilka, A. & Yehudayoff, A., 2014, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings. PART 1 ed. Springer Verlag, p. 701-712 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

  • Direct sum fails for zero error average communication

    Kol, G., Moran, S., Shpilka, A. & Yehudayoff, A., 2014, ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science. Association for Computing Machinery, p. 517-522 6 p. (ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science).

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

  • Equivalence of polynomial identity testing and deterministic multivariate polynomial factorization

    Kopparty, S., Saraf, S. & Shpilka, A., 2014, Proceedings - IEEE 29th Conference on Computational Complexity, CCC 2014. IEEE Computer Society, p. 169-180 12 p. 6875486. (Proceedings of the Annual IEEE Conference on Computational Complexity).

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

  • Hitting sets for multilinear read-once algebraic branching programs, in any order

    Forbes, M. A., Saptharishi, R. & Shpilka, A., 2014, STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 867-875 9 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    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

  • 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

  • 2013

    Explicit Noether normalization for simultaneous conjugation via polynomial identity testing

    Forbes, M. A. & Shpilka, A., 2013, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 16th International Workshop, APPROX 2013 and 17th International Workshop, RANDOM 2013, Proceedings. p. 527-542 16 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8096 LNCS).

    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

  • 2012

    Capacity achieving two-write WOM codes

    Shpilka, A., 2012, LATIN 2012: Theoretical Informatics - 10th Latin American Symposium, Proceedings. p. 631-642 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7256 LNCS).

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

  • High sum-rate three-write and non-binary WOM codes

    Yaakobi, E. & Shpilka, A., 2012, 2012 IEEE International Symposium on Information Theory Proceedings, ISIT 2012. p. 1386-1390 5 p. 6283488. (IEEE International Symposium on Information Theory - Proceedings).

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

  • On identity testing of tensors, low-rank recovery and compressed sensing

    Forbes, M. A. & Shpilka, A., 2012, STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing. p. 163-171 9 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

  • On sunflowers and matrix multiplication

    Alon, N., Shpilka, A. & Umans, C., 2012, Proceedings - 2012 IEEE 27th Conference on Computational Complexity, CCC 2012. p. 214-223 10 p. 6243397. (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

  • 2011

    Explicit dimension reduction and its applications

    Karnin, Z. S., Rabani, Y. & Shpilka, A., 2011, Proceedings - 26th Annual IEEE Conference on Computational Complexity, CCC 2011. p. 262-272 11 p. 5959815. (Proceedings of the Annual IEEE Conference on Computational Complexity).

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

  • On sums of locally testable affine invariant properties

    Ben-Sasson, E., Grigorescu, E., Maatouk, G., Shpilka, A. & Sudan, M., 2011, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 14th International Workshop, APPROX 2011 and 15th International Workshop, RANDOM 2011, Proceedings. p. 400-411 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6845 LNCS).

    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

  • 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

  • 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

  • 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

  • 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

  • 2010

    Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in

    Karnin, Z. S., Mukhopadhyay, P., Shpilka, A. & Volkovich, I., 2010, STOC'10 - Proceedings of the 2010 ACM International Symposium on Theory of Computing. p. 649-657 9 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    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 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

  • 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

  • 2009

    Explicit construction of a small epsilon-net for linear threshold functions

    Rabani, Y. & Shpilka, A., 2009, STOC'09 - Proceedings of the 2009 ACM International Symposium on Theory of Computing. p. 649-658 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

  • Improved polynomial identity testing for read-once formulas

    Shpilka, A. & Volkovich, I., 2009, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings. p. 700-713 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5687 LNCS).

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

  • 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

  • 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

  • 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

  • 2008

    Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in

    Karnin, Z. S. & Shpilka, A., 2008, Proceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008. p. 280-291 12 p. 4558830. (Proceedings of the Annual IEEE Conference on Computational Complexity).

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

  • Hardness-randomness tradeoffs for bounded depth arithmetic circuits

    Dvir, Z., Shpilka, A. & Yehudayoff, A., 2008, STOC'08: Proceedings of the 2008 ACM Symposium on Theory of Computing. Association for Computing Machinery (ACM), p. 741-748 8 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

  • Noisy Interpolating Sets for low degree polynomials

    Dvir, Z. & Shpilka, A., 2008, Proceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008. p. 140-148 9 p. 4558818. (Proceedings of the Annual IEEE Conference on Computational Complexity).

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