National
Institute of Informatics, Tokyo, Japan
An Optimal Algorithm for Certifying Monotone Functions
2022-04-04 Gupta, Manoj - An Optimal Algorithm for Certifying Monotone Functions paper Result Query Access to Monotone function of some certifying co… ...more
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.
-
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
-
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.
Recent Publications
Some publications have preprints available on ECCC or ArXiV.Conferences
Journals
Posts
Small Circuits Imply Efficient Arthur-Merlin Protocols
2021-08-30-DM-Small Circuits Imply Efficient Arthur-Merlin Protocols paper Result Setup Small Boolean Circuits $<x,y> = \sum_i x_i y_i \mod 2$ … ...more
Smaller ACC0 Circuits for Symmetric Functions
2021-07-09-CW-Smaller ACC0 Circuits for Symmetric Functions paper Results Theorem 1.1: For every $\epsilon$ and $m<(1/3)^{2/\epsilon}$ such that e… ...more