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

Tomb Raider and the Quick Event of Time



Quick time events are generally shunned in the gaming population. And even people open to different concepts hate them. I want to argue for quick time events on the example of "Tomb Raider" (2013).

Quick time events have the unique position emulating an action without a special controller required. The greatest example is probably Heavy Rain. Every movement translates to joystick movement or other controller input. And the input makes sense. If you need to brush your teeth you push the stick up and down in unison with animation. Every QTE in Heavy Rain uses movement which maps almost isomorphic to the real event happening on the screen. And because of this isomorphism our brain can see the event as a tool [1] and not just a weird input method. And if our brain sees this action as a tool we are more likely to immerse our self in the world. ...more

April 28, 2015 [Games]

They Bleed Pixels - The Hardcore Casual Platformer



I was recently playing "They Bleed Pixels" which at the first glance is just another 2D hardcore platformer like "Super Meat Boy". However after some time I noticed that the execution is very different.

Super Meat Boy has the big problem that the length of the levels increases by a lot as you go on which can lead to a lot of frustration. One of the big reasons Super Meat Boy works and is so successful is that the reset time and repeat time is very short. Any time you die you are immediately back to the start. If you are stuck at a specific part of the level you don't need a long time to get back to it. These two things are the major differences between old school platformers and new school. Old school fights the players while new school wants the player to succeed. ...more

April 27, 2015 [Games]