Seminár z teoretickej informatiky - Dana Pardubská (21.10.2016)

v piatok 21.10.2016 o 11:00 hod. v miestnosti M/213

18. 10. 2016 15.16 hod.
Od: Rastislav Královič

Prednášajúci: Dana Pardubská

Názov: Information Complexity Is Computable

Termín: 21.10.2016, 11:00 hod., M/213

Abstrakt:
Mark Braverman and Jon Schneider: Information Complexity Is Computable (ICALP 2016)

The information complexity of a function f is the minimum amount of information Alice and Bob need to exchange to compute the function f. In this paper an algorithm for approximating the information complexity of an arbitrary function f to within any additive error ε > 0 is given, thus resolving an open question as to whether information complexity is computable.

The process gives the first explicit upper bound on the rate of convergence of the information complexity of f when restricted to b-bit protocols to the (unrestricted) information complexity of f.

web: http://kedrigern.dcs.fmph.uniba.sk/STI2
rss: http://kedrigern.dcs.fmph.uniba.sk/STI2/rss.php