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.

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

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  

DNANanoProbes (2019)

Design of light-harvesting DNA-nanoprobes with ratiometric signal amplification for fluorescence imaging of live cells.

Read More  

PmNC (2019)

Policy-making of early nature conservation. The Netherlands and the United Kingdom compared, 1930-1960

Read More