10 citations · 12 across the 5 of their papers we have counts for
5 papers · 1 filter
Boolean Functions with Minimal Spectral Sensitivity
Krišjānis Prūsis, Jevgēnijs Vihrovs
We show examples of total Boolean functions that depend on variables and have spectral sensitivity , which is asymptotically minimal. Our main new function co…
On the Inner Product Predicate and a Generalization of Matching Vector Families
Balthazar Bauer, Jevgēnijs Vihrovs, Hoeteck Wee
Motivated by cryptographic applications such as predicate encryption, we consider the problem of representing an arbitrary predicate as the inner product predicate on two vectors.…
On Block Sensitivity and Fractional Block Sensitivity
Andris Ambainis, Krišjānis Prūsis, Jevgēnijs Vihrovs
We investigate the relation between the block sensitivity and fractional block sensitivity complexity measures of Boolean functions. While it is know…
Quadratically Tight Relations for Randomized Query Complexity
Dmitry Gavinsky, Rahul Jain, Hartmut Klauck +5
Let be a Boolean function. The certificate complexity is a complexity measure that is quadratically tight for the zero-error randomized que…
Sensitivity versus Certificate Complexity of Boolean Functions
Andris Ambainis, Krišjānis Prūsis, Jevgēnijs Vihrovs
Sensitivity, block sensitivity and certificate complexity are basic complexity measures of Boolean functions. The famous sensitivity conjecture claims that sensitivity is polynomia…