Amir Shpilka Bib File
@article{AlonSU11,
author = {Noga Alon and
Amir Shpilka and
Chris Umans},
title = {On Sunflowers and Matrix Multiplication},
journal = {Electronic Colloquium on Computational Complexity (ECCC)},
volume = {18},
year = {2011},
pages = {67},
ee = {http://eccc.hpi-web.de/report/2011/067},
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/ASU11.pdf}
}
@ARTICLE{BabaiSS05,
AUTHOR = {L{\'a}szl{\'o} Babai and Amir Shpilka and Daniel Stefankovic},
TITLE = {Locally testable cyclic codes},
JOURNAL = {IEEE Transactions on Information Theory},
YEAR = {2005},
VOLUME = {51},
PAGES = {2849-2858},
NUMBER = {8},
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/BSS_LTCC.pdf}
}
@inproceedings{BDSS11,
author = {Arnab Bhattacharyya and
Zeev Dvir and
Shubhangi Saraf and
Amir Shpilka},
title = {Tight lower bounds for 2-query LCCs over finite fields},
BOOKTITLE = {Proceedings of the 52nd FOCS},
YEAR = {2011},
PAGES = {638-647}
ee = {http://eccc.hpi-web.de/report/2011/054},
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/BDSS11.pdf}
}
@inproceedings{BGMSS11,
author = {Eli Ben-Sasson and
Elena Grigorescu and
Ghid Maatouk and
Amir Shpilka and
Madhu Sudan},
title = {On Sums of Locally Testable Affine Invariant Properties},
booktitle = {Approximation, Randomization and Combinatorial Optimization.
Algorithms and Techniques, volume 6845 of LNCS},
year = {2011},
pages = {400-411},
ee = {http://dx.doi.org/10.1007/978-3-642-22935-0_34},
crossref = {DBLP:conf/approx/2011},
bibsource = {DBLP, http://dblp.uni-trier.de},
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/BGMSS11.pdf}
}
@INPROCEEDINGS{BMSS11,
author = {Eli Ben-Sasson and
Ghid Maatouk and
Amir Shpilka and
Madhu Sudan},
title = {Symmetric LDPC codes are not necessarily locally testable},
BOOKTITLE = {Proceedings of the 26th Annual CCC},
year = {2011},
pages = {55-65},
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/BMSS10.pdf}
}
@article{CohenShpilka10,
author = {Gil Cohen and Amir Shpilka},
title = {On the degree of symmetric functions on the Boolean cube},
journal = {Electronic Colloquium on Computational Complexity (ECCC)},
volume = {17},
year = {2010},
pages = {39},
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/CohenShpilka10.pdf}
}
@article{CohenShpilkaTal10,
author = {Gil Cohen and Amir Shpilka and Avishay Tal},
title = {On the Degree of Univariate Polynomials Over the Integers},
journal = {Electronic Colloquium on Computational Complexity (ECCC)},
volume = {18},
year = {2011},
pages = {2},
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/CST10.pdf}
}
@article{DvirShpilka11,
author = {Zeev Dvir and
Amir Shpilka},
title = {Towards dimension expanders over finite fields},
journal = {Combinatorica},
volume = {31},
number = {3},
year = {2011},
pages = {305-320},
ee = {http://dx.doi.org/10.1007/s00493-011-2540-8},
bibsource = {DBLP, http://dblp.uni-trier.de},
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/DimensionExpanders.pdf}
}
@ARTICLE{DvirShpilka11,
AUTHOR = {Zeev Dvir and Amir Shpilka},
TITLE = {Noisy Interpolating Sets for Low Degree Polynomials},
JOURNAL = {Theory of Computing},
YEAR = {2011},
VOLUME = {7},
PAGES = {1-18},
PDF = {http://theoryofcomputing.org/articles/v007a001/v007a001.pdf}
}
@INPROCEEDINGS{DvirShpilka08b,
AUTHOR = {Zeev Dvir and Amir Shpilka},
TITLE = {Noisy Interpolating Sets for Low Degree Polynomials},
BOOKTITLE = {Proceedings of the 23rd Annual CCC},
PAGES = {140-148},
YEAR = {2008},
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/DvirShpilka_NIS.pdf}
}
@ARTICLE{DvirShpilka07,
AUTHOR = {Zeev Dvir and Amir Shpilka},
TITLE = {An Improved Analysis of Linear Mergers},
JOURNAL = {Computational Complexity},
YEAR = {2007},
VOLUME = {16},
PAGES = {34-59},
NUMBER = {1},
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/DvirShpilka_mergers.pdf}
}
@ARTICLE{DvirShpilka06,
AUTHOR = {Zeev Dvir and Amir Shpilka},
TITLE = {Locally decodable codes with 2 queries and polynomial identity testing
for depth 3 circuits},
JOURNAL = {SIAM J. on Computing},
YEAR = {2006},
VOLUME = {36},
PAGES = {1404-1434},
NUMBER = {5},
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/DvirShpilka_LDC_PIT.pdf}
}
@ARTICLE{DSY09,
AUTHOR = {Zeev Dvir and Amir Shpilka and Amir Yehudayoff},
TITLE = {Hardness-Randomness Tradeoffs for Bounded Depth Circuits},
JOURNAL = "SIAM J. on Computing",
year = {2009},
volume = "39",
number = "4",
pages = {1279-1293}
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/DSY.pdf}
}
@INPROCEEDINGS{ForbesShpilka11,
author = {Michael Forbes and
Amir Shpilka},
title = {On identity testing of tensors, low-rank recovery and compressed sensing},
BOOKTITLE = {Proceedings of the 44th Annual STOC},
pages = {163-171},
year = {2012},
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/ForbesShpilka11.pdf}
}
@INPROCEEDINGS{GLS09,
AUTHOR = {Parikshit Gopalan and Shachar Lovett and Amir Shpilka},
TITLE = {On the degree of Boolean functions in different characteristics},
BOOKTITLE = {Proceedings of the 24th Annual CCC},
YEAR = {2009},
PAGES = {173-183}
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/GLS.pdf}
}
@article{GOSSW11,
author = {Parikshit Gopalan and
Ryan O'Donnell and
Rocco A. Servedio and
Amir Shpilka and
Karl Wimmer},
title = {Testing Fourier Dimensionality and Sparsity},
journal = {SIAM J. Comput.},
volume = {40},
number = {4},
year = {2011},
pages = {1075-1100},
ee = {http://dx.doi.org/10.1137/100785429},
bibsource = {DBLP, http://dblp.uni-trier.de},
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/GOSSW09.pdf}
}
@INPROCEEDINGS{HaramatyShpilka10,
AUTHOR = {Elad Haramaty and Amir Shpilka},
TITLE = {On the Structure of Cubic and Quartic Polynomials},
BOOKTITLE = {Proceedings of the 42nd STOC},
YEAR = {2010},
PAGES = {331-340}
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/Cubic.pdf}
}
@INPROCEEDINGS{HaramatySS11,
author = {Elad Haramaty and
Amir Shpilka and
Madhu Sudan},
title = {Optimal testing of multivariate polynomials over small prime fields},
BOOKTITLE = {Proceedings of the 52nd FOCS},
YEAR = {2011},
PAGES = {629-637}
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/HSS11.pdf}
}
@ARTICLE{JKRS,
AUTHOR = {Ali Juma and Valentine Kabanets and Charles Rackoff and Amir Shpilka},
TITLE = {The Black-Box Query Complexity of Polynomial Summation.},
JOURNAL = {Computational Complexity},
YEAR = {2009},
VOLUME = {18},
PAGES = {59-79},
NUMBER = {1},
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/JKRS.pdf}
}
@INPROCEEDINGS{KMSV10,
AUTHOR = {Zohar S. Karnin and Partha Mukhopadhyay and Amir Shpilka and Ilya Volkovich},
TITLE = {Deterministic identity testing of depth 4 multilinear circuits with bounded top fan-in},
BOOKTITLE = {Proceedings of the 42nd Annual STOC},
YEAR = {2010},
PAGES = {649-658}
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/KMSV.pdf}
}
@INPROCEEDINGS{KarninShpilka09,
AUTHOR = {Zohar S. Karnin and Amir Shpilka},
TITLE = {Reconstruction of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-in},
BOOKTITLE = {Proceedings of the 24rd Annual CCC},
YEAR = {2009},
PAGES = {274-285}
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/KarninShpilka09.pdf}
}
@article{KarninShpilka11,
author = {Zohar Shay Karnin and
Amir Shpilka},
title = {Black box polynomial identity testing of generalized depth-3
arithmetic circuits with bounded top fan-in},
journal = {Combinatorica},
volume = {31},
number = {3},
year = {2011},
pages = {333-364},
ee = {http://dx.doi.org/10.1007/s00493-011-2537-3},
bibsource = {DBLP, http://dblp.uni-trier.de},
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/KarninShpilka_BB_PIT.pdf}
}
@article{KRS11,
author = {Zohar Shay Karnin and
Yuval Rabani and
Amir Shpilka},
title = {Explicit Dimension Reduction and Its Applications},
journal = {SIAM Journal on Computing},
year = {2012},
volume = {41},
number = {1},
pages = {219-249},
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/KRS09.pdf}
}
@ARTICLE{KlivansShpilka06,
AUTHOR = {Adam Klivans and Amir Shpilka},
TITLE = {Learning restricted models of arithmetic circuits.},
JOURNAL = {Theory of computing},
YEAR = {2006},
VOLUME = {2},
PAGES = {185-206},
NUMBER = {10},
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/KlivansShpilka_Learning_via_partial_derivatives.pdf}
}
@ARTICLE{MosselST06,
AUTHOR = {Elchanan Mossel and Amir Shpilka and Luca Trevisan},
TITLE = {On epsilon-biased generators in {NC}$^{\mbox{0}}$.},
JOURNAL = {Random Structures and Algorithms},
YEAR = {2006},
VOLUME = {29},
PAGES = {56-81},
NUMBER = {1},
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/MST_NC0.pdf}
}
@ARTICLE{RRSS09,
AUTHOR = {Sofya Raskhodnikova and Dana Ron and Amir Shpilka and Adam Smith},
TITLE = {Strong Lower Bounds for Approximating Distribution Support Size and
the Distinct Elements Problem},
JOURNAL = {SIAM Journal on Computing},
YEAR = {2009},
PAGES = {813-842}
VOLUME = {39}
NUMBER = {3}
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/RRSS.pdf}
}
@INPROCEEDINGS{RabaniShpilka09,
AUTHOR = {Yuval Rabani and Amir Shpilka},
TITLE = {Explicit construction of a small epsilon-net for linear threshold
functions},
BOOKTITLE = {Proceedings of the 41st Annual STOC},
YEAR = {2009},
PAGES = {649-658}
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/RabaniShpilka09.pdf}
}
@ARTICLE{RazShpilka05,
AUTHOR = {Ran Raz and Amir Shpilka},
TITLE = {Deterministic Polynomial Identity Testing in Non Commutative Models},
JOURNAL = {Computational Complexity},
YEAR = {2005},
VOLUME = {14},
PAGES = {1-19},
NUMBER = {1},
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/RazShpilka_PIT.pdf}
}
@INPROCEEDINGS{RazS04a,
AUTHOR = {Ran Raz and Amir Shpilka},
TITLE = {On the Power of Quantum Proofs},
BOOKTITLE = {IEEE Conference on Computational Complexity},
YEAR = {2004},
PAGES = {260-274},
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/RazShpilka_QMA.pdf}
}
@ARTICLE{RazShpilka01,
AUTHOR = {Ran Raz and Amir Shpilka},
TITLE = {Lower bounds for matrix product, in bounded depth circuits with arbitrary
gates},
JOURNAL = {SIAM J. on Computing},
YEAR = {2003},
VOLUME = {32},
PAGES = {488-513},
NUMBER = {2},
PS = {http://www.cs.technion.ac.il/~shpilka/publications/RazShpilka_BoundedDepth.ps.gz}
}
@ARTICLE{RSY08,
AUTHOR = {Ran Raz and Amir Shpilka and Amir Yehudayoff},
TITLE = {A lower bound for the size of syntactically multilinear arithmetic
circuits},
JOURNAL = {SIAM J. on Computing},
YEAR = {2008},
VOLUME = {38},
PAGES = {1624-1647},
NUMBER = {4},
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/RSY_Multilinear.pdf}
}
@Article{Shpilka09,
AUTHOR = {Amir Shpilka},
TITLE = {Interpolation of depth-3 arithmetic circuits with two multiplication
gates},
JOURNAL = {SIAM J. on Computing},
YEAR = {2009},
VOLUME = {38},
PAGES = {2130-2161},
NUMBER = {6},
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/Shpilka_Interpolation.pdf}
}
@ARTICLE{Shpilka09b,
AUTHOR = {Amir Shpilka},
TITLE = {Constructions of Low-Degree and Error-Correcting $\epsilon$-Biased Generators},
JOURNAL = {Computational Complexity},
YEAR = {2009},
VOLUME = {18},
PAGES = {495-525},
NUMBER = {4},
PS = {http://www.cs.technion.ac.il/~shpilka/publications/Shpilka_e_bias.ps}}
@ARTICLE{Shpilka01b,
AUTHOR = {Amir Shpilka},
TITLE = {Lower Bounds for Matrix Product},
JOURNAL = {SIAM J. on Computing},
YEAR = {2003},
VOLUME = {32},
PAGES = {1185-1200},
NUMBER = {5},
PS = {http://www.cs.technion.ac.il/~shpilka/publications/shpilka_a.ps.gz}
}
@ARTICLE{Shpilka01a,
AUTHOR = {Amir Shpilka},
TITLE = {Affine projections of symmetric polynomials},
JOURNAL = {J. of Computer and System Sciences},
YEAR = {2002},
VOLUME = {65},
PAGES = {639-659},
NUMBER = {4},
PS = {http://www.cs.technion.ac.il/~shpilka/publications/Shpilka_AffineProj.ps.gz}
}
@ARTICLE{Shpilka11,
AUTHOR = {Amir Shpilka},
TITLE = {New constructions of WOM codes using the Wozencraft ensemble},
journal = {CoRR},
volume = {abs/1110.6590},
year = {2011},
ee = {http://arxiv.org/abs/1110.6590},
bibsource = {DBLP, http://dblp.uni-trier.de},
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/Shpilka-WOM11.pdf}
}
@INPROCEEDINGS{ShpilkaTal11,
author = {Amir Shpilka and Avishay Tal},
title = {On the Minimal Fourier Degree of Symmetric Boolean Functions},
BOOKTITLE = {Proceedings of the 26th Annual CCC},
year = {2011},
pages = {200-209},
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/ShpilkaTal10.pdf}
}
@PHDTHESIS{ShpilkaThesis,
AUTHOR = {Amir Shpilka},
TITLE = {Lower Bounds for Small Depth Arithmetic and Boolean Circuits },
SCHOOL = {The Hebrew University},
YEAR = {2001},
PS = {http://www.cs.technion.ac.il/~shpilka/publications/Shpilka_thesis.ps.gz}
}
@INPROCEEDINGS{ShpilkaVolkovich08,
AUTHOR = {Amir Shpilka and Ilya Volkovich},
TITLE = {Read-once Polynomial Identity Testing},
BOOKTITLE = {Proceedings of the 40th Annual STOC},
YEAR = {2008},
PAGES = {507-516},
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/ShpilkaVolkovich_ROT.pdf}
}
@INPROCEEDINGS{ShpilkaVolkovich09,
AUTHOR = {Amir Shpilka and Ilya Volkovich},
TITLE = {Improved Polynomial Identity Testing of Read-Once Formulas},
BOOKTITLE = {Approximation, Randomization and Combinatorial Optimization.
Algorithms and Techniques, volume 5687 of LNCS},
YEAR = {2009},
PAGES = {700-713},
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/PROF.pdf}
}
@ARTICLE{ShpilkaW06,
AUTHOR = {Amir Shpilka and Avi Wigderson},
TITLE = {Derandomizing Homomorphism Testing in General Groups},
JOURNAL = {SIAM J. Computing},
YEAR = {2006},
VOLUME = {36},
PAGES = {1215-1230},
NUMBER = {4},
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/ShpilkaWigderson_Homomorphism.pdf}
}
@ARTICLE{ShpilkaWigderson01,
AUTHOR = {Amir Shpilka and Avi Wigderson},
TITLE = {Depth-3 Arithmetic Circuits over Fields of Characteristic Zero},
JOURNAL = {Computational Complexity},
YEAR = {2001},
VOLUME = {10},
PAGES = {1-27},
NUMBER = {1},
PS = {http://www.cs.technion.ac.il/~shpilka/publications/ShpilkaWigderson_d3-circuits.ps.gz}
}
@ARTICLE{ShpilkaYehudayoff,
AUTHOR = {Amir Shpilka and Amir Yehudayoff},
TITLE = {Arithmetic Circuits: A survey of recent results and open questions},
JOURNAL = {Foundations and Trends in Theoretical Computer Science},
YEAR = {2010},
VOLUME = {5},
PAGES = {207-388},
NUMBER = {3-4},
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf}
}
@ARTICLE{YaakobiShpilka12,
AUTHOR = {Eitan Yaakobi and Amir Shpilka},
TITLE = {High Sum-Rate Three-Write and Non-Binary WOM Codes},
YEAR = {2012},
PDF = {http://www.cs.technion.ac.il/~shpilka/publications/YaakobiShpilka12.pdf}
}