National Institute of Informatics, Tokyo, Japan

Biography

I am a PostDoc at the National Institute of Informatics, Tokyo. I am interested in almost everything TCS/ Computational Complexity related but my focus is on arithmetic circuit complexity. You can find a list of my current publications in my DBLP or Google Scholar. A more selected view with abstracts can be found on this homepage under Publication. Apart from my main interest in Computational Complexity, I also have many other interest such as programming (as you can see from my github), machine learning,Video Game Making and Music Production. You can find my Academic CV and my software focused CV. I sometimes write posts on either TCS or Games Mechanics.

Selected Projects

• Toukakoukan A way to split bills by automatically calculating who how much. Uses rust, svelte, daisyui, tailwindcss, typescript, javascript and is a PWA.
• Musicbrainz Release Grabber Grabs new release from the musicbrainz database. Parses directory names, finds the corresponding UUID and checks for new releases using the XML api. Using Rust.
• TheoryGrabber Fetch various TCS papers from ECCC and arxiv, downloads them puts them in a folder. Using Rust.
• SerieViewer A simple interface in Qt to show shows and remember which episode I am in. Simple to start the next episode with one button press if available.
• Viola A music player written in Rust with a frontend of GTK. It supports playlists, smart playlists, library view and much more. Over time, I moved the frontend to React, Typescript with the backend in Rust. Recently, Changed the frontend to Rust with seed-rs, yew and Web Assembly.

Recent Publications

Some publications have preprints available on ECCC or ArXiV.

Conferences

• 2022 - Sankardeep Chakraborty and Christian Engels - Lower Bounds for Lexicographical {DFS} Data Structures - Data Compression Conference, {DCC} 2022, Snowbird, UT, USA, March 22-25, 2022
• 2019 - Markus Bl{\"a}ser and Christian Engels - Parameterized Valiant's Classes - 14th International Symposium on Parameterized and Exact Computation, {IPEC} 2019, September 11-13, 2019, Munich, Germany
• 2018 - Suryajith Chillara and Christian Engels and Nutan Limaye - A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits - 59th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS} 2018, Paris, France, October 7-9, 2018
• 2017 - Christian Engels and B. V. Raghavendra Rao and Karteek, Sreenivasaiah - On {\textbackslash}varSigma {\textbackslash}wedge {\textbackslash}varSigma {\textbackslash}wedge {\textbackslash}varSigma Circuits: The Role of Middle {\textbackslash}varSigma Fan-In, Homogeneity and Bottom Degree - Fundamentals of Computation Theory - 21st International Symposium, {FCT} 2017, Bordeaux, France, September 11-13, 2017, Proceedings
• 2016 - Christian Engels and B. V. Raghavendra Rao - On Hard Instances of Non-Commutative Permanent - Computing and Combinatorics - 22nd International Conference, {COCOON} 2016, Ho Chi Minh City, Vietnam, August 2-4, 2016, Proceedings
• 2015 - Christian Engels - Dichotomy Theorems for Homomorphism Polynomials of Graph Classes - {WALCOM:} Algorithms and Computation - 9th International Workshop, {WALCOM} 2015, Dhaka, Bangladesh, February 26-28, 2015. Proceedings
• 2013 - Karl Bringmann and Christian Engels and Bodo Manthey and B. V. Raghavendra Rao - Random Shortest Paths: Non-euclidean Instances for Metric Optimization Problems - Mathematical Foundations of Computer Science 2013 - 38th International Symposium, {MFCS} 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings
• 2012 - Christian Engels and Bodo Manthey and B. V. Raghavendra Rao - Random Shortest Path Metrics with Applications - 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, Munich, Germany, May 29-31, 2012. Extended Abstracts
• 2011 - Markus Bl{\"a}ser and Christian Engels - Randomness Efficient Testing of Sparse Black Box Identities of Unbounded Degree over the Reals - 28th International Symposium on Theoretical Aspects of Computer Science, {STACS} 2011, March 10-12, 2011, Dortmund, Germany

Journals

• 2020 - Christian Engels and Mohit Garg and Kazuhisa Makino and Anup Rao - On Expressing Majority as a Majority of Majorities - {SIAM} J. Discret. Math.
• 2020 - Christian Engels and B. V. Raghavendra Rao - On hard instances of non-commutative permanent - Discret. Appl. Math.
• 2016 - Christian Engels - Dichotomy Theorems for Homomorphism Polynomials of Graph Classes - J. Graph Algorithms Appl.
• 2015 - Karl Bringmann and Christian Engels and Bodo Manthey and B. V. Raghavendra Rao - Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems - Algorithmica
• 2009 - Christian Engels and Bodo Manthey - Average-case approximation ratio of the 2-opt algorithm for the {TSP} - Oper. Res. Lett.

Posts

Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error

2021-07-25-MD-Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error paper Results I am only going to co… ...more

November 16, 2021 [TCS, Communication Complexity]

Keep that card in mind

2021-07-08-MN-Keep That Card in Mind: Card Guessing with Limited Memory.pdf paper Results Setup A Dealer deals cards via some strategy from a set of … ...more

November 11, 2021 [TCS, Data Structures]

Montone Complexity of Spanning Tree Polynomial Re-visited

2021-09-14-CDGM-Monotone Complexity of Spanning Tree Polynomial Re-visited paper Results Spanning Tree polynomial is in VP Has monotone circuit compl… ...more

November 10, 2021 [TCS, Arithmetic Circuits]