Sampling in Space Restricted Settings in COCOON 2015 (with Davis Issac, Ragesh Jaiswal and Amit Kumar)
Full version appeared in Algorithmica (COCOON special issue) Slides(PPTX)
Summary: We consider the random sampling problem in the streaming setting. The algorithm returns, at any time t, an item chosen uniformly at random from all items seen till time t. Our model allows storage for only one item at a time in the stream. We design an algorithm that takes O(log n) random bits and O(log n) space to maintain a random sample at all times. Our algorithm in the streaming setting matches the lower bound on the amount of required randomness for uniform sampling in the offline setting. We also extend the work on sampling in the query model by Bringmann and Larsen (STOC 2013) to the approximate setting and obtain almost matching upper and lower bounds for the problem.
SIMD-based Implementations of Eta Pairing Over Finite Fields of Small Characteristics in SECRYPT 2012 (with Abhijit Das, Dipanwita Roy Chowdhury, Bhargav Bellur and Aravind Iyer)
GPU-Based Implementation of 128-Bit Secure Eta Pairing over a Binary Field in AFRICACRYPT 2013 (with Utsab Bose and Abhijit Das)
Use of SIMD features to speed up eta pairing in E-Business and Telecommunications, Communications in Computer and Information Science, DOI: 10.1007/978-3-662-44791-8_9, Volume 455, pp 137-154, Springer-Verlag, 2014 (with Sabyasachi Karati, Abhijit Das, Dipanwita Roychowdhury, Bhargav Bellur and Aravind Iyer)