2019-2020 Papers

This page contains links to some papers produced during the academic year of 2019-2020.

Theoretical Computer Science

• V. Bulankina and A. Kupavskii. List colorings of Kneser graphs. In preparation 2020.
• N. Frankl and A. Kupavskii. Almost sharp bounds on the number of discrete chains in the plane. SoCG 2020: 48:1–48:15
• P. Frankl and A. Kupavskii. Almost intersecting families. arXiv:2004.08714v1
• P. Frankl and A. Kupavskii. Maximal degrees in subgraphs of Kneser graphs. arXiv:2004.08718v1
• P. Frankl and A. Kupavskii. Intersection theorems for (-1, 0, 1)-vectors. arXiv:2004.08721v1
• S. Kiselev and A. Kupavskii. Rainbow matchings in k-partite hypergraphs. arXiv:2001.02181v2. To appear in Bull. London Math. Soc.
• S. Kiselev and A. Kupavskii. Non-trivial colorings of Kneser graphs. In preparation 2020.
• A. Kupavskii and S. Weltge. Number of vertices and facets in 2-level polytopes. In preparation 2020.
• A. Garg, C. Ikenmeyer, V. Makam, R. Oliveira, M. Walter, A. Wigderson. Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings. CCC 2020.
• P. Burgisser, C. Franks, A. Garg, R. Oliveira, M. Walter, A. Wigderson. Towards a theory of non-commutative optimization: geodesic 1st and 2nd order methods for moment maps and polytopes. FOCS 2019, 845-861.

• Ankit Garg, Visu Makam, Rafael Mendes de Oliveira, Avi Wigderson. More barriers for rank methods, via a "numeric to symbolic" transfer. FOCS 2019, 824-844.

• Mark Braverman, Subhash Khot, and Dor Minzer. On rich $2$-to-$1$ games. ECCC 2019, 26:141.
• Yuval Filmus, Noam Lifshitz, Dor Minzer, and Elchanan Mossel. AND testing and robust judgement aggregation. STOC 2020: 222–233.
• Esty Kelman, Guy Kindler, Noam Lifshitz, Dor Minzer, and Muli Safra. Towards a Proof of the Fourier Entropy Conjecture? CoRR, abs/1911.10579, 2019.
• C.H. Liu and F. Wei. Phase Transition of Degeneracy in Minor-Closed Families. Arxiv:1912.02375, 2020.
• D. Král' , J. A. Noel, S. Norin, J. Volec and F. Wei. Non-bipartite k-common graphs. Arxiv: 2006.09422, 2020.
• D. Král' , J. A. Noel, S. Norin, J. Volec and F. Wei. k-common graphs with high chromatic number. Short note, 2020.
• D. Achlioptas, T. Gouleakis and F. Iliopoulos. Simple local computation algorithms for the Lovász local lemma. SPAA 2020, 1-10.
• D. Harris, F. Iliopoulos and V. Kolmogorov. A new notion of commutativity for the algorithmic Lovász Local Lemma. Technical report. In preparation, 2020.
• F. Iliopoulos. Girth-reducibility and the algorithmic barrier for coloring. Technical report. In submission, 2020. arXiv: 2004.02066.
• Yotam Dikstein, Irit Dinur, Prahladh Harsha, and Noga Ron-Zewi. Locally testable codes via high-dimensional expanders. ECCC 2020, 27:72.
• Matthias Christandl, Peter Vrana, and Jeroen Zuiddam. Barriers for fast matrix multiplication from irreversibility. CCC 2019.
• Matthias Christandl, Francois Le Gall, Vladimir Lysikov, Jeroen Zuiddam. Barriers for rectangular matrix multiplication. arXiv:2003.03019v1, 2020.
• Swastik Kopparty, Guy Moshkovitz and Jeroen Zuiddam. Geometric rank of tensors and subrank of matrix multiplication. CCC 2020.
• Anna Gál, Robert Robere. Lower bounds for (Non-monotone) comparator circuits. ITCS 2020.
• Or Meir, Jakob Nördstrom, Toniann Pitassi, Robert Robere, Susanna F. de Rezende. Lifting with simple gadgets and applications to circuit and proof complexity. ECCC 2019.
• Mika Göös, Jakob Nördstrom, Toniann Pitassi, Robert Robere, Dmitry Sokolov, Susanna F. de Rezende. Automating Algebraic Proof Systems is NP-Hard. ECCC 2020.
• Susanna F. de Rezende, Or Meir, Jakob Nördstrom, Toniann Pitassi, Robert Robere. KRW Composition Theorems via Lifting. Submitted to FOCS. arXiv:2007.02740v1, 2020.
• Meir, O., Nordstrom, J., Pitassi, T., Vinyals, M. Lifting with Simple Gadgets and Applications to Cutting Planes. Submitted to FOCS, 2020.
• Goos, M., Nordstrom, J., Pitassi, T., Robere, R., Sokolov, D. Automating Algebraic Proof Systems is NP-hard. Submitted to FOCS, 2020.
• Fleming, N., Goos, M., Imgagliazzo, R., Pitassi, T., Robere, R., and Tan, L. On Cutting Planes Proofs of Linear Equations. Submitted to RANDOM, 2020.
• Impagliazzo, R., Mouli, S., and Pitassi, T. The Surprising Power of Constant Depth Algebraic Proofs. LICS 2020, 591-603.
• Koroth, S., Goos, M., Mertz, I., and Pitassi, T. Automating Cutting Planes is NP-Hard. STOC 2020, 68-77.
• Pitassi, T., Shirley, M., and Watson, T. Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity. ICALP 2020.
• Li, C., Fleming, N., Vinyals, M., Pitassi, T., and Ganesh, V. Towards a Complexity-Theoretic Understanding of Restarts in SAT Solvers. SAT 2020.
• Fleming, N., Kothari, P., and Pitassi, T. Semialgebraic Proofs and Efficient Algorithm Design. Foundations and Trends in Theoretical Computer Science 2019, 14(1-2):1-221.
• Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, and Avi Wigderson. Towards a theory of non-commutative optimization: Geodesic 1^st and 2nd order methods for moment maps and polytopes. FOCS 2019, 845-861.
• Harm Derksen and Visu Makam. MLE for matrix models via quiver representations. In preparation, 2020.