Opendata, web and dolomites

MiLC SIGNED

Monotonicity in Logic and Complexity

Total Cost €

0

EC-Contrib. €

0

Partnership

0

Views

0

 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.

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

Project "MiLC" data sheet

The following table provides information about the project.

Coordinator
KOBENHAVNS UNIVERSITET 

Organization address
address: NORREGADE 10
city: KOBENHAVN
postcode: 1165
website: www.ku.dk

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 http://www.anupamdas.com/wp/milc
 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

 Partnership

Take a look of project's partnership.

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

Map

 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.

 Publications

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:
2020-04-09
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 (fabio@fabiodisconzi.com) 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.)

TheaTheor (2018)

Theorizing the Production of 'Comedia Nueva': The Process of Play Configuration in Spanish Golden Age Theater

Read More  

GENI (2019)

Gender, emotions and national identities: a new perspective on the abortion debates in Italy (1971-1981).

Read More  

ICL CHROM (2020)

DNA interstrand crosslink repair and chromatin remodelling

Read More