DIKU Bits: Monotonicity in Logic and Complexity

Speaker

Anupam Das, postdoc

Abstract

Monotonicity is a fundamental notion in mathematics and computation. For usual real-valued functions R → R this simply corresponds to the notion that a function is increasing (or decreasing) in its argument, however this can be parametrised by any partially ordered domain and codomain we wish. In computation we deal with programs that compute Boolean functions, {0,1}* → {0,1}*. Restricting to increasing functions over this structure can be seen as prohibiting the use of negation in a program; for instance monotone Boolean functions are computed by Boolean circuits without NOT gates. The idea of restricting negation scales to other models of computation, and for some important classes of functions the formulation is naturally robust, not depending on the particular model at hand, e.g. for the polynomial-time functions. Monotone computational problems abound in practice, e.g. sorting a string and detecting cliques in graphs, and ‘nonuniform’ monotone models of computation, such as monotone circuits, have been fundamental objects of study in computational complexity for decades.

In this talk I will propose a project that develops *logical* characterisations of monotone complexity classes. Namely, the project will identify proof systems whose representable functions coincide with certain monotone classes, and also develop fundamental recursion-theoretic programming languages in which to extract the monotone functions themselves. In particular the project focusses on the role of structural rules in proof theory, i.e. the duplication and erasure of formulae, for controlling monotonicity.

This talk is based on an ongoing Marie Skłodowska-Curie project: http://www.anupamdas.com/wp/milc/

Zooming in on Anupam Das

Which courses do you teach?
At the moment, none unfortunately – I just arrived as a new postdoc. Still I’m always looking for passionate undergraduates to take on as interns!

Which technology/research/projects/startup are you excited to see the evolution of?
I want researchers and academics not to react to the latest trend, looking only 10 years ahead at a time (I’m looking at you, big data and machine learning!). However, one ‘buzzword’ that I do think has the potential, in the long term, to change all aspects of our lives is quantum computation. While still many years away from a quantum revolution (they recently factorised 27!), if this takes off then we might look at the 21st century as a time of relatively primitive technology. What is amazing about the area at large is how it extends from deep theoretical advances all the way to engineering, and there is a big chunk of computer science in the middle.

What is your favorite sketch from the DIKUrevy?
I didn’t know about DIKUrevy! But I just had a look on the interwebs and liked the ‘how compilers are made’ sketch. Looks like I have some more procrastination material now…

DIKU Bits: A lecture series at DIKU

In this lecture series you can get a closer look at the research conducted at DIKU, be motivated you to follow your interest in computer science and be inspired when choosing a subject for your bachelors project. The lectures are addressed to DIKU bachelor students – however, everyone is welcome.
Find more information about DIKU Bits in Danish / in English.