BIT predicate

From Wikipedia, the free encyclopedia

In mathematics and computer science, the BIT predicate, sometimes written BIT(i, j), is a predicate which tests whether the jth bit of the number i is 1, when i is written in binary.

Implementation

In programming languages such as C, C++, Java, or Python that provide a right shift operator >> and a bitwise Boolean and operator &, the BIT predicate BIT(i, j) can be implemented by the expression (i>>j)&1. Here the bits of i are numbered from the low order bits to high order bits in the binary representation of i, with the ones bit being numbered as bit 0.[1]

Private information retrieval

In the mathematical study of computer security, the private information retrieval problem can be modeled as one in which a client, communicating with a collection of servers that store a binary number i, wishes to determine the result of a BIT predicate BIT(i, j) without divulging the value of j to the servers. Chor et al. (1998) describe a method for replicating i across two servers in such a way that the client can solve the private information retrieval problem using a substantially smaller amount of communication than would be necessary to recover the complete value of i.[2]

Mathematical logic

The BIT predicate is often examined in the context of first-order logic, where we can examine the system resulting from adding the BIT predicate to first-order logic. In descriptive complexity, the complexity class FO + BIT resulting from adding the BIT predicate to FO results in a more robust complexity class.[3] The class FO + BIT, of first-order logic with the BIT predicate, is the same as the class FO + PLUS + TIMES, of first-order logic with addition and multiplication predicates.[4]

Construction of the Rado graph

Richard Rado used this predicate in 1964 to construct the infinite Rado graph. In Rado's construction, the vertices of this graph correspond to the non-negative integers, written in binary, and there is an undirected edge from vertex i to vertex j, for i < j, when BIT(j,i) is nonzero.[5]

References

  1. ↑ Venugopal, K. R. (1997). Mastering C++. Muhammadali Shaduli. p. 123. ISBN 9780074634547. .
  2. ↑ Chor, Benny; Kushilevitz, Eyal; Goldreich, Oded; Sudan, Madhu (1998). "Private information retrieval". Journal of the ACM 45 (6): 965–981. doi:10.1145/293347.293350. .
  3. ↑ Immerman, Neil (1999). Descriptive Complexity. New York: Springer-Verlag. ISBN 0-387-98600-6. 
  4. ↑ Immerman, Neil (1999). Descriptive Complexity. New York: Springer-Verlag. pp. 14–16. ISBN 0-387-98600-6. 
  5. ↑ Rado, Richard (1964). "Universal graphs and universal functions". Acta Arith. 9: 331–340. .
This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.