![](https://dblp1.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp1.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp1.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp1.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp1.uni-trier.de/img/search.dark.16x16.png)
default search action
Amir Shpilka
Person information
Refine list
![note](https://dblp1.uni-trier.de/img/note-mark.dark.12x12.png)
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2024
- [j58]Roni Con
, Amir Shpilka
, Itzhak Tamo
:
Optimal Two-Dimensional Reed-Solomon Codes Correcting Insertions and Deletions. IEEE Trans. Inf. Theory 70(7): 5012-5016 (2024) - [c74]Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka
:
Lower Bounds for Set-Multilinear Branching Programs. CCC 2024: 20:1-20:20 - [c73]Jop Briët, Matthias Christandl, Itai Leigh, Amir Shpilka, Jeroen Zuiddam:
Discreteness of Asymptotic Tensor Ranks (Extended Abstract). ITCS 2024: 20:1-20:14 - [c72]Shir Peleg, Amir Shpilka, Ben Lee Volk:
Tensor Reconstruction Beyond Constant Rank. ITCS 2024: 87:1-87:20 - [c71]Ido Nahshon
, Amir Shpilka
:
New Bounds on Quotient Polynomials with Applications to Exact Division and Divisibility Testing of Sparse Polynomials. ISSAC 2024: 91-99 - 2023
- [j57]Emmanuel Abbe, Ori Sberlo, Amir Shpilka
, Min Ye:
Reed-Muller Codes. Found. Trends Commun. Inf. Theory 20(1-2): 1-156 (2023) - [j56]Roni Con
, Amir Shpilka
, Itzhak Tamo
:
Reed Solomon Codes Against Adversarial Insertions and Deletions. IEEE Trans. Inf. Theory 69(5): 2991-3000 (2023) - [c70]Suryajith Chillara, Coral Grichener, Amir Shpilka
:
On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts. STACS 2023: 22:1-22:20 - [i85]Jop Briët, Matthias Christandl, Itai Leigh, Amir Shpilka
, Jeroen Zuiddam:
Discreteness of asymptotic tensor ranks. CoRR abs/2306.01718 (2023) - [i84]Ido Nahshon, Amir Shpilka
:
New Bounds on Quotient Polynomials with Applications to Exact Divisibility and Divisibility Testing of Sparse Polynomials. CoRR abs/2308.03885 (2023) - [i83]Roni Con, Amir Shpilka, Itzhak Tamo:
Optimal Two-Dimensional Reed-Solomon Codes Correcting Insertions and Deletions. CoRR abs/2311.02771 (2023) - [i82]Prerona Chatterjee
, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka:
Lower Bounds for Set-Multilinear Branching Programs. CoRR abs/2312.15874 (2023) - [i81]Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka:
Exponential Lower Bounds Against Sums of ROABPs. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [j55]Shir Peleg, Amir Shpilka
, Ben Lee Volk:
Lower Bounds on Stabilizer Rank. Quantum 6: 652 (2022) - [j54]Yuval Rabani
, Amir Shpilka
:
Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions. SIAM J. Comput. 51(5): 1692-1702 (2022) - [j53]Roni Con
, Amir Shpilka
:
Improved Constructions of Coding Schemes for the Binary Deletion Channel and the Poisson Repeat Channel. IEEE Trans. Inf. Theory 68(5): 2920-2940 (2022) - [j52]Roni Con
, Amir Shpilka
, Itzhak Tamo
:
Explicit and Efficient Constructions of Linear Codes Against Adversarial Insertions and Deletions. IEEE Trans. Inf. Theory 68(10): 6516-6526 (2022) - [c69]Shir Peleg, Amir Shpilka
:
Robust Sylvester-Gallai Type Theorem for Quadratic Polynomials. SoCG 2022: 43:1-43:15 - [c68]Shir Peleg, Ben Lee Volk, Amir Shpilka
:
Lower Bounds on Stabilizer Rank. ITCS 2022: 110:1-110:4 - [c67]Roni Con, Amir Shpilka
, Itzhak Tamo:
Reed Solomon Codes Against Adversarial Insertions and Deletions. ISIT 2022: 2940-2945 - [i80]Roni Con, Amir Shpilka, Itzhak Tamo:
Explicit and Efficient Constructions of linear Codes Against Adversarial Insertions and Deletions. CoRR abs/2201.06130 (2022) - [i79]Shir Peleg, Amir Shpilka:
Robust Sylvester-Gallai type theorem for quadratic polynomials. CoRR abs/2202.04932 (2022) - [i78]Suryajith Chillara, Coral Grichener, Amir Shpilka
:
On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts. CoRR abs/2207.10588 (2022) - [i77]Shir Peleg, Amir Shpilka
, Ben Lee Volk:
Tensor Reconstruction Beyond Constant Rank. CoRR abs/2209.04177 (2022) - [i76]Suryajith Chillara, Coral Grichener, Amir Shpilka:
On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts. Electron. Colloquium Comput. Complex. TR22 (2022) - [i75]Shir Peleg, Amir Shpilka, Ben Lee Volk:
Tensor Reconstruction Beyond Constant Rank. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [j51]Emmanuel Abbe, Amir Shpilka
, Min Ye
:
Reed-Muller Codes: Theory and Algorithms. IEEE Trans. Inf. Theory 67(6): 3251-3277 (2021) - [j50]Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson:
Proof Complexity Lower Bounds from Algebraic Circuit Complexity. Theory Comput. 17: 1-88 (2021) - [c66]Dori Medini, Amir Shpilka
:
Hitting Sets and Reconstruction for Dense Orbits in VP_{e} and ΣΠΣ Circuits. CCC 2021: 19:1-19:27 - [c65]Shai Ben-David, Pavel Hrubes, Shay Moran
, Amir Shpilka
, Amir Yehudayoff:
Learnability can be independent of set theory (invited paper). STOC 2021: 11 - [c64]Shir Peleg, Amir Shpilka
:
Polynomial time deterministic identity testing algorithm for Σ[3]ΠΣΠ[2] circuits via Edelstein-Kelly type theorem for quadratic polynomials. STOC 2021: 259-271 - [i74]Dori Medini, Amir Shpilka:
Hitting Sets and Reconstruction for Dense Orbits in VPe and ΣΠΣ Circuits. CoRR abs/2102.05632 (2021) - [i73]Shir Peleg, Amir Shpilka, Ben Lee Volk:
Lower Bounds on Stabilizer Rank. CoRR abs/2106.03214 (2021) - [i72]Roni Con, Amir Shpilka, Itzhak Tamo:
Linear and Reed Solomon Codes Against Adversarial Insertions and Deletions. CoRR abs/2107.05699 (2021) - [i71]Dori Medini, Amir Shpilka:
Hitting Sets and Reconstruction for Dense Orbits in VP$_e$ and $\Sigma\Pi\Sigma$ Circuits. Electron. Colloquium Comput. Complex. TR21 (2021) - [i70]Shir Peleg, Amir Shpilka, Ben Lee Volk:
Lower Bounds on Stabilizer Rank. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [c63]Shir Peleg, Amir Shpilka
:
A Generalized Sylvester-Gallai Type Theorem for Quadratic Polynomials. CCC 2020: 8:1-8:33 - [c62]Amir Shpilka
:
On Some Recent Advances in Algebraic Complexity (Invited Talk). FSTTCS 2020: 6:1-6:1 - [c61]Roni Con, Amir Shpilka
:
Explicit and Efficient Constructions of Coding Schemes for the Binary Deletion Channel. ISIT 2020: 84-89 - [c60]Ori Sberlo, Amir Shpilka
:
On the Performance of Reed-Muller Codes with respect to Random Errors and Erasures. SODA 2020: 1357-1376 - [i69]Emmanuel Abbe, Amir Shpilka, Min Ye:
Reed-Muller Codes: Theory and Algorithms. CoRR abs/2002.03317 (2020) - [i68]Shir Peleg, Amir Shpilka:
A generalized Sylvester-Gallai type theorem for quadratic polynomials. CoRR abs/2003.05152 (2020) - [i67]Shir Peleg, Amir Shpilka:
Polynomial time deterministic identity testingalgorithm for Σ[3]ΠΣΠ[2] circuits via Edelstein-Kelly type theorem for quadratic polynomials. CoRR abs/2006.08263 (2020)
2010 – 2019
- 2019
- [j49]Gillat Kol, Shay Moran, Amir Shpilka
, Amir Yehudayoff:
Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound. Comput. Complex. 28(1): 1-25 (2019) - [j48]Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka
, Amir Yehudayoff
:
Learnability can be undecidable. Nat. Mach. Intell. 1(1): 44-48 (2019) - [j47]Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka
, Amir Yehudayoff
:
Author Correction: Learnability can be undecidable. Nat. Mach. Intell. 1(2): 121 (2019) - [c59]Amir Shpilka
:
Sylvester-Gallai type theorems for quadratic polynomials. STOC 2019: 1203-1214 - [e1]Amir Shpilka:
34th Computational Complexity Conference, CCC 2019, July 18-20, 2019, New Brunswick, NJ, USA. LIPIcs 137, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2019, ISBN 978-3-95977-116-0 [contents] - [i66]Amir Shpilka:
Sylvester-Gallai type theorems for quadratic polynomials. CoRR abs/1904.06245 (2019) - [i65]Roni Con, Amir Shpilka:
Explicit and Efficient Constructions of Coding Schemes for the Binary Deletion Channel and the Poisson Repeat Channel. CoRR abs/1909.10177 (2019) - 2018
- [j46]Michael A. Forbes, Amir Shpilka
, Ben Lee Volk:
Succinct Hitting Sets and Barriers to Proving Lower Bounds for Algebraic Circuits. Theory Comput. 14(1): 1-45 (2018) - [j45]Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi
, Amir Shpilka
, Ben Lee Volk:
Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs. ACM Trans. Comput. Theory 10(1): 3:1-3:30 (2018) - [c58]Michael A. Forbes, Amir Shpilka
:
A PSPACE construction of a hitting set for the closure of small algebraic circuits. STOC 2018: 1180-1192 - [i64]Ori Sberlo, Amir Shpilka:
On the Performance of Reed-Muller Codes with respect to Random Errors and Erasures. CoRR abs/1811.12447 (2018) - 2017
- [j44]Amir Shpilka
, Avishay Tal, Ben lee Volk:
On the Structure of Boolean Functions with Small Spectral Norm. Comput. Complex. 26(1): 229-273 (2017) - [j43]Gil Cohen, Amir Shpilka
, Avishay Tal:
On the degree of univariate polynomials over the integers. Comb. 37(3): 419-464 (2017) - [j42]Ramprasad Saptharishi
, Amir Shpilka
, Ben Lee Volk
:
Efficiently Decoding Reed-Muller Codes From Random Errors. IEEE Trans. Inf. Theory 63(4): 1954-1960 (2017) - [c57]Michael A. Forbes, Amir Shpilka
, Ben Lee Volk:
Succinct hitting sets and barriers to proving algebraic circuits lower bounds. STOC 2017: 653-664 - [i63]Michael A. Forbes, Amir Shpilka, Ben Lee Volk:
Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds. CoRR abs/1701.05328 (2017) - [i62]Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff:
A learning problem that is independent of the set theory ZFC axioms. CoRR abs/1711.05195 (2017) - [i61]Michael A. Forbes, Amir Shpilka:
A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits. CoRR abs/1712.09967 (2017) - [i60]Michael A. Forbes, Amir Shpilka:
A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits. Electron. Colloquium Comput. Complex. TR17 (2017) - [i59]Michael A. Forbes, Amir Shpilka, Ben Lee Volk:
Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j41]Gillat Kol, Shay Moran
, Amir Shpilka
, Amir Yehudayoff:
Direct Sum Fails for Zero-Error Average Communication. Algorithmica 76(3): 782-795 (2016) - [j40]Rafael Oliveira, Amir Shpilka
, Ben lee Volk:
Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas. Comput. Complex. 25(2): 455-505 (2016) - [j39]Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka
:
Tight lower bounds for linear 2-query LCCs over finite fields. Comb. 36(1): 1-36 (2016) - [c56]Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi
, Amir Shpilka
, Ben Lee Volk:
Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs. CCC 2016: 30:1-30:25 - [c55]Michael A. Forbes, Amir Shpilka
, Iddo Tzameret, Avi Wigderson:
Proof Complexity Lower Bounds from Algebraic Circuit Complexity. CCC 2016: 32:1-32:17 - [c54]Ramprasad Saptharishi
, Amir Shpilka
, Ben Lee Volk:
Efficiently decoding Reed-Muller codes from random errors. STOC 2016: 227-235 - [i58]Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson:
Proof Complexity Lower Bounds from Algebraic Circuit Complexity. CoRR abs/1606.05050 (2016) - [i57]Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson:
Proof Complexity Lower Bounds from Algebraic Circuit Complexity. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j38]Swastik Kopparty, Shubhangi Saraf, Amir Shpilka
:
Equivalence of Polynomial Identity Testing and Polynomial Factorization. Comput. Complex. 24(2): 295-331 (2015) - [j37]Amir Shpilka
, Ilya Volkovich
:
Read-once polynomial identity testing. Comput. Complex. 24(3): 477-532 (2015) - [j36]Michael A. Forbes, Amir Shpilka
:
Complexity Theory Column 88: Challenges in Polynomial Factorization1. SIGACT News 46(4): 32-49 (2015) - [j35]Emmanuel Abbe, Amir Shpilka
, Avi Wigderson:
Reed-Muller Codes for Random Erasures and Errors. IEEE Trans. Inf. Theory 61(10): 5229-5252 (2015) - [c53]Rafael Oliveira, Amir Shpilka
, Ben Lee Volk:
Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas. CCC 2015: 304-322 - [c52]Shay Moran, Amir Shpilka
, Avi Wigderson, Amir Yehudayoff:
Compressing and Teaching for Low VC-Dimension. FOCS 2015: 40-51 - [c51]Emmanuel Abbe, Amir Shpilka
, Avi Wigderson:
Reed-Muller Codes for Random Erasures and Errors. STOC 2015: 297-306 - [i56]Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff:
Teaching and compressing for low VC-dimension. CoRR abs/1502.06187 (2015) - [i55]Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk:
Decoding high rate Reed-Muller codes from random errors in near linear time. CoRR abs/1503.09092 (2015) - [i54]Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk:
Identity Testing and Lower Bounds for Read-$k$ Oblivious Algebraic Branching Programs. CoRR abs/1511.07136 (2015) - [i53]Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk:
Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs. Electron. Colloquium Comput. Complex. TR15 (2015) - [i52]Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff:
Teaching and compressing for low VC-dimension. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j34]Amir Shpilka
, Avishay Tal:
On the minimal fourier degree of symmetric Boolean functions. Comb. 34(3): 359-377 (2014) - [j33]Amir Shpilka
:
Capacity-Achieving Multiwrite WOM Codes. IEEE Trans. Inf. Theory 60(3): 1481-1487 (2014) - [j32]Eitan Yaakobi, Amir Shpilka
:
High Sum-Rate Three-Write and Nonbinary WOM Codes. IEEE Trans. Inf. Theory 60(11): 7006-7015 (2014) - [j31]Amir Shpilka
, Ilya Volkovich:
On Reconstruction and Testing of Read-Once Formulas. Theory Comput. 10: 465-514 (2014) - [c50]Swastik Kopparty, Shubhangi Saraf, Amir Shpilka
:
Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization. CCC 2014: 169-180 - [c49]Zeev Dvir, Rafael Oliveira, Amir Shpilka
:
Testing Equivalence of Polynomials under Shifts. ICALP (1) 2014: 417-428 - [c48]Gillat Kol, Shay Moran, Amir Shpilka
, Amir Yehudayoff:
Approximate Nonnegative Rank Is Equivalent to the Smooth Rectangle Bound. ICALP (1) 2014: 701-712 - [c47]Amir Shpilka
, Avishay Tal, Ben lee Volk:
On the structure of boolean functions with small spectral norm. ITCS 2014: 37-48 - [c46]Gillat Kol, Shay Moran, Amir Shpilka
, Amir Yehudayoff:
Direct sum fails for zero error average communication. ITCS 2014: 517-522 - [c45]Michael A. Forbes, Ramprasad Saptharishi
, Amir Shpilka
:
Hitting sets for multilinear read-once algebraic branching programs, in any order. STOC 2014: 867-875 - [i51]Zeev Dvir, Rafael Oliveira, Amir Shpilka:
Testing Equivalence of Polynomials under Shifts. CoRR abs/1401.3714 (2014) - [i50]Emmanuel Abbe, Amir Shpilka, Avi Wigderson:
Reed-Muller codes for random erasures and errors. CoRR abs/1411.4590 (2014) - [i49]Rafael Oliveira, Amir Shpilka, Ben Lee Volk:
Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas. CoRR abs/1411.7492 (2014) - [i48]Zeev Dvir, Rafael Oliveira, Amir Shpilka:
Testing Equivalence of Polynomials under Shifts. Electron. Colloquium Comput. Complex. TR14 (2014) - [i47]Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff:
Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound. Electron. Colloquium Comput. Complex. TR14 (2014) - [i46]Swastik Kopparty, Shubhangi Saraf, Amir Shpilka:
Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization. Electron. Colloquium Comput. Complex. TR14 (2014) - [i45]Rafael Oliveira, Amir Shpilka, Ben Lee Volk:
Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [j30]Noga Alon, Amir Shpilka
, Christopher Umans:
On sunflowers and matrix multiplication. Comput. Complex. 22(2): 219-243 (2013) - [j29]Shachar Lovett
, Partha Mukhopadhyay, Amir Shpilka
:
Pseudorandom generators for CC0[p] and the Fourier spectrum of low-degree polynomials over finite fields. Comput. Complex. 22(4): 679-725 (2013) - [j28]Elad Haramaty, Amir Shpilka
, Madhu Sudan:
Optimal Testing of Multivariate Polynomials over Small Prime Fields. SIAM J. Comput. 42(2): 536-562 (2013) - [j27]Zohar Shay Karnin, Partha Mukhopadhyay, Amir Shpilka
, Ilya Volkovich:
Deterministic Identity Testing of Depth-4 Multilinear Circuits with Bounded Top Fan-in. SIAM J. Comput. 42(6): 2114-2131 (2013) - [j26]Amir Shpilka
:
New Constructions of WOM Codes Using the Wozencraft Ensemble. IEEE Trans. Inf. Theory 59(7): 4520-4529 (2013) - [c44]Michael A. Forbes, Amir Shpilka
:
Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing. APPROX-RANDOM 2013: 527-542 - [c43]Michael A. Forbes, Amir Shpilka
:
Quasipolynomial-Time Identity Testing of Non-commutative and Read-Once Oblivious Algebraic Branching Programs. FOCS 2013: 243-252 - [i44]Michael A. Forbes, Amir Shpilka:
Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing. CoRR abs/1303.0084 (2013) - [i43]Amir Shpilka, Ben lee Volk:
On the Structure of Boolean Functions with Small Spectral Norm. CoRR abs/1304.0371 (2013) - [i42]Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka:
Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order. CoRR abs/1309.5668 (2013) - [i41]Michael A. Forbes, Amir Shpilka:
Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing. Electron. Colloquium Comput. Complex. TR13 (2013) - [i40]Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka:
Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order. Electron. Colloquium Comput. Complex. TR13 (2013) - [i39]Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff:
Direct Sum Fails for Zero Error Average Communication. Electron. Colloquium Comput. Complex. TR13 (2013) - [i38]Amir Shpilka, Ben lee Volk:
On the Structure of Boolean Functions with Small Spectral Norm. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j25]Zohar Shay Karnin, Yuval Rabani
, Amir Shpilka
:
Explicit Dimension Reduction and Its Applications. SIAM J. Comput. 41(1): 219-249 (2012) - [c42]Noga Alon, Amir Shpilka
, Christopher Umans:
On Sunflowers and Matrix Multiplication. CCC 2012: 214-223 - [c41]Gil Cohen, Amir Shpilka
, Avishay Tal:
On the degree of univariate polynomials over the integers. ITCS 2012: 409-427 - [c40]Eitan Yaakobi, Amir Shpilka
:
High sum-rate three-write and non-binary WOM codes. ISIT 2012: 1386-1390 - [c39]Amir Shpilka
:
Capacity Achieving Two-Write WOM Codes. LATIN 2012: 631-642 - [c38]Michael A. Forbes, Amir Shpilka
:
On identity testing of tensors, low-rank recovery and compressed sensing. STOC 2012: 163-172 - [i37]Amir Shpilka:
Capacity achieving multiwrite WOM codes. CoRR abs/1209.1128 (2012) - [i36]Michael A. Forbes, Amir Shpilka:
Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs. CoRR abs/1209.2408 (2012) - [i35]Michael A. Forbes, Amir Shpilka:
Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [j24]Zeev Dvir, Amir Shpilka
:
Towards dimension expanders over finite fields. Comb. 31(3): 305-320 (2011) - [j23]Zohar Shay Karnin, Amir Shpilka
:
Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in. Comb. 31(3): 333-364 (2011) - [j22]Parikshit Gopalan, Ryan O'Donnell, Rocco A. Servedio
, Amir Shpilka
, Karl Wimmer:
Testing Fourier Dimensionality and Sparsity. SIAM J. Comput. 40(4): 1075-1100 (2011) - [j21]Zeev Dvir, Amir Shpilka:
Noisy Interpolating Sets for Low-Degree Polynomials. Theory Comput. 7(1): 1-18 (2011) - [c37]Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka
, Madhu Sudan:
On Sums of Locally Testable Affine Invariant Properties. APPROX-RANDOM 2011: 400-411 - [c36]Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka
, Madhu Sudan:
Symmetric LDPC Codes are not Necessarily Locally Testable. CCC 2011: 55-65 - [c35]Amir Shpilka
, Avishay Tal:
On the Minimal Fourier Degree of Symmetric Boolean Functions. CCC 2011: 200-209 - [c34]Zohar Shay Karnin, Yuval Rabani
, Amir Shpilka
:
Explicit Dimension Reduction and Its Applications. CCC 2011: 262-272 - [c33]Amir Shpilka
:
Recent Results on Polynomial Identity Testing. CSR 2011: 397-400 - [c32]Elad Haramaty, Amir Shpilka
, Madhu Sudan:
Optimal Testing of Multivariate Polynomials over Small Prime Fields. FOCS 2011: 629-637 - [c31]Arnab Bhattacharyya, Zeev Dvir, Amir Shpilka
, Shubhangi Saraf:
Tight Lower Bounds for 2-query LCCs over Finite Fields. FOCS 2011: 638-647 - [i34]Amir Shpilka:
New constructions of WOM codes using the Wozencraft ensemble. CoRR abs/1110.6590 (2011) - [i33]Michael A. Forbes, Amir Shpilka:
On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing. CoRR abs/1111.0663 (2011) - [i32]Noga Alon, Amir Shpilka, Christopher Umans:
On Sunflowers and Matrix Multiplication. Electron. Colloquium Comput. Complex. TR11 (2011) - [i31]Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan:
On Sums of Locally Testable Affine Invariant Properties. Electron. Colloquium Comput. Complex. TR11 (2011) - [i30]Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka:
Tight lower bounds for 2-query LCCs over finite fields. Electron. Colloquium Comput. Complex. TR11 (2011) - [i29]Gil Cohen, Amir Shpilka, Avishay Tal:
On the Degree of Univariate Polynomials Over the Integers. Electron. Colloquium Comput. Complex. TR11 (2011) - [i28]Michael A. Forbes, Amir Shpilka:
On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing. Electron. Colloquium Comput. Complex. TR11 (2011) - [i27]Elad Haramaty, Amir Shpilka, Madhu Sudan:
Optimal testing of multivariate polynomials over small prime fields. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [j20]Parikshit Gopalan, Amir Shpilka
, Shachar Lovett
:
The Complexity of Boolean Functions in Different Characteristics. Comput. Complex. 19(2): 235-263 (2010) - [j19]Amir Shpilka
, Amir Yehudayoff:
Arithmetic Circuits: A survey of recent results and open questions. Found. Trends Theor. Comput. Sci. 5(3-4): 207-388 (2010) - [j18]Yuval Rabani
, Amir Shpilka
:
Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions. SIAM J. Comput. 39(8): 3501-3520 (2010) - [c30]Shachar Lovett
, Partha Mukhopadhyay, Amir Shpilka
:
Pseudorandom Generators for CC0[p] and the Fourier Spectrum of Low-Degree Polynomials over Finite Fields. FOCS 2010: 695-704 - [c29]Amir Shpilka
, Ilya Volkovich:
On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors. ICALP (1) 2010: 408-419 - [c28]Elad Haramaty, Amir Shpilka
:
On the structure of cubic and quartic polynomials. STOC 2010: 331-340 - [c27]Zohar Shay Karnin, Partha Mukhopadhyay, Amir Shpilka
, Ilya Volkovich:
Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in. STOC 2010: 649-658 - [i26]Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Madhu Sudan:
Symmetric LDPC codes are not necessarily locally testable. Electron. Colloquium Comput. Complex. TR10 (2010) - [i25]Gil Cohen, Amir Shpilka:
On the degree of symmetric functions on the Boolean cube. Electron. Colloquium Comput. Complex. TR10 (2010) - [i24]Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka:
Pseudorandom generators for CC0[p] and the Fourier spectrum of low-degree polynomials over finite fields. Electron. Colloquium Comput. Complex. TR10 (2010) - [i23]Amir Shpilka, Avishay Tal:
On the Minimal Fourier Degree of Symmetric Boolean Functions. Electron. Colloquium Comput. Complex. TR10 (2010) - [i22]Amir Shpilka, Ilya Volkovich:
Read-Once Polynomial Identity Testing. Electron. Colloquium Comput. Complex. TR10 (2010) - [i21]Amir Shpilka, Ilya Volkovich:
On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [j17]Ali Juma, Valentine Kabanets, Charles Rackoff, Amir Shpilka
:
The Black-Box Query Complexity of Polynomial Summation. Comput. Complex. 18(1): 59-79 (2009) - [j16]Amir Shpilka
:
Constructions of Low-degree and Error-Correcting epsilon-Biased Generators. Comput. Complex. 18(4): 495-525 (2009) - [j15]Amir Shpilka
:
Interpolation of Depth-3 Arithmetic Circuits with Two Multiplication Gates. SIAM J. Comput. 38(6): 2130-2161 (2009) - [j14]Sofya Raskhodnikova, Dana Ron
, Amir Shpilka
, Adam D. Smith:
Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem. SIAM J. Comput. 39(3): 813-842 (2009) - [j13]Zeev Dvir, Amir Shpilka
, Amir Yehudayoff:
Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits. SIAM J. Comput. 39(4): 1279-1293 (2009) - [c26]Amir Shpilka
, Ilya Volkovich:
Improved Polynomial Identity Testing for Read-Once Formulas. APPROX-RANDOM 2009: 700-713 - [c25]Parikshit Gopalan, Shachar Lovett
, Amir Shpilka
:
On the Complexity of Boolean Functions in Different Characteristics. CCC 2009: 173-183 - [c24]Zohar Shay Karnin, Amir Shpilka
:
Reconstruction of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-in. CCC 2009: 274-285 - [c23]Parikshit Gopalan, Ryan O'Donnell, Rocco A. Servedio
, Amir Shpilka
, Karl Wimmer:
Testing Fourier Dimensionality and Sparsity. ICALP (1) 2009: 500-512 - [c22]Yuval Rabani
, Amir Shpilka
:
Explicit construction of a small epsilon-net for linear threshold functions. STOC 2009: 649-658 - [i20]Parikshit Gopalan, Shachar Lovett, Amir Shpilka:
On the Complexity of Boolean Functions in Different Characteristics. Electron. Colloquium Comput. Complex. TR09 (2009) - [i19]Elad Haramaty, Amir Shpilka:
On the Structure of Cubic and Quartic Polynomials. Electron. Colloquium Comput. Complex. TR09 (2009) - [i18]Zohar Shay Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich:
Deterministic identity testing of depth 4 multilinear circuits with bounded top fan-in. Electron. Colloquium Comput. Complex. TR09 (2009) - [i17]Zohar Shay Karnin, Yuval Rabani, Amir Shpilka:
Explicit Dimension Reduction and Its Applications. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [j12]Ran Raz
, Amir Shpilka, Amir Yehudayoff:
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits. SIAM J. Comput. 38(4): 1624-1647 (2008) - [c21]Zeev Dvir, Amir Shpilka
:
Noisy Interpolating Sets for Low Degree Polynomials. CCC 2008: 140-148 - [c20]Zohar Shay Karnin, Amir Shpilka
:
Black Box Polynomial Identity Testing of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-In. CCC 2008: 280-291 - [c19]Zeev Dvir, Amir Shpilka
:
Towards Dimension Expanders over Finite Fields. CCC 2008: 304-310 - [c18]Amir Shpilka
, Ilya Volkovich
:
Read-once polynomial identity testing. STOC 2008: 507-516 - [c17]Zeev Dvir, Amir Shpilka
, Amir Yehudayoff:
Hardness-randomness tradeoffs for bounded depth arithmetic circuits. STOC 2008: 741-748 - [i16]Zeev Dvir, Amir Shpilka:
Noisy Interpolating Sets for Low Degree Polynomials. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [j11]Zeev Dvir, Amir Shpilka
:
An Improved Analysis of Linear Mergers. Comput. Complex. 16(1): 34-59 (2007) - [j10]Zeev Dvir, Amir Shpilka
:
Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits. SIAM J. Comput. 36(5): 1404-1434 (2007) - [c16]Ran Raz
, Amir Shpilka, Amir Yehudayoff:
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits. FOCS 2007: 438-448 - [c15]Sofya Raskhodnikova, Dana Ron, Amir Shpilka, Adam D. Smith:
Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem. FOCS 2007: 559-569 - [c14]Amir Shpilka
:
Interpolation of depth-3 arithmetic circuits with two multiplication gates. STOC 2007: 284-293 - [i15]Zeev Dvir, Amir Shpilka:
Towards Dimension Expanders Over Finite Fields. Electron. Colloquium Comput. Complex. TR07 (2007) - [i14]Zeev Dvir, Amir Shpilka, Amir Yehudayoff:
Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits. Electron. Colloquium Comput. Complex. TR07 (2007) - [i13]Ali Juma, Valentine Kabanets, Charles Rackoff, Amir Shpilka:
The black-box query complexity of polynomial summation. Electron. Colloquium Comput. Complex. TR07 (2007) - [i12]Zohar Shay Karnin, Amir Shpilka:
Black Box Polynomial Identity Testing of Depth-3 Arithmetic Circuits with Bounded Top Fan-in. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [j9]Elchanan Mossel
, Amir Shpilka
, Luca Trevisan
:
On epsilon-biased generators in NC0. Random Struct. Algorithms 29(1): 56-81 (2006) - [j8]Amir Shpilka
, Avi Wigderson:
Derandomizing Homomorphism Testing in General Groups. SIAM J. Comput. 36(4): 1215-1230 (2006) - [j7]Adam R. Klivans, Amir Shpilka:
Learning Restricted Models of Arithmetic Circuits. Theory Comput. 2(10): 185-206 (2006) - [c13]Amir Shpilka
:
Constructions of Low-Degree and Error-Correcting in-Biased Generators. CCC 2006: 33-45 - [i11]Ran Raz, Amir Shpilka, Amir Yehudayoff:
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [j6]Ran Raz
, Amir Shpilka
:
Deterministic polynomial identity testing in non-commutative models. Comput. Complex. 14(1): 1-19 (2005) - [j5]László Babai
, Amir Shpilka
, Daniel Stefankovic
:
Locally testable cyclic codes. IEEE Trans. Inf. Theory 51(8): 2849-2858 (2005) - [c12]Zeev Dvir, Amir Shpilka
:
An Improved Analysis of Mergers. APPROX-RANDOM 2005: 270-281 - [c11]Zeev Dvir, Amir Shpilka
:
Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits. STOC 2005: 592-601 - [i10]Zeev Dvir, Amir Shpilka:
Locally Decodable Codes with 2 queries and Polynomial Identity Testing for depth 3 circuits. Electron. Colloquium Comput. Complex. TR05 (2005) - [i9]Zeev Dvir, Amir Shpilka:
An Improved Analysis of Mergers. Electron. Colloquium Comput. Complex. TR05 (2005) - [i8]Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka, Adam D. Smith:
Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size. Electron. Colloquium Comput. Complex. TR05 (2005) - [i7]Amir Shpilka:
Constructions of low-degree and error-correcting epsilon-biased sets. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [c10]Ran Raz
, Amir Shpilka
:
Deterministic Polynomial Identity Testing in Non-Commutative Models. CCC 2004: 215-222 - [c9]Ran Raz
, Amir Shpilka
:
On the Power of Quantum Proofs. CCC 2004: 260-274 - [c8]Amir Shpilka
, Avi Wigderson:
Derandomizing homomorphism testing in general groups. STOC 2004: 427-435 - 2003
- [j4]Ran Raz
, Amir Shpilka:
Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates. SIAM J. Comput. 32(2): 488-513 (2003) - [j3]Amir Shpilka
:
Lower Bounds for Matrix Product. SIAM J. Comput. 32(5): 1185-1200 (2003) - [c7]Adam R. Klivans, Amir Shpilka
:
Learning Arithmetic Circuits via Partial Derivatives. COLT 2003: 463-476 - [c6]László Babai
, Amir Shpilka
, Daniel Stefankovic
:
Locally Testable Cyclic Codes. FOCS 2003: 116-125 - [c5]Elchanan Mossel, Amir Shpilka
, Luca Trevisan
:
On e-Biased Generators in NC0. FOCS 2003: 136-145 - [i6]Elchanan Mossel, Amir Shpilka, Luca Trevisan:
On epsilon-Biased Generators in NC0. Electron. Colloquium Comput. Complex. TR03 (2003) - 2002
- [j2]Amir Shpilka
:
Affine projections of symmetric polynomials. J. Comput. Syst. Sci. 65(4): 639-659 (2002) - [i5]Amir Shpilka:
Lower Bounds for Matrix Product. CoRR cs.CC/0201001 (2002) - 2001
- [b1]Amir Shpilka:
Lower bounds for small depth arithmetic and Boolean circuits. (חסמים תחתונים למעגלים אריתמטים ובוליאנים מעומק חסום.). Hebrew University of Jerusalem, Israel, 2001 - [j1]Amir Shpilka
, Avi Wigderson:
Depth-3 arithmetic circuits over fields of characteristic zero. Comput. Complex. 10(1): 1-27 (2001) - [c4]Amir Shpilka
:
Affine Projections of Symmetric Polynomials. CCC 2001: 160-171 - [c3]Amir Shpilka
:
Lower Bounds for Matrix Product. FOCS 2001: 358-367 - [c2]Ran Raz
, Amir Shpilka
:
Lower bounds for matrix product, in bounded depth circuits with arbitrary gates. STOC 2001: 409-418 - [i4]Amir Shpilka:
Affine Projections of Symmetric Polynomials. Electron. Colloquium Comput. Complex. TR01 (2001) - [i3]Amir Shpilka:
Lower bounds for matrix product. Electron. Colloquium Comput. Complex. TR01 (2001) - 2000
- [i2]Ran Raz, Amir Shpilka:
Lower Bounds for Matrix Product, in Bounded Depth Circuits with Arbitrary Gates. Electron. Colloquium Comput. Complex. TR00 (2000)
1990 – 1999
- 1999
- [c1]Amir Shpilka
, Avi Wigderson:
Depth-3 Arithmetic Formulae over Fields of Characteristic Zero. CCC 1999: 87- - [i1]Amir Shpilka, Avi Wigderson:
Depth-3 Arithmetic Formulae over Fields of Characteristic Zero. Electron. Colloquium Comput. Complex. TR99 (1999)
Coauthor Index
![](https://dblp1.uni-trier.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-08-05 21:16 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint