Hi, I'm Avishay, a postdoctoral researcher in the Theoretical Computer Science and Discrete Mathematics group (CSDM) at the Institute for Advanced Study (IAS). In September 2015, I received my PhD from the Weizmann Institute of Science, under the guidance of Ran Raz. Before that, I was an MSc student at the Technion under the guidance of Amir Shpilka. I feel fortunate to have had both Amir and Ran as my mentors. Main Research Interests: Computational Complexity, Analysis of Boolean Functions, Circuit and Formula Lower Bounds, Decision Tree Complexity, Pseudorandomness, Learning, Combinatorics, and the connections between Algorithms and Lower Bounds. My Curriculum Vitae. Contact Info: Address: School of Mathematics, Institute for Advanced Study, Princeton, NJ 08540, USA E-mail: firstname.lastname@gmail.com | Publications Lower Bounds for 2-Query LCCs over Large Alphabet joint with Arnab Bhattacharyya and Sivakanth Gopi. Accepted to RANDOM, 2017. Psuedorandom Generators for Low Sensitivity Functions The Bipartite Formula Complexity of Inner-Product is Quadratic Accepted to STOC, 2017 (merged with "Computing Requires Larger Formulas than Approximating"). Time-Space Hardness of Learning Sparse Parities Degree and Sensitivity: Tails of Two Distributions joint with Parikshit Gopalan, Rocco Servedio and Avi Wigderson. On the Sensitivity Conjecture #SAT Algorithms from Shrinkage Matrix Rigidity of Random Toeplitz Matrices joint with Oded Goldreich. Computational Complexity, 2016 (preliminary version in STOC, 2016). Shrinkage of De Morgan Formulae by Spectral Techniques FOCS, 2014. On Fractional Block Sensitivity PDF Journal-version joint with Raghav Kulkarni. CJTCS, 2016. Two Structural Results for Low Degree Polynomials and Applications joint with Gil Cohen. RANDOM, 2015. An implementation of the algorithm suggested in Theorem 4.1. On the Structure of Boolean Functions with Small Spectral Norm joint with Amir Shpilka and Ben lee Volk. Computational Complexity, 2015 (preliminary version in ITCS, 2014). Improved Average-Case Lower Bounds for De Morgan Formula Size joint with Ilan Komargodski and Ran Raz. SICOMP, 2017 (preliminary version in FOCS, 2013). Properties and Applications of Boolean Function Composition ITCS, 2013. (Best Student Paper) On the Degree of Univariate Polynomials Over the Integers joint with Gil Cohen and Amir Shpilka. Combinatorica, 2016 (preliminary version in ITCS, 2012). On The Minimal Fourier Degree of Symmetric Boolean Functions joint with Amir Shpilka. Combinatorica, 2014 (preliminary version in CCC, 2011). |
