Derandomisierung von Polynom Identitätstests und dem Isolation Lemma

• Antragsteller: Professor Dr. Thomas Thierauf
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2010 bis 2019
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 167224914

• Erstellungsjahr: 2019

Zusammenfassung der Projektergebnisse

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.

Projektbezogene Publikationen (Auswahl)

• A Kolmogorov complexity proof of the Lovász Local Lemma for satisfiability. Theoretical Compututer Science 461: 55-64 (2012)
  Messner, Jochen & Thierauf, Thomas
  
• Reachability in K3,3-free and K5-free Graphs is in Unambiguous Logspace. Chicago Journal of Theoretical Compututer Science 2014 (2014)
  Thierauf, Thomas & Wagner, Fabian
  
• Counting the Number of Perfect Matchings in K5 -Free Graphs. Theory of Computing Systems 59(3): 416-439 (2016)
  Straub, Simon; Thierauf, Thomas & Wagner, Fabian
  
• Bipartite perfect matching is in quasi-NC. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC) 2016: 754-763
  Fenner, Stephen; Gurjar, Rohit & Thierauf, Thomas
  
• Deterministic Identity Testing for Sum of Read-Once Oblivious Arithmetic Branching Programs. Computational Complexity 26(4): 835-880 (2017)
  Gurjar, Rohit; Korwar, Arpita; Saxena, Nitin & Thierauf, Thomas
  
• Planarizing Gadgets for Perfect Matching Do Not Exist. ACM Transactions on Computation Theory (TOCT) 8(4): 14:1-14:15 (2016)
  Gurjar, Rohit; Korwar, Arpita; Messner, Jochen; Straub, Simon & Thierauf, Thomas
  
• Exact Perfect Matching in Complete Graphs. ACM Transactions on Computation Theory (TOCT) 9(2): 8:1-8:20 (2017)
  Gurjar, Rohit; Korwar, Arpita; Messner, Jochen & Thierauf, Thomas
  
• Linear matroid intersection is in quasi-NC. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC) 2017: 821-830
  Gurjar, Rohit & Thierauf, Thomas
  
• 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)
  Fenner, Stephen; Gurjar, Rohit & Thierauf, Thomas