Opendata, web and dolomites


Monotonicity in Logic and Complexity

Total Cost €


EC-Contrib. €






 MiLC project word cloud

Explore the words cloud of the MiLC project. It provides you a very rough idea of what is the project "MiLC" about.

detection    inclusion    reformulating    characterisations    monotonicity    feasible    purpose    calibrate    theoretic    functions    representable    structural    underlying    sorting    computed    tight    certain    eliminate    theories    proofs    class    view    logic    milc    employed    negation    propositional    correspondences    theory    polynomial    hierarchy    modular    proof    aci    point    handling    tools    arithmetic    deep    inference    bounds    witnessing    attack    bounded    logical    boolean    lens    formally    yielding    discovered    recursion    techniques    suited    respectively    inducing    setting    nci    complexity    witness    circuits    graphs    algorithms    nonuniform    machine    languages    calibrating    computation    usual    avenues    abound    switched    capture    extraction    represented    clique    arrive    off    restricting    independent    area    intuitionistic    building    monotone    classes    nonmonotone    reasoning    correspondence    invariants    rules    computational    exclusion   

Project "MiLC" data sheet

The following table provides information about the project.


Organization address
address: NORREGADE 10
postcode: 1165

contact info
title: n.a.
name: n.a.
surname: n.a.
function: n.a.
email: n.a.
telephone: n.a.
fax: n.a.

 Coordinator Country Denmark [DK]
 Project website
 Total cost 200˙194 €
 EC max contribution 200˙194 € (100%)
 Programme 1. H2020-EU.1.3.2. (Nurturing excellence by means of cross-border and cross-sector mobility)
 Code Call H2020-MSCA-IF-2016
 Funding Scheme MSCA-IF-EF-ST
 Starting year 2017
 Duration (year-month-day) from 2017-09-01   to  2019-08-31


Take a look of project's partnership.

# participants  country  role  EC contrib. [€] 
1    KOBENHAVNS UNIVERSITET DK (KOBENHAVN) coordinator 200˙194.00


 Project objective

MiLC will develop logical characterisations of monotone complexity classes, yielding languages and systems which are machine-independent and well suited for reasoning over such classes of functions. Monotone Boolean functions abound in the theory of computation, e.g. in sorting algorithms and clique detection in graphs, and nonuniform classes of monotone functions have been well studied in computational complexity under the lens of monotone circuits.

From the point of view of computation, monotone functions are computed by algorithms not using negation, and this will lead to several recursion-theoretic characterisations of feasible classes such as monotone P, NCi, ACi and the polynomial hierarchy. The main purpose of MiLC will be to capture these classes proof theoretically, by calibrating each class with the formally representable functions of a certain theory. MiLC will work in the setting of Bounded Arithmetic since its techniques are well suited to handling monotonicity, building on recently discovered correspondences with monotone proof complexity. To this end two avenues for controlling monotonicity will be investigated: (a) restricting negation in proofs, inducing monotone witnessing invariants, and (b) restricting structural rules of the underlying logic to eliminate the nonmonotone cases of witness extraction. The aim is to arrive at modular characterisations, where monotonicity of a represented class is switched on or off by the inclusion or exclusion, respectively, of certain structural rules.

Finally MiLC will calibrate these theories with well studied systems in proof complexity, namely monotone, intuitionistic and deep inference systems, under the usual correspondence between theories of Bounded Arithmetic and systems of propositional logic. These tight correspondences ensure that the tools developed in MiLC may be employed to attack certain open problems in the area, reformulating and improving existing bounds.


year authors and title journal last update
List of publications.
2019 Das, Anupam
From QBFs to MALL and back via focussing: fragments of multiplicative additive linear logic for each level of the polynomial hierarchy
published pages: , ISSN: , DOI:
1 2020-04-09
2019 Sam Buss, Anupam Das, Alexander Knop
Proof complexity of systems of (non-deterministic) decision trees and branching programs
published pages: , ISSN: , DOI:
2018 Anupam Das, Isabel Oitavem
A Recursion-Theoretic Characterisation of the Positive Polynomial-Time Functions
published pages: , ISSN: , DOI: 10.4230/lipics.csl.2018.18
27th EACSL Annual Conference on Computer Science Logic (CSL 2018) 2020-04-09
2018 Anupam Das, Amina Doumane, Damien Pous
Left-Handed Completeness for Kleene algebra, via Cyclic Proofs
published pages: 271-251, ISSN: , DOI: 10.29007/hzq3
EPiC Series in Computing volume 57 2020-04-09
2019 Das, Anupam
On the logical complexity of cyclic arithmetic
published pages: , ISSN: , DOI:
1 2020-04-09
2018 Anupam Das, Damien Pous
Non-Wellfounded Proof Theory For (Kleene+Action)(Algebras+Lattices)
published pages: 19:1--19:18, ISSN: , DOI: 10.4230/lipics.csl.2018.19
27th EACSL Annual Conference on Computer Science Logic (CSL 2018) 2020-04-09

Are you the coordinator (or a participant) of this project? Plaese send me more information about the "MILC" project.

For instance: the website url (it has not provided by EU-opendata yet), the logo, a more detailed description of the project (in plain text as a rtf file or a word file), some pictures (as picture files, not embedded into any word file), twitter account, linkedin page, etc.

Send me an  email ( and I put them in your project's page as son as possible.

Thanks. And then put a link of this page into your project's website.

The information about "MILC" are provided by the European Opendata Portal: CORDIS opendata.

More projects from the same programme (H2020-EU.1.3.2.)

RegARcis (2020)

Role of the SWI/SNF complex in the Androgen Receptor cistrome regulation

Read More  

MathematicsAnalogies (2019)

Mathematics Analogies

Read More  

MingleIFT (2020)

Multi-color and single-molecule fluorescence imaging of intraflagellar transport in the phasmid chemosensory cilia of C. Elegans

Read More