---
res:
bibo_abstract:
- In this paper, we investigate the computational complexity of quantitative information
flow (QIF) problems. Information-theoretic quantitative relaxations of noninterference
(based on Shannon entropy)have been introduced to enable more fine-grained reasoning
about programs in situations where limited information flow is acceptable. The
QIF bounding problem asks whether the information flow in a given program is bounded
by a constant $d$. Our first result is that the QIF bounding problem is PSPACE-complete.
The QIF memoryless synthesis problem asks whether it is possible to resolve nondeterministic
choices in a given partial program in such a way that in the resulting deterministic
program, the quantitative information flow is bounded by a given constant $d$.
Our second result is that the QIF memoryless synthesis problem is also EXPTIME-complete.
The QIF memoryless synthesis problem generalizes to QIF general synthesis problem
which does not impose the memoryless requirement (that is, by allowing the synthesized
program to have more variables then the original partial program). Our third result
is that the QIF general synthesis problem is EXPTIME-hard.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Pavol
foaf_name: Cerny, Pavol
foaf_surname: Cerny
foaf_workInfoHomepage: http://www.librecat.org/personId=4DCBEFFE-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Krishnendu
foaf_name: Chatterjee, Krishnendu
foaf_surname: Chatterjee
foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-4561-241X
- foaf_Person:
foaf_givenName: Thomas A
foaf_name: Henzinger, Thomas A
foaf_surname: Henzinger
foaf_workInfoHomepage: http://www.librecat.org/personId=40876CD8-F248-11E8-B48F-1D18A9856A87
orcid: 0000−0002−2985−7724
bibo_doi: 10.1109/CSF.2011.21
dct_date: 2011^xs_gYear
dct_language: eng
dct_publisher: IEEE@
dct_title: The complexity of quantitative information flow problems@
...