"NP-Hardness of Circuit Minimization for Multi-Output Functions"

No próximo dia 28 de outubro, pelas 14h30, Bruno Loff, docente do DCC-FCUP, irá dar uma palestra intitulada "NP-Hardness of Circuit Minimization for Multi-Output Functions"


A palestra é organizada pelo DCC-FCUP e pelo grupo de investigação CRACS-INESC TEC e é aberta a todos os interessados.


A sessão será de forma remota, utilizando os seguintes dados:


- Meeting id: 897 4115 2950
- Password: 516503

Short Bio:
Bruno Loff did his PhD under the supervision of Harry Buhrman, at the center for mathematics and informatics (CWI), in Amsterdam, and he has worked as a postdoc at the Charles University in Prague, and at the University of Porto. His main research interest is computational complexity, and has spent the last several years attempting to prove unconditional impossibility results, also known as lower-bounds, mainly in the area of data structures and communication complexity, which is one of the few areas where we know how to prove such results.
NP-Hardness of Circuit Minimization for Multi-Output Functions
In recent years there has been a surge of interest in a topic which could be called "meta-complexity", or "computational complexity of computational complexity". Namely, we are interested in understanding the computational complexity of tasks as follows:

* Given the truth-table of a Boolean function f, what is the size of the smallest DNF for f? What is the size of the smallest Boolean circuit for f? The smallest two-player communication protocol? etc

The central open-problem in the area is the so-called MCSP problem, which asks, when given as input the truth-table of a Boolean function with a single output-bit f:{0,1}ⁿ → {0,1}, to compute, or at least approximate SIZE(f), the size of the smallest Boolean AND/OR/NOT circuit for computing f. The most important conjecture in the area is that the MCSP problem is NP-hard, but there is a general belief that we are very far from proving this conjecture.

However, in this work we show that if the input is instead the truth-table of a Boolean function with multiple output bits F:{0,1}ⁿ → {0,1}ᵐ, then the problem of computing SIZE(F) is, indeed, NP-hard.

In the talk we will outline the work that has been done in the area, and briefly sketch some ideas in the proof of our result.
This is joint work with Rahul Ilango (MIT) and Igor Oliveira (Warwick), and was presented at CCC 2020. A pre-print is available at https://eccc.weizmann.ac.il/report/2020/021/.



Também lhe pode interessar


"Randomness Beacons for Enhanced Public Auditability"

René Peralta and Luís Brandão dão palestra no DCC


"Ramanujan graphs: Theory and Applications"

Pedro Paredes dá palestra no DCC


"Cognitive Packet Networks Adaptively Defend Against Cyber-Attacks"

Prof. Erol Gelenbe dá palestra no DCC