2013-2014 Papers

This page contains links to some papers produced during the academic year of 2013-2014.

Theoretical Computer Science

• S. Aaronson, A. Ambainis. The need for structure in quantum speedups. Theory of Computing, accpeted for publication.
• A. Ai, Z. Dvir, S. Saraf, A. Wigderson. Sylvester-Gallai type theorems for approximate collinearity. Forum of Mathematics-Sigma. To appear.
• N. Alon. Paul Erdos and the Probabilistic Method. 2014.
• N. Alon, H. Aydinian, H. Huang. Maximizing the number of nonnegative subsets. SIAM J. Discrete Math. 28 (2014). 811-816.
• N. Alon, J. Bourgain. Addictive Patterns in Multiplicative Subgroups. Geometric and Fuctional Analysis 24 (2014). no. 3. 721-739.
• N. Alon, J. Fox. Easily Testable Graph Properties. 2014.
• N. Alon, M. Ghaffari, B. Haeupler, M. Khabbazian. Broadcast Throughput in Radio Networks: Routing vs. Network Coding. Proc. SODA 2014. 1831-1843.
• N. Alon, R. Hod, A. Weinstein. On Active and Passive Testing. 2013.
• N. Alon, S. Snir, R, Yuster. On the compatibility of quartet trees. Proc. SODA 2014. 535-545.
• N. Alon, H. Aydinian, H. Huang. Maximizing the number of nonnegative subsets. SIAM J. Discrete Math. 28 (2014). 811-816.
• A. Ambainis. On physical problems that are slightly more difficult than QMA. IEEE Conference on Computational Complexity (CCC) 2014, accepted for publication.
• A. Ambainis, K. Prusis. A tight lower bound on certificate complexity in terms of block sensitivity and sensitivity. ArXiv preprint 1402.5078.
• A. Ambainis, A. Rosmanis, D. Unruh. Quantum attacks on classical proof systems - The hardness of quantum rewinding. ArXiv preprint 1404.6898.
• G. Cohen, A. Ganor, R. Raz. Two sides of the coin problem. ECCC 21:23. 2014.
• S. Cook, Y. Filmus, D. Le. The complexity of the comparator circuit value problem. To appear in Transactions on Computation Theory.
• A. De, I. Diakonikolas, R. Servedio. Deterministic approximate counting for Juntas of degree-2 polynomial threshold functions. IEEE Conference on Computational Complexity (CCC) 2014. 229-240.
• A. De, R. Servedio. Efficient deterministic approximate counting for low-degree polynomial threshold functions. ACM Symposium on Theory of Computing (STOC) 2014. 832-841.
• Z. Dvir, S. Saraf, A. Wigderson. Breaking the quadratic barrier for 3-LCC's over the reals. STOC 2014. 784-793.
• Y. Filmus, H. Hatami. Bounds on the sum of L1 influences. ArXiv 1404.3396. 2014.
• Y. Filmus, J. Oren. Efficient Voting via The Top-k Elicitation Scheme: A Probabilistic Approach. To appear in EC14.
• Y. Filmus, J. Ward. Monotone submodular maximization over a matroid via non-oblivious local search. SIAM J. Computing 43(2). 514-542. 2014.
• A. Ganor, G. Kol, R. Raz. Exponential separation of information and communication. ECCC 21:49. 2014.
• A. Ganor, R. Raz. Space pseudorandom generators by communication complexity lower bounds. Proc. of RANDOM 2014.
• D. Gavinsky, O. Meir, O. Weinstein, A. Wigderson. Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture. STOC 2014. 213-222.
• E. Gnang. A combinatorial approach to hypermatrix algebra. ArXiv preprint 1403.3134.
• E. Gnang. Computational Aspects of the Combinatorial Nullstellensatz Method. ArXiv preprint 1402.6920.
• E. Gnang. Computing Spectral Elimination Ideals. ArXiv preprint 1403.3557.
• E. Gnang, O. Parzanchevski, Y. Filmus. A Sage TeX Hypermatrix Algebra Package. ArXiv preprint 1403.2630.
• O. Goldreich, A. Wigderson. On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions. ECCC 20:43. 2013.
• O. Goldreich, A. Wigderson. On Derandomizing Algorithms that Err Extremely Rarely. ECCC 20:152. 2013.
• V. Guruswami, A. K. Sinop. Rounding Lasserre SDPs using column selection and spectrum-based approximation schemes for graph partitioning and Quadratic IPs. Under review for Journal of ACM.
• M. Hajiabadi, B. Kapron. Gambling, computational information and encryption security. 8th International Conference on Information-Theoretic Security (ICITS). 2015
• P. Hrubes, A. Wigderson. Non-commutative arithmetic circuits with division. ITCS 2014. 49-66.
• H. Huang, B. Sudakov. The minimum number of nonnegative edges in hypergraph. ArXiv preprint 1309.2549.
• Y. Kalai, R. Raz, R. D. Rothblum. How to Delegate Computations: The Power of No-Signaling Proofs. STOC 2014. 485-494.
• O. Parzanchevski. Mixing in high-dimensional expanders. ArXiv 1310.6477. 2013.
• O. Parzanchevski, R. Rosenthal, R. J. Tessler. Isoperimetric inequalities in simplicial complexes. ArXiv 1207.0638. 2013.