skip to main content

Title: Bit-Stream Processing with No Bit-Stream: Efficient Software Simulation of Stochastic Vision Machines
Award ID(s):
2127780 2019511
Author(s) / Creator(s):
; ; ;
Date Published:
Journal Name:
Proceedings of the Great Lakes Symposium on VLSI
Page Range / eLocation ID:
273 to 279
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Few studies have explored the complex circuit simulation of stochastic and unary computing systems, which are referred to under the umbrella term of bit-stream processing. The computer simulation of multi-level cascaded circuits with reconvergent paths has not been largely examined in the context of bit-stream processing systems. This study addresses this gap and proposes a contingency table-based reconvergent path-aware simulation method for fast and efficient simulation of multi-level circuits. The proposed method exhibits significantly better runtime and accuracy. 
    more » « less
  2. Abstract We study both the practical and theoretical efficiency of private information retrieval (PIR) protocols in a model wherein several untrusted servers work to obliviously service remote clients’ requests for data and yet no pair of servers colludes in a bid to violate said obliviousness. In exchange for such a strong security assumption, we obtain new PIR protocols exhibiting remarkable efficiency with respect to every cost metric—download, upload, computation, and round complexity—typically considered in the PIR literature. The new constructions extend a multiserver PIR protocol of Shah, Rashmi, and Ramchandran (ISIT 2014), which exhibits a remarkable property of its own: to fetch a b -bit record from a collection of r such records, the client need only download b + 1 bits total. We find that allowing “a bit more” download (and optionally introducing computational assumptions) yields a family of protocols offering very attractive trade-offs. In addition to Shah et al.’s protocol, this family includes as special cases (2-server instances of) the seminal protocol of Chor, Goldreich, Kushilevitz, and Sudan (FOCS 1995) and the recent DPF-based protocol of Boyle, Gilboa, and Ishai (CCS 2016). An implicit “folklore” axiom that dogmatically permeates the research literature on multiserver PIR posits that the latter protocols are the “most efficient” protocols possible in the perfectly and computationally private settings, respectively. Yet our findings soundly refute this supposed axiom: These special cases are (by far) the least performant representatives of our family, with essentially all other parameter settings yielding instances that are significantly faster. 
    more » « less