Derandomizing Polynomial Identity Testing and the Isolation Lemma

• Applicant: Professor Dr. Thomas Thierauf
• Subject Area: Theoretical Computer Science
• Term: from 2010 to 2019
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 167224914

• Final Report Year: 2019

Final Report Abstract

The most spectacular result we got is certainly the parallel algorithm for bipartite perfect matching. This is considered a breakthrough result. It solves a problem that was open for more than 30 years. It prepared the ground for a lot of further results. Derandomizing the Isolation Lemma was the very ambitious title of the project. This is the technique behind our perfect matching algorithm. Maybe nobody really expected that we get so close to this goal. We considerably generalized the perfect matching result in two subsequent papers. In the first step, we showed a similar result for the matroid intersection problem, where bipartite perfect matching is a special case of. The second step was even larger: we extended the isolation approach to all problems that can be described by polytopes with totally unimodular faces. This includes matroid intersection and bipartite perfect matching as very special cases. Moreover, a lot of combinatorial problems fall into this category. The above results should not overshadow the other work that was done in the project. Another highlight was the equivalence test for read-once oblivious arithmetic branching programs. We derandomized the probabilistic algorithm for this problem. We constructed a polynomial-time algorithm in the white-box setting, and even more surprisingly, a quasipolynomial-time algorithm in the black-box setting. This was an open problem for several years. In summary, the cooperation with IIT Kanpur was very fruitful. Many exchanges of visits lead to strong collaborations.

Publications

• A Kolmogorov complexity proof of the Lovász Local Lemma for satisfiability. Theoretical Compututer Science 461: 55-64 (2012)
  Jochen Messner, Thomas Thierauf
  
• Reachability in K3,3-free and K5-free Graphs is in Unambiguous Logspace. Chicago Journal of Theoretical Compututer Science 2014 (2014)
  Thomas Thierauf, Fabian Wagner
  
• Bipartite perfect matching is in quasi-NC. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC) 2016: 754-763
  Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf
  
• Counting the Number of Perfect Matchings in K5 -Free Graphs. Theory of Computing Systems 59(3): 416-439 (2016)
  Simon Straub, Thomas Thierauf, Fabian Wagner
  
• Planarizing Gadgets for Perfect Matching Do Not Exist. ACM Transactions on Computation Theory (TOCT) 8(4): 14:1-14:15 (2016)
  Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf
  
• Deterministic Identity Testing for Sum of Read-Once Oblivious Arithmetic Branching Programs. Computational Complexity 26(4): 835-880 (2017)
  Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf
  
• Exact Perfect Matching in Complete Graphs. ACM Transactions on Computation Theory (TOCT) 9(2): 8:1-8:20 (2017)
  Rohit Gurjar, Arpita Korwar, Jochen Messner, Thomas Thierauf
  
• Linear matroid intersection is in quasi-NC. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC) 2017: 821-830
  Rohit Gurjar, Thomas Thierauf
  
• Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces. In 45th International Colloquium on Automata, Languages, and Programming (ICALP) 2018: 74:1-74:14
  Rohit Gurjar, Thomas Thierauf, Nisheeth K. Vishnoi
  
• A deterministic parallel algorithm for bipartite perfect matching. Communications of the ACM 62(3): 109-115 (2019)
  Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf