More Like this

1. A Bit More Than a Bit Is More Than a Bit Better

   https://doi.org/10.2478/popets-2019-0061  

   Hafiz, Syed Mahbub; Henry, Ryan (October 2019, Proceedings on Privacy Enhancing Technologies)

   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
2. Bit-GraphBLAS: Bit-Level Optimizations of Matrix-Centric Graph Processing on GPU

   https://doi.org/10.1109/IPDPS53621.2022.00056  

   Chen, Jou-An; Sung, Hsin-Hsuan; Shen, Xipeng; Tallent, Nathan; Barker, Kevin; Li, Ang (May 2022, 36th IEEE International Parallel & Distributed Processing Symposium)
3. Bit Fusion: Bit-Level Dynamically Composable Architecture for Accelerating Deep Neural Network

   https://doi.org/10.1109/ISCA.2018.00069  

   Sharma, Hardik; Park, Jongse; Suda, Naveen; Lai, Liangzhen; Chau, Benson; Chandra, Vikas; Esmaeilzadeh, Hadi (June 2018, ISCA)
4. One-bit digital radar

   https://doi.org/10.1109/ACSSC.2017.8335529  

   Ren, Jiaying; Li, Jian (October 2017, Signals, Systems, and Computers, 2017 51st Asilomar Conference on)

   This paper introduces a one-bit digital radar involving direct one-bit sampling with unknown dithering of the received radio frequency (RF) signal. Due to avoiding the analog mixer and the down-conversion of the RF signal, the digital radar can be energy-efficient and low-priced. The use of unknown dithering allows for the one-bit samples to be processed efficiently using conventional algorithms. A computationally efficient range-Doppler estimation method based on fractional Fourier transform (FRFT) and fast Fourier transform (FFT) is used for linear frequency modulated continuous wave (LFMCW) transmissions, and the CLEAN algorithm is used for target parameter estimation. 

   more » « less
5. Bit Blasting Probabilistic Programs

   https://doi.org/10.1145/3656412  

   Garg, Poorva; Holtzen, Steven; Van_den_Broeck, Guy; Millstein, Todd (June 2024, Proceedings of the ACM on Programming Languages)

   Probabilistic programming languages (PPLs) are an expressive means for creating and reasoning about probabilistic models. Unfortunatelyhybridprobabilistic programs that involve both continuous and discrete structures are not well supported by today’s PPLs. In this paper we develop a new approximate inference algorithm for hybrid probabilistic programs that first discretizes the continuous distributions and then performs discrete inference on the resulting program. The key novelty is a form of discretization that we callbit blasting, which uses a binary representation of numbers such that a domain of $2^b$discretized points can be succinctly represented as a discrete probabilistic program overpoly $\left(b\right)$Boolean random variables. Surprisingly, we prove that many common continuous distributions can be bit blasted in a manner that incurs no loss of accuracy over an explicit discretization and supports efficient probabilistic inference. We have built a probabilistic programming system for hybrid programs calledHyBit, which employs bit blasting followed by discrete probabilistic inference. We empirically demonstrate the benefits of our approach over existing sampling-based and symbolic inference approaches 

   more » « less