The Experts below are selected from a list of 1725 Experts worldwide ranked by ideXlab platform

Vladimir Nikishkin - One of the best experts on this subject based on the ideXlab platform.

  • amortized communication complexity of an Equality Predicate
    Computer Science Symposium in Russia, 2013
    Co-Authors: Vladimir Nikishkin
    Abstract:

    We study the communication complexity of the direct sum of independent copies of the Equality Predicate. We prove that the probabilistic communication complexity of this problem is equal to O(N); the computational complexity of the proposed protocol is polynomial in the size of inputs. Our protocol improves the result achieved in 1991 by Feder et al. Our construction is based on two techniques: Nisan’s pseudorandom generator (1992, Nisan) and Smith’s string synchronization algorithm (2007, Smith).

  • Amortized communication complexity of an Equality Predicate
    arXiv: Computational Complexity, 2012
    Co-Authors: Vladimir Nikishkin
    Abstract:

    We study the communication complexity of a direct sum of independent copies of the Equality Predicate. We prove that the probabilistic communication complexity of this problem is equal to O(N); computational complexity of the proposed protocol is polynomial in size of inputs. Our protocol improves the result achieved in 1995(Feder, Kushilevitz, Naor, Nisan). Our construction is based on two techniques: Nisan's pseudorandom generator (1992) and Smith's string synchronization algorithm (2007).

  • Amortized communication complexity of an Equality Predicate. (Beta version)
    2012
    Co-Authors: Vladimir Nikishkin
    Abstract:

    We study the communication complexity of a direct sum of independent copies of the Equality Predicate. We prove that the probabilistic communication complexity of this problem is equal to O(N); computational complexity of the proposed protocol is polynomial in size of inputs. Our protocol improves the result achieved in 1995(Feder, Kushilevitz, Naor, Nisan). Our construction is based on two techniques: Nisan's pseudorandom generator (1992) and Smith's string synchronization algorithm (2007).

Hoeteck Wee - One of the best experts on this subject based on the ideXlab platform.

  • On the Inner Product Predicate and a Generalization of Matching Vector Families
    arXiv: Computational Complexity, 2018
    Co-Authors: Balthazar Bauer, Jevgēnijs Vihrovs, Hoeteck Wee
    Abstract:

    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. Concretely, fix a Boolean function $P$ and some modulus $q$. We are interested in encoding $x$ to $\vec x$ and $y$ to $\vec y$ so that $$P(x,y) = 1 \Longleftrightarrow \langle\vec x,\vec y\rangle= 0 \bmod q,$$ where the vectors should be as short as possible. This problem can also be viewed as a generalization of matching vector families, which corresponds to the Equality Predicate. Matching vector families have been used in the constructions of Ramsey graphs, private information retrieval (PIR) protocols, and more recently, secret sharing. Our main result is a simple lower bound that allows us to show that known encodings for many Predicates considered in the cryptographic literature such as greater than and threshold are essentially optimal for prime modulus $q$. Using this approach, we also prove lower bounds on encodings for composite $q$, and then show tight upper bounds for such Predicates as greater than, index and disjointness.

Balthazar Bauer - One of the best experts on this subject based on the ideXlab platform.

  • On the Inner Product Predicate and a Generalization of Matching Vector Families
    arXiv: Computational Complexity, 2018
    Co-Authors: Balthazar Bauer, Jevgēnijs Vihrovs, Hoeteck Wee
    Abstract:

    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. Concretely, fix a Boolean function $P$ and some modulus $q$. We are interested in encoding $x$ to $\vec x$ and $y$ to $\vec y$ so that $$P(x,y) = 1 \Longleftrightarrow \langle\vec x,\vec y\rangle= 0 \bmod q,$$ where the vectors should be as short as possible. This problem can also be viewed as a generalization of matching vector families, which corresponds to the Equality Predicate. Matching vector families have been used in the constructions of Ramsey graphs, private information retrieval (PIR) protocols, and more recently, secret sharing. Our main result is a simple lower bound that allows us to show that known encodings for many Predicates considered in the cryptographic literature such as greater than and threshold are essentially optimal for prime modulus $q$. Using this approach, we also prove lower bounds on encodings for composite $q$, and then show tight upper bounds for such Predicates as greater than, index and disjointness.

Jevgēnijs Vihrovs - One of the best experts on this subject based on the ideXlab platform.

  • On the Inner Product Predicate and a Generalization of Matching Vector Families
    arXiv: Computational Complexity, 2018
    Co-Authors: Balthazar Bauer, Jevgēnijs Vihrovs, Hoeteck Wee
    Abstract:

    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. Concretely, fix a Boolean function $P$ and some modulus $q$. We are interested in encoding $x$ to $\vec x$ and $y$ to $\vec y$ so that $$P(x,y) = 1 \Longleftrightarrow \langle\vec x,\vec y\rangle= 0 \bmod q,$$ where the vectors should be as short as possible. This problem can also be viewed as a generalization of matching vector families, which corresponds to the Equality Predicate. Matching vector families have been used in the constructions of Ramsey graphs, private information retrieval (PIR) protocols, and more recently, secret sharing. Our main result is a simple lower bound that allows us to show that known encodings for many Predicates considered in the cryptographic literature such as greater than and threshold are essentially optimal for prime modulus $q$. Using this approach, we also prove lower bounds on encodings for composite $q$, and then show tight upper bounds for such Predicates as greater than, index and disjointness.

James Worrell - One of the best experts on this subject based on the ideXlab platform.

  • Nets with tokens which carry data
    2016
    Co-Authors: Tom Newcomb, A. W. Roscoe, James Worrell
    Abstract:

    Abstract. We study data nets, a generalisation of Petri nets in which tokens carry data from linearly-ordered innite domains and in which whole-place operations such as resets and transfers are possible. Data nets subsume several known classes of innite-state systems, including multiset rewriting systems and polymorphic systems with arrays. We show that coverability and termination are decidable for arbitrary data nets, and that boundedness is decidable for data nets in which whole-place operations are restricted to transfers. By providing an en-coding of lossy channel systems into data nets without whole-place oper-ations, we establish that coverability, termination and boundedness for the latter class have non-primitive recursive complexity. The main result of the paper is that, even for unordered data domains (i.e., with only the Equality Predicate), each of the three verication problems for data nets without whole-place operations has non-elementary complexity.

  • IOS Press Nets with tokens which carry data
    2012
    Co-Authors: Ranko Lazić C, Tom Newcomb, A. W. Roscoe, Joël Ouaknine, James Worrell
    Abstract:

    Abstract. We study data nets, a generalisation of Petri nets in which tokens carry data from linearlyordered infinite domains and in which whole-place operations such as resets and transfers are possible. Data nets subsume several known classes of infinite-state systems, including multiset rewriting systems and polymorphic systems with arrays. We show that coverability and termination are decidable for arbitrary data nets, and that boundedness is decidable for data nets in which whole-place operations are restricted to transfers. By providing an encoding of lossy channel systems into data nets without whole-place operations, we establish that coverability, termination and boundedness for the latter class have non-primitive recursive complexity. The main result of the paper is that, even for unordered data domains (i.e., with only the Equality Predicate), each of the three verification problems for data nets without whole-place operations has non-elementary complexity. Keywords: Petri nets, infinite-state systems, program verification, computational complexit