Hard submatrices for non-negative rank and communication complexity. ECCC, 2024.
A subquadratic upper bound on sum-of-squares composition formulas. ECCC, 2024.
New lower bounds against homogeneous non-commutative circuits, with P. Chatterjee. CCC, 2023.
Shadows of Newton polytopes, with A. Yehudayoff. ECCC, 2021.
On the distribution of runners on a circle, European Journal of Combinatorics, 89, 2020.
On the complexity of computing a random Boolean function over the reals, Theory of Computing, 16(9):1–12, 2020.
On $\epsilon$-sensitive monotone computations, Computational Complexity, 29(2), 2020.
Learnability can be undecidable, with S. Ben-David, S. Moran, A. Shpilka and A. Yehudayoff. Nature Machine Intelligence 1(1):44-48, 2019.
Lower bounds for balancing families and depth-two circuits, with S. N. Ramamamorthy, A. Rao and A. Yehudayoff. LIPICS, 2019.
A note on monotone real circuits, with P. Pudlak. IPL, 131:15-19, ACM Transactions on Computation Theory, 9(1), 2018.
Random formulas, monotone circuits, and interpolation, with P. Pudlak. FOCS, 121-131, 2017.
On hardness of multilinearization, and VNP-completeness in characteristics two, ACM Transactions on Computation Theory, 9(1), 2016.
Semantic versus syntactic cutting planes, with Y. Filmus and M. Lauria. STACS, 2016.
Circuits with medium fan-in, with A. Rao. IEEE Conference on Computational Complexity, 2015.
Short proofs for the determinant identities, with I. Tzameret. SIAM J. Comput. 44(2): 193–212, 2015.
On families of anticommuting matrices, Linear Algebra and Applications, 493:494–507, 2016.
Total maps of Turing categories, with J.R.B. Cockett and P.J.W. Hofstra, Electr. Notes Theor. Comput. Sci., 38:129-146, 2014.
A note on semantic cutting planes, Electronic Colloquium in Computational Complexity, 2013.
Non-commutative arithmetic circuits with division, with A. Wigderson. ITCS, 2014.
On the real τ-conjecture and the distribution of complex roots. Theory of Computing, 9(10): 403–411, 2013.
An asymptotic bound on the composition number of integer sums of squares formulas, with A. Wigderson and A. Yehudayoff. Canadian Mathematical Bulletin, 56:70–79, 2013.
On the nonnegative rank of distance matrices. Information Processing Letters, 112(11): 457–461, 2012.
Formulas are exponentially stronger than monotone circuits in non-commutative setting, with A. Yehudayoff. Conference on Computational Complexity, 2013.
Timed sets, functional complexity, and computability, with R. Cockett, J. Dıaz-Boıls, and J. Gallagher. Electr. Notes Theor. Comput. Sci., 286:117–137, 2012.
Short proofs for the determinant identities, with I. Tzameret. In STOC’ 12 Proceedings of the 44th symposium on Theory of Computing, pages 193–212, 2012.
Non-commutative circuits and the sum of squares problem, with A. Wigderson and A. Yehudayoff. J. Amer. Math. Soc., 24:871–898, 2011.
How much commutativity is needed to prove polynomial identities? Electronic Colloquium in Computational Complexity, 2011.
Homogeneous formulas and symmetric polynomials, with A. Yehudayoff. Computational Complexity, 20(3):559–578, 2011.
Arithmetic complexity in ring extensions, with A. Yehudayoff. Theory of Computing, 7:119–129, 2011.
Non-commutative circuits and the sum of squares problem, with A. Wigderson and A. Yehudayoff. In STOC’ 10 Proceedings of the 42nd symposium on Theory of Computing, pages 667–676, 2010.
On convex complexity measures, with S. Jukna, A. Kulikov, and P. Pudlak. Theoretical Computer Science, 411(16):1842–1854, 2010.
Relationless completeness and separations, with A. Wigderson and A. Yehudayoff. In IEEE Conference on Computational Complexity, pages 280–290, 2010.
On lengths of proofs in non-classical logics. Annals of Pure and Applied Logic, 157(194-205), 2009.
Proof complexity of polynomial identities, with I. Tzameret. CCC, pages 41–51, 2009.
Kreisel’s conjecture with minimality principle. Journal of Symbolic logic, 74(3):976–988, 2009.
Monotone separations for constant degree polynomials, with A. Yehudayoff.. Information Processing Letters, 110(1): 1-3, 2009.
Lower bounds for modal logics. Journal of Symbolic logic, 72(3):941–958, 2007.
A lower bound for intuitionistic logic. Ann. Pure Appl. Logic, 146:72–90, 2007.
Theories very close to PA where Kreisel’s conjecture is false. Journal of Symbolic logic, 72:123–137, 2007.