Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic
- Submitting institution
-
King's College London
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 136476450
- Type
- D - Journal article
- DOI
-
10.1137/15M1027267
- Title of journal
- SIAM JOURNAL ON COMPUTING
- Article number
- -
- First page
- 456
- Volume
- 47
- Issue
- 2
- ISSN
- 0097-5397
- Open access status
- Technical exception
- Month of publication
- April
- Year of publication
- 2018
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
1
- Research group(s)
-
-
- Citation count
- 3
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This work, which appeared in preliminary form at LICS2014, investigates one of the most significant and elusive problems in computer science, the hypergraph duality problem (DUAL), whose complexity has been open for around 40 years, and which is at the base of many applications, e.g., in machine learning and computational biology. This work proves the lowest complexity upper-bound on DUAL currently known. Descriptive complexity theory and computational logics were adopted for the first time in the literature on DUAL to obtain the new result. This result was also presented in an invited talk at Samsung AI Center Cambridge.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -