Composable Coresets for Determinant Maximization: Greedy is Almost Optimal
Siddharth Gollapudi, Sepideh Mahabadi, Varun Sivashankar
NeurIPS 2023 | December 2023
Return to Microsoft Research Lab – India
Algorithms | India
Publications
Publications by Year
-
-
Online Discrepancy with Recourse for Vectors and Graphs
SIAM Symposium on Discrete Algorithms 2022 | January 2022
-
Adaptive Extractors and their Application to Leakage Resilient Secret Sharing
Nishanth Chandran, Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, Sruthi Sekar
CRYPTO | May 2021
-
Elastic Caching
January 2020
-
Efficient, Constant-Round and Actively Secure MPC: Beyond the Three-Party Case
Nishanth Chandran, Juan Garay, Payman Mohassel, Satyanarayana Vusirikala
ACM Conference on Computer and Communications Security 2017 | August 2017
Online and dynamic algorithms for set cover
Ravishankar Krishnaswamy, Anupam Gupta, Amit Kumar, Debmalya Panigrahi
STOC 2017 Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | June 2017
HOP: Hardware makes Obfuscation Practical
Kartik Nayak, Christopher W. Fletcher, Ling Ren, Nishanth Chandran, Satya Lokam, Elaine Shi, Vipul Goyal
Network and Distributed System Security Symposium 2017 | February 2017
HOP: Hardware makes Obfuscation Practical
Kartik Nayak, Christopher W Fletcher, Ling Ren, Nishanth Chandran, Satya Lokam, Elaine Shi, Vipul Goyal
NDSS 2017 – 24th Annual Network and Distributed System Security Symposium | February 2017
-
Upper bounds on Fourier entropy
Sourav Chakraborty, Raghav Kulkarni, Satya Lokam (satya), Nitin Saurabh
Theoretical Computer Science | November 2016, Vol 654: pp. 92-112
On the Sensitivity Conjecture for Read-k Formulas
Mitali Bafna, Satya Lokam, S{'e}bastien Tavenas , Ameya Velingker
Proceedings of 41st International Symposium on Mathematical Foundations of Computer Science | August 2016
ISBN: 978-3-95977-016-3
Nearly-optimal Robust Matrix Completion
Yeshwanth Cherapanamjeri, Kartik Gupta, Prateek Jain
MSR-TR-2016-21 | July 2016
The Non-Uniform k-Center Problem
Deeparnab Chakrabarty, Prachi Goyal, Ravishankar Krishnaswamy
43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy | July 2016
ISBN: 978-3-95977-013-2
Block-wise Non-Malleable Codes
Nishanth Chandran, Vipul Goyal, Pratyay Mukherjee, Omkant Pandey, Jalaj Upadhyay
ICALP 2016 | June 2016
Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja’s Algorithm
Prateek Jain, Chi Jin, Sham Kakade, Praneeth Netrapalli, Aaron Sidford
Proceedings of The 29th Conference on Learning Theory (COLT) | June 2016
Proceedings of The 29th Conference on Learning Theory (COLT)
Efficient and Consistent Robust Time Series Analysis
Kush Bhatia, Prateek Jain, Purushottam Kar, Kamalaurben Parameswaran
MSR-TR-2016-20 | June 2016
Tensor vs Matrix Methods: Robust Tensor Decomposition under Block Sparse Perturbations
Anima Anandkumar, Prateek Jain, Yang Shi, U N Niranjan
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS) | May 2016
-
Alternating Minimization for Regression Problems with Vector-valued Outputs
Prateek Jain, Ambuj Tewari
Proceedings of the 28th Annual Conference on Advances in Neural Information Processing Systems (NIPS) | December 2015
Predtron: A Family of Online Algorithms for General Prediction Problems
Prateek Jain, Nagarajan Natarajan, Ambuj Tewari
Proceedings of the 28th Annual Conference on Advances in Neural Information Processing Systems (NIPS) | December 2015
Robust Regression via Hard Thresholding
Kush Bhatia, Prateek Jain, Purushottam Kar
Proceedings of the 28th Annual Conference on Advances in Neural Information Processing Systems (NIPS) | December 2015
Online Buy-at-Bulk Network Design
Deeparnab Chakrabarty, Alina Ene, Ravishankar Krishnaswamy, Debmalya Panigrahi
FOCS ’15 Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS) | October 2015
ISBN: 978-1-4673-8191-8
Efficient Matrix Sensing Using Rank-1 Gaussian Measurements
Kai Zhong, Prateek Jain, Inderjit S. Dhillon
Proceedings of 26th International Conference on Algorithmic Learning Theory (ALT) | October 2015
Phase Retrieval using Alternating Minimization
Praneeth Netrapalli, Prateek Jain, Sujay Sanghavi
IEEE Transactions on Signal Processing 2015. An extended abstract appeared in 27th Annual Conference on Neural Information Processing Systems 2013. | October 2015
Optimizing Non-decomposable Performance Measures: A Tale of Two Classes
, Prateek Jain
Proceedings of the 32nd International Conference on Machine Learning (ICML) | July 2015
Surrogate Functions for Maximizing Precision at the Top
Purushottam Kar, Harikrishna Narasimhan, Prateek Jain
Proceedings of the 32nd International Conference on Machine Learning (ICML) | July 2015
Fast Exact Matrix Completion with Finite Samples
Prateek Jain, Praneeth Netrapalli, Praneeth Netrapalli
Proceedings of The 28th Conference on Learning Theory (COLT) | June 2015
Multi-k-ic depth three circuit lower bound
Neeraj Kayal, Chandan Saha
Symposium on Theoretical Aspects of Computer Science (STACS) | March 2015
Symposium on Theoretical Aspects of Computer Science (STACS)
Tighter Low-rank Approximation via Sampling the Leveraged Element
Prateek Jain, Srinadh Bhojanapalli, Sujay Sanghavi
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) | January 2015
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
On (1, eps)-Restricted Assignment Makespan Minimization
Deeparnab Chakrabarty, Sanjeev Khanna, Shi Li
SODA ’15 Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, California | January 2015
Proceedings of SODA
Fast algorithms for online stochastic convex programming
Shipra Agrawal, Nikhil Devanur
SODA 2015 (ACM-SIAM Symposium on Discrete Algorithms) | January 2015
SODA 2015 (ACM-SIAM Symposium on Discrete Algorithms)
Relax, No Need to Round: Integrality of Clustering Formulations
Pranjal Awasthi, Afonso S. Bandeira, Moses Charikar, Ravishankar Krishnaswamy, Soledad Villar, Rachel Ward
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science | January 2015
ISBN: 978-1-4503-3333-7
The Hidden Graph Model: Communication Locality and Optimal Resiliency with Adaptive Faults
Nishanth Chandran, Wutichai Chongchitmate, Juan A. Garay, Shafi Goldwasser, Rafail Ostrovsky, Vassilis Zikas
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015 | January 2015
ISBN: 978-1-4503-3333-7
-
Balancing Output Length and Query Bound in Hardness Preserving Constructions of Pseudorandom Functions
Nishanth Chandran, Sanjam Garg
Progress in Cryptology – INDOCRYPT 2014 – 15th International Conference on Cryptology in India, New Delhi, India, December 14-17, 2014, Proceedings | December 2014
ISBN: 978-3-319-13038-5
Provable Submodular Minimization Using Wolfe’s Algorithm
Deeparnab Chakrabarty, Prateek Jain, Pravesh Kothari
NIPS’14 Proceedings of the 27th International Conference on Neural Information Processing Systems, Montreal, Canada | December 2014
Non-convex Robust PCA
Praneeth Netrapalli, U N Niranjan, Sujay Sanghavi, Anima Anandkumar, Prateek Jain
Advances in Neural Information Processing Systems | December 2014
On Iterative Hard Thresholding Methods for High-dimensional M-Estimation
Prateek Jain, Ambuj Tewari, Purushottam Kar
Proceedings of the 28th Annual Conference on Neural Information Processing Systems (NIPS) | December 2014
Online and Stochastic Gradient Methods for Non-decomposable Loss Functions
Purushottam Kar, Harikrishna Narasimhan, Prateek Jain
Proceedings of the 28th Annual Conference on Neural Information Processing Systems (NIPS) | December 2014
An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan
Foundations of Computer Science (FOCS) | October 2014
Invited to Special Issue of SICOMP journal
Privacy amplification with asymptotically optimal entropy loss
Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky, Leonid Reyzin
Journal of ACM | August 2014, Vol 61: pp. 29
Constrained Pseudorandom Functions: Verifiable and Delegatable
Nishanth Chandran, Srinivasan Raghuraman, Dhinakaran Vinayagamurthy
IACR Cryptology ePrint Archive | July 2014, Vol 2014: pp. 522
Learning Mixtures of Discrete Product Distributions using Spectral Decompositions
Prateek Jain, Sewoong Oh
Proceedings of The 27th Conference on Learning Theory, COLT 2014, Barcelona, Spain, June 13-15, 2014 | July 2014
Learning Sparsely Used Overcomplete Dictionaries
Alekh Agarwal, Animashree Anandkumar, Prateek Jain, Praneeth Netrapalli, Rashish Tandon
Proceedings of The 27th Conference on Learning Theory, COLT 2014, Barcelona, Spain, June 13-15, 2014 | July 2014
Universal Matrix Completion
Srinadh Bhojanapalli, Prateek Jain
Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014 | July 2014
(Near) Dimension Independent Risk Bounds for Differentially Private Learning
Prateek Jain, Abhradeep Guha Thakurta
Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014 | June 2014
Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014
A super-polynomial lower bound for regular arithmetic formulas.
Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi
Symposium on Theory of Computing (STOC) | June 2014
Symposium on Theory of Computing (STOC)
Cluster Before You Hallucinate: Approximating Node-capacitated Network Design and Energy Efficient Routing
Ravishankar Krishnaswamy, Viswanath Nagarajan, Kirk Pruhs, Cliff Stein
Proceedings of the 46th Annual ACM Symposium on Theory of Computing | May 2014
Proceedings of the 46th Annual ACM Symposium on Theory of Computing
ISBN: 978-1-4503-2710-7
Achieving Privacy in Verifiable Computation with Multiple Servers – Without FHE and without Pre-processing
Prabhanjan Ananth, Nishanth Chandran, Vipul Goyal, Bhavana Kanukurthi, Rafail Ostrovsky
Public-Key Cryptography – PKC 2014 – 17th International Conference on Practice and Theory in Public-Key Cryptography, Buenos Aires, Argentina | March 2014
ISBN: 978-3-642-54630-3
Locally Updatable and Locally Decodable Codes
Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky
Theory of Cryptography – 11th Theory of Cryptography Conference, TCC 2014, San Diego, CA, USA, February 24-26, 2014. Proceedings | March 2014
ISBN: 978-3-642-54241-1
Re-encryption, Functional Re-encryption, and Multi-hop Re-encryption: A Framework for Achieving Obfuscation-Based Security and Instantiations from Lattices
Nishanth Chandran, Melissa Chase, Feng-Hao Liu, Ryo Nishimaki, Keita Xagawa
Public-Key Cryptography – PKC 2014 – 17th International Conference on Practice and Theory in Public-Key Cryptography, Buenos Aires, Argentina, March 26-28, 2014. Proceedings | March 2014
ISBN: 978-3-642-54630-3
Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach
Nikhil Bansal, Moses Charikar, Ravishankar Krishnaswamy, Shi Li
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | January 2014
Chapter 5, in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms
ISBN: 978-1-61197-338-9
Hashing Hyperplane Queries to Near Points with Applications to Large-Scale Active Learning
Sudheendra Vijayanarasimhan, Prateek Jain, Kristen Grauman
IEEE Trans. Pattern Anal. Mach. Intell. (PAMI) | January 2014
Position-Based Quantum Cryptography: Impossibility and Constructions
Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner
SIAM Journal on Computing | January 2014, Vol 43: pp. 150-178
-
Almost-Everywhere Secure Computation with Edge Corruptions
Nishanth Chandran, Juan A. Garay, Rafail Ostrovsky
Journal of Cryptology | December 2013, pp. 1-24
Memory Limited, Streaming PCA
Ioannis Mitliagkas, Constantine Caramanis, Prateek Jain
Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States. | December 2013
Improved Multiple Sequence Alignments Using Coupled Pattern Mining
K. S. M. Tozammel Hossain, Debprakash Patnaik, Srivatsan Laxman, Prateek Jain, Chris Bailey-Kellogg, Naren Ramakrishnan
IEEE/ACM Trans. Comput. Biology Bioinform. | November 2013, Vol 10: pp. 1098-1112
Differentially Private Learning with Kernels
Prateek Jain, Abhradeep Thakurta
Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013 | July 2013
Approaching the chasm at depth four
Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
Conference on Computational Complexity | June 2013
Conference on Computational Complexity
Best Paper Award
Low-rank matrix completion using alternating minimization
Prateek Jain, Praneeth Netrapalli, Sujay Sanghavi
Symposium on Theory of Computing, STOC’13, Palo Alto, CA, USA, June 1-4, 2013 | June 2013
Random Arithmetic Formulas can be Reconstructed Efficiently
Ankit Gupta, Neeraj Kayal, Youming Qiao
Conference on Computational Complexity | June 2013
Invited to Special Issue of Computational Complexity journal
Thompson Sampling For Contextual Bandits With Linear Payoffs
Shipra Agrawal, Navin Goyal
30th International Conference on Machine Learning (ICML) | June 2013
Arithmetic Circuits: A chasm at depth three
Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
Foundations of Computer Science (FOCS) | March 2013
Invited to Special Issue of SICOMP journal
-
Edge Fault Tolerance on Sparse Networks
Nishanth Chandran, Juan A. Garay, Rafail Ostrovsky
Automata, Languages, and Programming – 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part II | July 2012
Automata, Languages, and Programming
ISBN: 978-3-642-31584-8
Functional Re-encryption and Collusion-Resistant Obfuscation
Nishanth Chandran, Melissa Chase, Vinod Vaikuntanathan
Theory of Cryptography – 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings | March 2012
Theory of Cryptography – 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings
ISBN: 978-3-642-28913-2
Approximation Algorithms for Stochastic Orienteering
Anupam Gupta, Ravishankar Krishnaswamy, Viswanath Nagarajan, R. Ravi
SODA | January 2012
-
Approximation Algorithms for Correlated Knapsack and Non-Martingale Bandits
Anupam Gupta, Ravishankar Krishnaswamy, Marco Molinaro, R. Ravi
Foundations of Computer Science | October 2011
Position-Based Quantum Cryptography: Impossibility and Constructions
Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner
Advances in Cryptology – CRYPTO 2011 – 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings | August 2011
ISBN: 978-3-642-22791-2
-
Public-Key Encryption with Efficient Amortized Updates
Nishanth Chandran, Rafail Ostrovsky, William E. Skeith III
Proceedings Security and Cryptography for Networks, 7th International Conference, SCN 2010, Amalfi, Italy, September 13-15, 2010. | September 2010
ISBN: 978-3-642-15316-7
Improved Fault Tolerance and Secure Computation on Sparse Networks
Nishanth Chandran, Juan A. Garay, Rafail Ostrovsky
Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part II | July 2010
ISBN: 978-3-642-14161-4
Privacy amplification with asymptotically optimal entropy loss
Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky, Leonid Reyzin
Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010 | June 2010
Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010
ISBN: 978-1-4503-0050-6
-
Position Based Cryptography
Nishanth Chandran, Vipul Goyal, Ryan Moriarty, Rafail Ostrovsky
Advances in Cryptology – CRYPTO 2009, 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2009. Proceedings | August 2009
ISBN: 978-3-642-03355-1
A Secure Cryptographic Token Interface
Christian Cachin, Nishanth Chandran
Proceedings of the 22nd IEEE Computer Security Foundations Symposium, CSF 2009, Port Jefferson, New York, USA, July 8-10, 2009 | July 2009
ISBN: 978-0-7695-3712-2
A Public Key Encryption Scheme Secure against Key Dependent Chosen Plaintext and Adaptive Chosen Ciphertext Attacks
Jan Camenisch, Nishanth Chandran, Victor Shoup
Advances in Cryptology – EUROCRYPT 2009, 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cologne, Germany, April 26-30, 2009. Proceedings | May 2009
Advances in Cryptology – EUROCRYPT 2009, 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cologne, Germany, April 26-30, 2009. Proceedings
ISBN: 978-3-642-01000-2
-
Improved algorithms for optimal embeddings
Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, Mohammad Ali Safari, Amit Sahai
ACM Transactions on Algorithms | August 2008, Vol 4
New Constructions for UC Secure Computation Using Tamper-Proof Hardware
Nishanth Chandran, Vipul Goyal, Amit Sahai
Advances in Cryptology – EUROCRYPT 2008, 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Istanbul, Turkey, April 13-17, 2008. Proceedings | April 2008
ISBN: 978-3-540-78966-6
-
Covert Multi-Party Computation
Nishanth Chandran, Vipul Goyal, Rafail Ostrovsky, Amit Sahai
48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings | October 2007
48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings
ISBN: 978-0-7695-3010-9
Ring Signatures of Sub-linear Size Without Random Oracles
Nishanth Chandran, Jens Groth, Amit Sahai
Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wroclaw, Poland | July 2007
ISBN: 978-3-540-73419-2
Publications by Research Area
-
Composable Coresets for Determinant Maximization: Greedy is Almost Optimal
Siddharth Gollapudi, Sepideh Mahabadi, Varun Sivashankar
NeurIPS 2023 | December 2023
Online Discrepancy with Recourse for Vectors and Graphs
SIAM Symposium on Discrete Algorithms 2022 | January 2022
Elastic Caching
January 2020
Online and dynamic algorithms for set cover
Ravishankar Krishnaswamy, Anupam Gupta, Amit Kumar, Debmalya Panigrahi
STOC 2017 Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | June 2017
Upper bounds on Fourier entropy
Sourav Chakraborty, Raghav Kulkarni, Satya Lokam (satya), Nitin Saurabh
Theoretical Computer Science | November 2016, Vol 654: pp. 92-112
On the Sensitivity Conjecture for Read-k Formulas
Mitali Bafna, Satya Lokam, S{'e}bastien Tavenas , Ameya Velingker
Proceedings of 41st International Symposium on Mathematical Foundations of Computer Science | August 2016
ISBN: 978-3-95977-016-3
Nearly-optimal Robust Matrix Completion
Yeshwanth Cherapanamjeri, Kartik Gupta, Prateek Jain
MSR-TR-2016-21 | July 2016
The Non-Uniform k-Center Problem
Deeparnab Chakrabarty, Prachi Goyal, Ravishankar Krishnaswamy
43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy | July 2016
ISBN: 978-3-95977-013-2
Block-wise Non-Malleable Codes
Nishanth Chandran, Vipul Goyal, Pratyay Mukherjee, Omkant Pandey, Jalaj Upadhyay
ICALP 2016 | June 2016
Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja’s Algorithm
Prateek Jain, Chi Jin, Sham Kakade, Praneeth Netrapalli, Aaron Sidford
Proceedings of The 29th Conference on Learning Theory (COLT) | June 2016
Proceedings of The 29th Conference on Learning Theory (COLT)
Efficient and Consistent Robust Time Series Analysis
Kush Bhatia, Prateek Jain, Purushottam Kar, Kamalaurben Parameswaran
MSR-TR-2016-20 | June 2016
Tensor vs Matrix Methods: Robust Tensor Decomposition under Block Sparse Perturbations
Anima Anandkumar, Prateek Jain, Yang Shi, U N Niranjan
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS) | May 2016
Alternating Minimization for Regression Problems with Vector-valued Outputs
Prateek Jain, Ambuj Tewari
Proceedings of the 28th Annual Conference on Advances in Neural Information Processing Systems (NIPS) | December 2015
Predtron: A Family of Online Algorithms for General Prediction Problems
Prateek Jain, Nagarajan Natarajan, Ambuj Tewari
Proceedings of the 28th Annual Conference on Advances in Neural Information Processing Systems (NIPS) | December 2015
Robust Regression via Hard Thresholding
Kush Bhatia, Prateek Jain, Purushottam Kar
Proceedings of the 28th Annual Conference on Advances in Neural Information Processing Systems (NIPS) | December 2015
Online Buy-at-Bulk Network Design
Deeparnab Chakrabarty, Alina Ene, Ravishankar Krishnaswamy, Debmalya Panigrahi
FOCS ’15 Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS) | October 2015
ISBN: 978-1-4673-8191-8
Phase Retrieval using Alternating Minimization
Praneeth Netrapalli, Prateek Jain, Sujay Sanghavi
IEEE Transactions on Signal Processing 2015. An extended abstract appeared in 27th Annual Conference on Neural Information Processing Systems 2013. | October 2015
Fast Exact Matrix Completion with Finite Samples
Prateek Jain, Praneeth Netrapalli, Praneeth Netrapalli
Proceedings of The 28th Conference on Learning Theory (COLT) | June 2015
Multi-k-ic depth three circuit lower bound
Neeraj Kayal, Chandan Saha
Symposium on Theoretical Aspects of Computer Science (STACS) | March 2015
Symposium on Theoretical Aspects of Computer Science (STACS)
Tighter Low-rank Approximation via Sampling the Leveraged Element
Prateek Jain, Srinadh Bhojanapalli, Sujay Sanghavi
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) | January 2015
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
On (1, eps)-Restricted Assignment Makespan Minimization
Deeparnab Chakrabarty, Sanjeev Khanna, Shi Li
SODA ’15 Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, California | January 2015
Proceedings of SODA
Relax, No Need to Round: Integrality of Clustering Formulations
Pranjal Awasthi, Afonso S. Bandeira, Moses Charikar, Ravishankar Krishnaswamy, Soledad Villar, Rachel Ward
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science | January 2015
ISBN: 978-1-4503-3333-7
The Hidden Graph Model: Communication Locality and Optimal Resiliency with Adaptive Faults
Nishanth Chandran, Wutichai Chongchitmate, Juan A. Garay, Shafi Goldwasser, Rafail Ostrovsky, Vassilis Zikas
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015 | January 2015
ISBN: 978-1-4503-3333-7
Fast algorithms for online stochastic convex programming
Shipra Agrawal, Nikhil Devanur
SODA 2015 (ACM-SIAM Symposium on Discrete Algorithms) | January 2015
SODA 2015 (ACM-SIAM Symposium on Discrete Algorithms)
Balancing Output Length and Query Bound in Hardness Preserving Constructions of Pseudorandom Functions
Nishanth Chandran, Sanjam Garg
Progress in Cryptology – INDOCRYPT 2014 – 15th International Conference on Cryptology in India, New Delhi, India, December 14-17, 2014, Proceedings | December 2014
ISBN: 978-3-319-13038-5
Provable Submodular Minimization Using Wolfe’s Algorithm
Deeparnab Chakrabarty, Prateek Jain, Pravesh Kothari
NIPS’14 Proceedings of the 27th International Conference on Neural Information Processing Systems, Montreal, Canada | December 2014
Online and Stochastic Gradient Methods for Non-decomposable Loss Functions
Purushottam Kar, Harikrishna Narasimhan, Prateek Jain
Proceedings of the 28th Annual Conference on Neural Information Processing Systems (NIPS) | December 2014
Non-convex Robust PCA
Praneeth Netrapalli, U N Niranjan, Sujay Sanghavi, Anima Anandkumar, Prateek Jain
Advances in Neural Information Processing Systems | December 2014
On Iterative Hard Thresholding Methods for High-dimensional M-Estimation
Prateek Jain, Ambuj Tewari, Purushottam Kar
Proceedings of the 28th Annual Conference on Neural Information Processing Systems (NIPS) | December 2014
An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan
Foundations of Computer Science (FOCS) | October 2014
Invited to Special Issue of SICOMP journal
Privacy amplification with asymptotically optimal entropy loss
Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky, Leonid Reyzin
Journal of ACM | August 2014, Vol 61: pp. 29
Learning Sparsely Used Overcomplete Dictionaries
Alekh Agarwal, Animashree Anandkumar, Prateek Jain, Praneeth Netrapalli, Rashish Tandon
Proceedings of The 27th Conference on Learning Theory, COLT 2014, Barcelona, Spain, June 13-15, 2014 | July 2014
Learning Mixtures of Discrete Product Distributions using Spectral Decompositions
Prateek Jain, Sewoong Oh
Proceedings of The 27th Conference on Learning Theory, COLT 2014, Barcelona, Spain, June 13-15, 2014 | July 2014
Universal Matrix Completion
Srinadh Bhojanapalli, Prateek Jain
Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014 | July 2014
Constrained Pseudorandom Functions: Verifiable and Delegatable
Nishanth Chandran, Srinivasan Raghuraman, Dhinakaran Vinayagamurthy
IACR Cryptology ePrint Archive | July 2014, Vol 2014: pp. 522
(Near) Dimension Independent Risk Bounds for Differentially Private Learning
Prateek Jain, Abhradeep Guha Thakurta
Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014 | June 2014
Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014
A super-polynomial lower bound for regular arithmetic formulas.
Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi
Symposium on Theory of Computing (STOC) | June 2014
Symposium on Theory of Computing (STOC)
Cluster Before You Hallucinate: Approximating Node-capacitated Network Design and Energy Efficient Routing
Ravishankar Krishnaswamy, Viswanath Nagarajan, Kirk Pruhs, Cliff Stein
Proceedings of the 46th Annual ACM Symposium on Theory of Computing | May 2014
Proceedings of the 46th Annual ACM Symposium on Theory of Computing
ISBN: 978-1-4503-2710-7
Achieving Privacy in Verifiable Computation with Multiple Servers – Without FHE and without Pre-processing
Prabhanjan Ananth, Nishanth Chandran, Vipul Goyal, Bhavana Kanukurthi, Rafail Ostrovsky
Public-Key Cryptography – PKC 2014 – 17th International Conference on Practice and Theory in Public-Key Cryptography, Buenos Aires, Argentina | March 2014
ISBN: 978-3-642-54630-3
Re-encryption, Functional Re-encryption, and Multi-hop Re-encryption: A Framework for Achieving Obfuscation-Based Security and Instantiations from Lattices
Nishanth Chandran, Melissa Chase, Feng-Hao Liu, Ryo Nishimaki, Keita Xagawa
Public-Key Cryptography – PKC 2014 – 17th International Conference on Practice and Theory in Public-Key Cryptography, Buenos Aires, Argentina, March 26-28, 2014. Proceedings | March 2014
ISBN: 978-3-642-54630-3
Locally Updatable and Locally Decodable Codes
Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky
Theory of Cryptography – 11th Theory of Cryptography Conference, TCC 2014, San Diego, CA, USA, February 24-26, 2014. Proceedings | March 2014
ISBN: 978-3-642-54241-1
Position-Based Quantum Cryptography: Impossibility and Constructions
Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner
SIAM Journal on Computing | January 2014, Vol 43: pp. 150-178
Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach
Nikhil Bansal, Moses Charikar, Ravishankar Krishnaswamy, Shi Li
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | January 2014
Chapter 5, in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms
ISBN: 978-1-61197-338-9
Almost-Everywhere Secure Computation with Edge Corruptions
Nishanth Chandran, Juan A. Garay, Rafail Ostrovsky
Journal of Cryptology | December 2013, pp. 1-24
Memory Limited, Streaming PCA
Ioannis Mitliagkas, Constantine Caramanis, Prateek Jain
Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States. | December 2013
Improved Multiple Sequence Alignments Using Coupled Pattern Mining
K. S. M. Tozammel Hossain, Debprakash Patnaik, Srivatsan Laxman, Prateek Jain, Chris Bailey-Kellogg, Naren Ramakrishnan
IEEE/ACM Trans. Comput. Biology Bioinform. | November 2013, Vol 10: pp. 1098-1112
Differentially Private Learning with Kernels
Prateek Jain, Abhradeep Thakurta
Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013 | July 2013
Approaching the chasm at depth four
Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
Conference on Computational Complexity | June 2013
Conference on Computational Complexity
Best Paper Award
Low-rank matrix completion using alternating minimization
Prateek Jain, Praneeth Netrapalli, Sujay Sanghavi
Symposium on Theory of Computing, STOC’13, Palo Alto, CA, USA, June 1-4, 2013 | June 2013
Thompson Sampling For Contextual Bandits With Linear Payoffs
Shipra Agrawal, Navin Goyal
30th International Conference on Machine Learning (ICML) | June 2013
Random Arithmetic Formulas can be Reconstructed Efficiently
Ankit Gupta, Neeraj Kayal, Youming Qiao
Conference on Computational Complexity | June 2013
Invited to Special Issue of Computational Complexity journal
Arithmetic Circuits: A chasm at depth three
Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
Foundations of Computer Science (FOCS) | March 2013
Invited to Special Issue of SICOMP journal
Edge Fault Tolerance on Sparse Networks
Nishanth Chandran, Juan A. Garay, Rafail Ostrovsky
Automata, Languages, and Programming – 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part II | July 2012
Automata, Languages, and Programming
ISBN: 978-3-642-31584-8
Functional Re-encryption and Collusion-Resistant Obfuscation
Nishanth Chandran, Melissa Chase, Vinod Vaikuntanathan
Theory of Cryptography – 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings | March 2012
Theory of Cryptography – 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings
ISBN: 978-3-642-28913-2
Approximation Algorithms for Stochastic Orienteering
Anupam Gupta, Ravishankar Krishnaswamy, Viswanath Nagarajan, R. Ravi
SODA | January 2012
Approximation Algorithms for Correlated Knapsack and Non-Martingale Bandits
Anupam Gupta, Ravishankar Krishnaswamy, Marco Molinaro, R. Ravi
Foundations of Computer Science | October 2011
Position-Based Quantum Cryptography: Impossibility and Constructions
Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner
Advances in Cryptology – CRYPTO 2011 – 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings | August 2011
ISBN: 978-3-642-22791-2
Public-Key Encryption with Efficient Amortized Updates
Nishanth Chandran, Rafail Ostrovsky, William E. Skeith III
Proceedings Security and Cryptography for Networks, 7th International Conference, SCN 2010, Amalfi, Italy, September 13-15, 2010. | September 2010
ISBN: 978-3-642-15316-7
Improved Fault Tolerance and Secure Computation on Sparse Networks
Nishanth Chandran, Juan A. Garay, Rafail Ostrovsky
Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part II | July 2010
ISBN: 978-3-642-14161-4
Privacy amplification with asymptotically optimal entropy loss
Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky, Leonid Reyzin
Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010 | June 2010
Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010
ISBN: 978-1-4503-0050-6
Position Based Cryptography
Nishanth Chandran, Vipul Goyal, Ryan Moriarty, Rafail Ostrovsky
Advances in Cryptology – CRYPTO 2009, 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2009. Proceedings | August 2009
ISBN: 978-3-642-03355-1
A Secure Cryptographic Token Interface
Christian Cachin, Nishanth Chandran
Proceedings of the 22nd IEEE Computer Security Foundations Symposium, CSF 2009, Port Jefferson, New York, USA, July 8-10, 2009 | July 2009
ISBN: 978-0-7695-3712-2
A Public Key Encryption Scheme Secure against Key Dependent Chosen Plaintext and Adaptive Chosen Ciphertext Attacks
Jan Camenisch, Nishanth Chandran, Victor Shoup
Advances in Cryptology – EUROCRYPT 2009, 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cologne, Germany, April 26-30, 2009. Proceedings | May 2009
Advances in Cryptology – EUROCRYPT 2009, 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cologne, Germany, April 26-30, 2009. Proceedings
ISBN: 978-3-642-01000-2
Improved algorithms for optimal embeddings
Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, Mohammad Ali Safari, Amit Sahai
ACM Transactions on Algorithms | August 2008, Vol 4
New Constructions for UC Secure Computation Using Tamper-Proof Hardware
Nishanth Chandran, Vipul Goyal, Amit Sahai
Advances in Cryptology – EUROCRYPT 2008, 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Istanbul, Turkey, April 13-17, 2008. Proceedings | April 2008
ISBN: 978-3-540-78966-6
Covert Multi-Party Computation
Nishanth Chandran, Vipul Goyal, Rafail Ostrovsky, Amit Sahai
48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings | October 2007
48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings
ISBN: 978-0-7695-3010-9
Ring Signatures of Sub-linear Size Without Random Oracles
Nishanth Chandran, Jens Groth, Amit Sahai
Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wroclaw, Poland | July 2007
ISBN: 978-3-540-73419-2
-
Adaptive Extractors and their Application to Leakage Resilient Secret Sharing
Nishanth Chandran, Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, Sruthi Sekar
CRYPTO | May 2021
Efficient, Constant-Round and Actively Secure MPC: Beyond the Three-Party Case
Nishanth Chandran, Juan Garay, Payman Mohassel, Satyanarayana Vusirikala
ACM Conference on Computer and Communications Security 2017 | August 2017
HOP: Hardware makes Obfuscation Practical
Kartik Nayak, Christopher W. Fletcher, Ling Ren, Nishanth Chandran, Satya Lokam, Elaine Shi, Vipul Goyal
Network and Distributed System Security Symposium 2017 | February 2017
HOP: Hardware makes Obfuscation Practical
Kartik Nayak, Christopher W Fletcher, Ling Ren, Nishanth Chandran, Satya Lokam, Elaine Shi, Vipul Goyal
NDSS 2017 – 24th Annual Network and Distributed System Security Symposium | February 2017
Block-wise Non-Malleable Codes
Nishanth Chandran, Vipul Goyal, Pratyay Mukherjee, Omkant Pandey, Jalaj Upadhyay
ICALP 2016 | June 2016
The Hidden Graph Model: Communication Locality and Optimal Resiliency with Adaptive Faults
Nishanth Chandran, Wutichai Chongchitmate, Juan A. Garay, Shafi Goldwasser, Rafail Ostrovsky, Vassilis Zikas
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015 | January 2015
ISBN: 978-1-4503-3333-7
Privacy amplification with asymptotically optimal entropy loss
Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky, Leonid Reyzin
Journal of ACM | August 2014, Vol 61: pp. 29
Constrained Pseudorandom Functions: Verifiable and Delegatable
Nishanth Chandran, Srinivasan Raghuraman, Dhinakaran Vinayagamurthy
IACR Cryptology ePrint Archive | July 2014, Vol 2014: pp. 522
Achieving Privacy in Verifiable Computation with Multiple Servers – Without FHE and without Pre-processing
Prabhanjan Ananth, Nishanth Chandran, Vipul Goyal, Bhavana Kanukurthi, Rafail Ostrovsky
Public-Key Cryptography – PKC 2014 – 17th International Conference on Practice and Theory in Public-Key Cryptography, Buenos Aires, Argentina | March 2014
ISBN: 978-3-642-54630-3
Re-encryption, Functional Re-encryption, and Multi-hop Re-encryption: A Framework for Achieving Obfuscation-Based Security and Instantiations from Lattices
Nishanth Chandran, Melissa Chase, Feng-Hao Liu, Ryo Nishimaki, Keita Xagawa
Public-Key Cryptography – PKC 2014 – 17th International Conference on Practice and Theory in Public-Key Cryptography, Buenos Aires, Argentina, March 26-28, 2014. Proceedings | March 2014
ISBN: 978-3-642-54630-3
Locally Updatable and Locally Decodable Codes
Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky
Theory of Cryptography – 11th Theory of Cryptography Conference, TCC 2014, San Diego, CA, USA, February 24-26, 2014. Proceedings | March 2014
ISBN: 978-3-642-54241-1
Position-Based Quantum Cryptography: Impossibility and Constructions
Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner
SIAM Journal on Computing | January 2014, Vol 43: pp. 150-178
Almost-Everywhere Secure Computation with Edge Corruptions
Nishanth Chandran, Juan A. Garay, Rafail Ostrovsky
Journal of Cryptology | December 2013, pp. 1-24
Edge Fault Tolerance on Sparse Networks
Nishanth Chandran, Juan A. Garay, Rafail Ostrovsky
Automata, Languages, and Programming – 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part II | July 2012
Automata, Languages, and Programming
ISBN: 978-3-642-31584-8
Functional Re-encryption and Collusion-Resistant Obfuscation
Nishanth Chandran, Melissa Chase, Vinod Vaikuntanathan
Theory of Cryptography – 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings | March 2012
Theory of Cryptography – 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings
ISBN: 978-3-642-28913-2
Position-Based Quantum Cryptography: Impossibility and Constructions
Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner
Advances in Cryptology – CRYPTO 2011 – 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings | August 2011
ISBN: 978-3-642-22791-2
Public-Key Encryption with Efficient Amortized Updates
Nishanth Chandran, Rafail Ostrovsky, William E. Skeith III
Proceedings Security and Cryptography for Networks, 7th International Conference, SCN 2010, Amalfi, Italy, September 13-15, 2010. | September 2010
ISBN: 978-3-642-15316-7
Improved Fault Tolerance and Secure Computation on Sparse Networks
Nishanth Chandran, Juan A. Garay, Rafail Ostrovsky
Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part II | July 2010
ISBN: 978-3-642-14161-4
Privacy amplification with asymptotically optimal entropy loss
Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky, Leonid Reyzin
Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010 | June 2010
Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010
ISBN: 978-1-4503-0050-6
Position Based Cryptography
Nishanth Chandran, Vipul Goyal, Ryan Moriarty, Rafail Ostrovsky
Advances in Cryptology – CRYPTO 2009, 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2009. Proceedings | August 2009
ISBN: 978-3-642-03355-1
A Secure Cryptographic Token Interface
Christian Cachin, Nishanth Chandran
Proceedings of the 22nd IEEE Computer Security Foundations Symposium, CSF 2009, Port Jefferson, New York, USA, July 8-10, 2009 | July 2009
ISBN: 978-0-7695-3712-2
A Public Key Encryption Scheme Secure against Key Dependent Chosen Plaintext and Adaptive Chosen Ciphertext Attacks
Jan Camenisch, Nishanth Chandran, Victor Shoup
Advances in Cryptology – EUROCRYPT 2009, 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cologne, Germany, April 26-30, 2009. Proceedings | May 2009
Advances in Cryptology – EUROCRYPT 2009, 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cologne, Germany, April 26-30, 2009. Proceedings
ISBN: 978-3-642-01000-2
New Constructions for UC Secure Computation Using Tamper-Proof Hardware
Nishanth Chandran, Vipul Goyal, Amit Sahai
Advances in Cryptology – EUROCRYPT 2008, 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Istanbul, Turkey, April 13-17, 2008. Proceedings | April 2008
ISBN: 978-3-540-78966-6
Covert Multi-Party Computation
Nishanth Chandran, Vipul Goyal, Rafail Ostrovsky, Amit Sahai
48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings | October 2007
48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings
ISBN: 978-0-7695-3010-9
Ring Signatures of Sub-linear Size Without Random Oracles
Nishanth Chandran, Jens Groth, Amit Sahai
Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wroclaw, Poland | July 2007
ISBN: 978-3-540-73419-2
-
Position-Based Quantum Cryptography: Impossibility and Constructions
Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner
SIAM Journal on Computing | January 2014, Vol 43: pp. 150-178
Position-Based Quantum Cryptography: Impossibility and Constructions
Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner
Advances in Cryptology – CRYPTO 2011 – 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings | August 2011
ISBN: 978-3-642-22791-2
-
Upper bounds on Fourier entropy
Sourav Chakraborty, Raghav Kulkarni, Satya Lokam (satya), Nitin Saurabh
Theoretical Computer Science | November 2016, Vol 654: pp. 92-112
On the Sensitivity Conjecture for Read-k Formulas
Mitali Bafna, Satya Lokam, S{'e}bastien Tavenas , Ameya Velingker
Proceedings of 41st International Symposium on Mathematical Foundations of Computer Science | August 2016
ISBN: 978-3-95977-016-3
-
Nearly-optimal Robust Matrix Completion
Yeshwanth Cherapanamjeri, Kartik Gupta, Prateek Jain
MSR-TR-2016-21 | July 2016
Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja’s Algorithm
Prateek Jain, Chi Jin, Sham Kakade, Praneeth Netrapalli, Aaron Sidford
Proceedings of The 29th Conference on Learning Theory (COLT) | June 2016
Proceedings of The 29th Conference on Learning Theory (COLT)
Efficient and Consistent Robust Time Series Analysis
Kush Bhatia, Prateek Jain, Purushottam Kar, Kamalaurben Parameswaran
MSR-TR-2016-20 | June 2016
Tensor vs Matrix Methods: Robust Tensor Decomposition under Block Sparse Perturbations
Anima Anandkumar, Prateek Jain, Yang Shi, U N Niranjan
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS) | May 2016
Alternating Minimization for Regression Problems with Vector-valued Outputs
Prateek Jain, Ambuj Tewari
Proceedings of the 28th Annual Conference on Advances in Neural Information Processing Systems (NIPS) | December 2015
Predtron: A Family of Online Algorithms for General Prediction Problems
Prateek Jain, Nagarajan Natarajan, Ambuj Tewari
Proceedings of the 28th Annual Conference on Advances in Neural Information Processing Systems (NIPS) | December 2015
Robust Regression via Hard Thresholding
Kush Bhatia, Prateek Jain, Purushottam Kar
Proceedings of the 28th Annual Conference on Advances in Neural Information Processing Systems (NIPS) | December 2015
Efficient Matrix Sensing Using Rank-1 Gaussian Measurements
Kai Zhong, Prateek Jain, Inderjit S. Dhillon
Proceedings of 26th International Conference on Algorithmic Learning Theory (ALT) | October 2015
Phase Retrieval using Alternating Minimization
Praneeth Netrapalli, Prateek Jain, Sujay Sanghavi
IEEE Transactions on Signal Processing 2015. An extended abstract appeared in 27th Annual Conference on Neural Information Processing Systems 2013. | October 2015
Surrogate Functions for Maximizing Precision at the Top
Purushottam Kar, Harikrishna Narasimhan, Prateek Jain
Proceedings of the 32nd International Conference on Machine Learning (ICML) | July 2015
Optimizing Non-decomposable Performance Measures: A Tale of Two Classes
, Prateek Jain
Proceedings of the 32nd International Conference on Machine Learning (ICML) | July 2015
Fast Exact Matrix Completion with Finite Samples
Prateek Jain, Praneeth Netrapalli, Praneeth Netrapalli
Proceedings of The 28th Conference on Learning Theory (COLT) | June 2015
Tighter Low-rank Approximation via Sampling the Leveraged Element
Prateek Jain, Srinadh Bhojanapalli, Sujay Sanghavi
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) | January 2015
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
Fast algorithms for online stochastic convex programming
Shipra Agrawal, Nikhil Devanur
SODA 2015 (ACM-SIAM Symposium on Discrete Algorithms) | January 2015
SODA 2015 (ACM-SIAM Symposium on Discrete Algorithms)
Provable Submodular Minimization Using Wolfe’s Algorithm
Deeparnab Chakrabarty, Prateek Jain, Pravesh Kothari
NIPS’14 Proceedings of the 27th International Conference on Neural Information Processing Systems, Montreal, Canada | December 2014
Online and Stochastic Gradient Methods for Non-decomposable Loss Functions
Purushottam Kar, Harikrishna Narasimhan, Prateek Jain
Proceedings of the 28th Annual Conference on Neural Information Processing Systems (NIPS) | December 2014
Non-convex Robust PCA
Praneeth Netrapalli, U N Niranjan, Sujay Sanghavi, Anima Anandkumar, Prateek Jain
Advances in Neural Information Processing Systems | December 2014
On Iterative Hard Thresholding Methods for High-dimensional M-Estimation
Prateek Jain, Ambuj Tewari, Purushottam Kar
Proceedings of the 28th Annual Conference on Neural Information Processing Systems (NIPS) | December 2014
Learning Sparsely Used Overcomplete Dictionaries
Alekh Agarwal, Animashree Anandkumar, Prateek Jain, Praneeth Netrapalli, Rashish Tandon
Proceedings of The 27th Conference on Learning Theory, COLT 2014, Barcelona, Spain, June 13-15, 2014 | July 2014
Learning Mixtures of Discrete Product Distributions using Spectral Decompositions
Prateek Jain, Sewoong Oh
Proceedings of The 27th Conference on Learning Theory, COLT 2014, Barcelona, Spain, June 13-15, 2014 | July 2014
Universal Matrix Completion
Srinadh Bhojanapalli, Prateek Jain
Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014 | July 2014
(Near) Dimension Independent Risk Bounds for Differentially Private Learning
Prateek Jain, Abhradeep Guha Thakurta
Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014 | June 2014
Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014
Hashing Hyperplane Queries to Near Points with Applications to Large-Scale Active Learning
Sudheendra Vijayanarasimhan, Prateek Jain, Kristen Grauman
IEEE Trans. Pattern Anal. Mach. Intell. (PAMI) | January 2014
Memory Limited, Streaming PCA
Ioannis Mitliagkas, Constantine Caramanis, Prateek Jain
Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States. | December 2013
Improved Multiple Sequence Alignments Using Coupled Pattern Mining
K. S. M. Tozammel Hossain, Debprakash Patnaik, Srivatsan Laxman, Prateek Jain, Chris Bailey-Kellogg, Naren Ramakrishnan
IEEE/ACM Trans. Comput. Biology Bioinform. | November 2013, Vol 10: pp. 1098-1112
Differentially Private Learning with Kernels
Prateek Jain, Abhradeep Thakurta
Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013 | July 2013
Low-rank matrix completion using alternating minimization
Prateek Jain, Praneeth Netrapalli, Sujay Sanghavi
Symposium on Theory of Computing, STOC’13, Palo Alto, CA, USA, June 1-4, 2013 | June 2013
Thompson Sampling For Contextual Bandits With Linear Payoffs
Shipra Agrawal, Navin Goyal
30th International Conference on Machine Learning (ICML) | June 2013
Publications by Type
-
Composable Coresets for Determinant Maximization: Greedy is Almost Optimal
Siddharth Gollapudi, Sepideh Mahabadi, Varun Sivashankar
NeurIPS 2023 | December 2023
Online Discrepancy with Recourse for Vectors and Graphs
SIAM Symposium on Discrete Algorithms 2022 | January 2022
Adaptive Extractors and their Application to Leakage Resilient Secret Sharing
Nishanth Chandran, Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, Sruthi Sekar
CRYPTO | May 2021
Elastic Caching
January 2020
Efficient, Constant-Round and Actively Secure MPC: Beyond the Three-Party Case
Nishanth Chandran, Juan Garay, Payman Mohassel, Satyanarayana Vusirikala
ACM Conference on Computer and Communications Security 2017 | August 2017
Online and dynamic algorithms for set cover
Ravishankar Krishnaswamy, Anupam Gupta, Amit Kumar, Debmalya Panigrahi
STOC 2017 Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | June 2017
HOP: Hardware makes Obfuscation Practical
Kartik Nayak, Christopher W. Fletcher, Ling Ren, Nishanth Chandran, Satya Lokam, Elaine Shi, Vipul Goyal
Network and Distributed System Security Symposium 2017 | February 2017
HOP: Hardware makes Obfuscation Practical
Kartik Nayak, Christopher W Fletcher, Ling Ren, Nishanth Chandran, Satya Lokam, Elaine Shi, Vipul Goyal
NDSS 2017 – 24th Annual Network and Distributed System Security Symposium | February 2017
On the Sensitivity Conjecture for Read-k Formulas
Mitali Bafna, Satya Lokam, S{'e}bastien Tavenas , Ameya Velingker
Proceedings of 41st International Symposium on Mathematical Foundations of Computer Science | August 2016
ISBN: 978-3-95977-016-3
The Non-Uniform k-Center Problem
Deeparnab Chakrabarty, Prachi Goyal, Ravishankar Krishnaswamy
43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy | July 2016
ISBN: 978-3-95977-013-2
Block-wise Non-Malleable Codes
Nishanth Chandran, Vipul Goyal, Pratyay Mukherjee, Omkant Pandey, Jalaj Upadhyay
ICALP 2016 | June 2016
Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja’s Algorithm
Prateek Jain, Chi Jin, Sham Kakade, Praneeth Netrapalli, Aaron Sidford
Proceedings of The 29th Conference on Learning Theory (COLT) | June 2016
Proceedings of The 29th Conference on Learning Theory (COLT)
Tensor vs Matrix Methods: Robust Tensor Decomposition under Block Sparse Perturbations
Anima Anandkumar, Prateek Jain, Yang Shi, U N Niranjan
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS) | May 2016
Alternating Minimization for Regression Problems with Vector-valued Outputs
Prateek Jain, Ambuj Tewari
Proceedings of the 28th Annual Conference on Advances in Neural Information Processing Systems (NIPS) | December 2015
Predtron: A Family of Online Algorithms for General Prediction Problems
Prateek Jain, Nagarajan Natarajan, Ambuj Tewari
Proceedings of the 28th Annual Conference on Advances in Neural Information Processing Systems (NIPS) | December 2015
Robust Regression via Hard Thresholding
Kush Bhatia, Prateek Jain, Purushottam Kar
Proceedings of the 28th Annual Conference on Advances in Neural Information Processing Systems (NIPS) | December 2015
Online Buy-at-Bulk Network Design
Deeparnab Chakrabarty, Alina Ene, Ravishankar Krishnaswamy, Debmalya Panigrahi
FOCS ’15 Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS) | October 2015
ISBN: 978-1-4673-8191-8
Efficient Matrix Sensing Using Rank-1 Gaussian Measurements
Kai Zhong, Prateek Jain, Inderjit S. Dhillon
Proceedings of 26th International Conference on Algorithmic Learning Theory (ALT) | October 2015
Phase Retrieval using Alternating Minimization
Praneeth Netrapalli, Prateek Jain, Sujay Sanghavi
IEEE Transactions on Signal Processing 2015. An extended abstract appeared in 27th Annual Conference on Neural Information Processing Systems 2013. | October 2015
Surrogate Functions for Maximizing Precision at the Top
Purushottam Kar, Harikrishna Narasimhan, Prateek Jain
Proceedings of the 32nd International Conference on Machine Learning (ICML) | July 2015
Optimizing Non-decomposable Performance Measures: A Tale of Two Classes
, Prateek Jain
Proceedings of the 32nd International Conference on Machine Learning (ICML) | July 2015
Fast Exact Matrix Completion with Finite Samples
Prateek Jain, Praneeth Netrapalli, Praneeth Netrapalli
Proceedings of The 28th Conference on Learning Theory (COLT) | June 2015
Multi-k-ic depth three circuit lower bound
Neeraj Kayal, Chandan Saha
Symposium on Theoretical Aspects of Computer Science (STACS) | March 2015
Symposium on Theoretical Aspects of Computer Science (STACS)
Tighter Low-rank Approximation via Sampling the Leveraged Element
Prateek Jain, Srinadh Bhojanapalli, Sujay Sanghavi
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) | January 2015
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
On (1, eps)-Restricted Assignment Makespan Minimization
Deeparnab Chakrabarty, Sanjeev Khanna, Shi Li
SODA ’15 Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, California | January 2015
Proceedings of SODA
Relax, No Need to Round: Integrality of Clustering Formulations
Pranjal Awasthi, Afonso S. Bandeira, Moses Charikar, Ravishankar Krishnaswamy, Soledad Villar, Rachel Ward
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science | January 2015
ISBN: 978-1-4503-3333-7
The Hidden Graph Model: Communication Locality and Optimal Resiliency with Adaptive Faults
Nishanth Chandran, Wutichai Chongchitmate, Juan A. Garay, Shafi Goldwasser, Rafail Ostrovsky, Vassilis Zikas
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015 | January 2015
ISBN: 978-1-4503-3333-7
Fast algorithms for online stochastic convex programming
Shipra Agrawal, Nikhil Devanur
SODA 2015 (ACM-SIAM Symposium on Discrete Algorithms) | January 2015
SODA 2015 (ACM-SIAM Symposium on Discrete Algorithms)
Balancing Output Length and Query Bound in Hardness Preserving Constructions of Pseudorandom Functions
Nishanth Chandran, Sanjam Garg
Progress in Cryptology – INDOCRYPT 2014 – 15th International Conference on Cryptology in India, New Delhi, India, December 14-17, 2014, Proceedings | December 2014
ISBN: 978-3-319-13038-5
Provable Submodular Minimization Using Wolfe’s Algorithm
Deeparnab Chakrabarty, Prateek Jain, Pravesh Kothari
NIPS’14 Proceedings of the 27th International Conference on Neural Information Processing Systems, Montreal, Canada | December 2014
Online and Stochastic Gradient Methods for Non-decomposable Loss Functions
Purushottam Kar, Harikrishna Narasimhan, Prateek Jain
Proceedings of the 28th Annual Conference on Neural Information Processing Systems (NIPS) | December 2014
Non-convex Robust PCA
Praneeth Netrapalli, U N Niranjan, Sujay Sanghavi, Anima Anandkumar, Prateek Jain
Advances in Neural Information Processing Systems | December 2014
On Iterative Hard Thresholding Methods for High-dimensional M-Estimation
Prateek Jain, Ambuj Tewari, Purushottam Kar
Proceedings of the 28th Annual Conference on Neural Information Processing Systems (NIPS) | December 2014
An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan
Foundations of Computer Science (FOCS) | October 2014
Invited to Special Issue of SICOMP journal
Learning Sparsely Used Overcomplete Dictionaries
Alekh Agarwal, Animashree Anandkumar, Prateek Jain, Praneeth Netrapalli, Rashish Tandon
Proceedings of The 27th Conference on Learning Theory, COLT 2014, Barcelona, Spain, June 13-15, 2014 | July 2014
Learning Mixtures of Discrete Product Distributions using Spectral Decompositions
Prateek Jain, Sewoong Oh
Proceedings of The 27th Conference on Learning Theory, COLT 2014, Barcelona, Spain, June 13-15, 2014 | July 2014
Universal Matrix Completion
Srinadh Bhojanapalli, Prateek Jain
Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014 | July 2014
(Near) Dimension Independent Risk Bounds for Differentially Private Learning
Prateek Jain, Abhradeep Guha Thakurta
Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014 | June 2014
Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014
A super-polynomial lower bound for regular arithmetic formulas.
Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi
Symposium on Theory of Computing (STOC) | June 2014
Symposium on Theory of Computing (STOC)
Cluster Before You Hallucinate: Approximating Node-capacitated Network Design and Energy Efficient Routing
Ravishankar Krishnaswamy, Viswanath Nagarajan, Kirk Pruhs, Cliff Stein
Proceedings of the 46th Annual ACM Symposium on Theory of Computing | May 2014
Proceedings of the 46th Annual ACM Symposium on Theory of Computing
ISBN: 978-1-4503-2710-7
Achieving Privacy in Verifiable Computation with Multiple Servers – Without FHE and without Pre-processing
Prabhanjan Ananth, Nishanth Chandran, Vipul Goyal, Bhavana Kanukurthi, Rafail Ostrovsky
Public-Key Cryptography – PKC 2014 – 17th International Conference on Practice and Theory in Public-Key Cryptography, Buenos Aires, Argentina | March 2014
ISBN: 978-3-642-54630-3
Re-encryption, Functional Re-encryption, and Multi-hop Re-encryption: A Framework for Achieving Obfuscation-Based Security and Instantiations from Lattices
Nishanth Chandran, Melissa Chase, Feng-Hao Liu, Ryo Nishimaki, Keita Xagawa
Public-Key Cryptography – PKC 2014 – 17th International Conference on Practice and Theory in Public-Key Cryptography, Buenos Aires, Argentina, March 26-28, 2014. Proceedings | March 2014
ISBN: 978-3-642-54630-3
Locally Updatable and Locally Decodable Codes
Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky
Theory of Cryptography – 11th Theory of Cryptography Conference, TCC 2014, San Diego, CA, USA, February 24-26, 2014. Proceedings | March 2014
ISBN: 978-3-642-54241-1
Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach
Nikhil Bansal, Moses Charikar, Ravishankar Krishnaswamy, Shi Li
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | January 2014
Chapter 5, in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms
ISBN: 978-1-61197-338-9
Hashing Hyperplane Queries to Near Points with Applications to Large-Scale Active Learning
Sudheendra Vijayanarasimhan, Prateek Jain, Kristen Grauman
IEEE Trans. Pattern Anal. Mach. Intell. (PAMI) | January 2014
Memory Limited, Streaming PCA
Ioannis Mitliagkas, Constantine Caramanis, Prateek Jain
Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States. | December 2013
Differentially Private Learning with Kernels
Prateek Jain, Abhradeep Thakurta
Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013 | July 2013
Approaching the chasm at depth four
Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
Conference on Computational Complexity | June 2013
Conference on Computational Complexity
Best Paper Award
Low-rank matrix completion using alternating minimization
Prateek Jain, Praneeth Netrapalli, Sujay Sanghavi
Symposium on Theory of Computing, STOC’13, Palo Alto, CA, USA, June 1-4, 2013 | June 2013
Thompson Sampling For Contextual Bandits With Linear Payoffs
Shipra Agrawal, Navin Goyal
30th International Conference on Machine Learning (ICML) | June 2013
Random Arithmetic Formulas can be Reconstructed Efficiently
Ankit Gupta, Neeraj Kayal, Youming Qiao
Conference on Computational Complexity | June 2013
Invited to Special Issue of Computational Complexity journal
Arithmetic Circuits: A chasm at depth three
Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
Foundations of Computer Science (FOCS) | March 2013
Invited to Special Issue of SICOMP journal
Edge Fault Tolerance on Sparse Networks
Nishanth Chandran, Juan A. Garay, Rafail Ostrovsky
Automata, Languages, and Programming – 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part II | July 2012
Automata, Languages, and Programming
ISBN: 978-3-642-31584-8
Functional Re-encryption and Collusion-Resistant Obfuscation
Nishanth Chandran, Melissa Chase, Vinod Vaikuntanathan
Theory of Cryptography – 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings | March 2012
Theory of Cryptography – 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings
ISBN: 978-3-642-28913-2
Approximation Algorithms for Stochastic Orienteering
Anupam Gupta, Ravishankar Krishnaswamy, Viswanath Nagarajan, R. Ravi
SODA | January 2012
Approximation Algorithms for Correlated Knapsack and Non-Martingale Bandits
Anupam Gupta, Ravishankar Krishnaswamy, Marco Molinaro, R. Ravi
Foundations of Computer Science | October 2011
Position-Based Quantum Cryptography: Impossibility and Constructions
Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner
Advances in Cryptology – CRYPTO 2011 – 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings | August 2011
ISBN: 978-3-642-22791-2
Public-Key Encryption with Efficient Amortized Updates
Nishanth Chandran, Rafail Ostrovsky, William E. Skeith III
Proceedings Security and Cryptography for Networks, 7th International Conference, SCN 2010, Amalfi, Italy, September 13-15, 2010. | September 2010
ISBN: 978-3-642-15316-7
Improved Fault Tolerance and Secure Computation on Sparse Networks
Nishanth Chandran, Juan A. Garay, Rafail Ostrovsky
Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part II | July 2010
ISBN: 978-3-642-14161-4
Privacy amplification with asymptotically optimal entropy loss
Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky, Leonid Reyzin
Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010 | June 2010
Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010
ISBN: 978-1-4503-0050-6
Position Based Cryptography
Nishanth Chandran, Vipul Goyal, Ryan Moriarty, Rafail Ostrovsky
Advances in Cryptology – CRYPTO 2009, 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2009. Proceedings | August 2009
ISBN: 978-3-642-03355-1
A Secure Cryptographic Token Interface
Christian Cachin, Nishanth Chandran
Proceedings of the 22nd IEEE Computer Security Foundations Symposium, CSF 2009, Port Jefferson, New York, USA, July 8-10, 2009 | July 2009
ISBN: 978-0-7695-3712-2
A Public Key Encryption Scheme Secure against Key Dependent Chosen Plaintext and Adaptive Chosen Ciphertext Attacks
Jan Camenisch, Nishanth Chandran, Victor Shoup
Advances in Cryptology – EUROCRYPT 2009, 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cologne, Germany, April 26-30, 2009. Proceedings | May 2009
Advances in Cryptology – EUROCRYPT 2009, 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cologne, Germany, April 26-30, 2009. Proceedings
ISBN: 978-3-642-01000-2
New Constructions for UC Secure Computation Using Tamper-Proof Hardware
Nishanth Chandran, Vipul Goyal, Amit Sahai
Advances in Cryptology – EUROCRYPT 2008, 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Istanbul, Turkey, April 13-17, 2008. Proceedings | April 2008
ISBN: 978-3-540-78966-6
Covert Multi-Party Computation
Nishanth Chandran, Vipul Goyal, Rafail Ostrovsky, Amit Sahai
48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings | October 2007
48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings
ISBN: 978-0-7695-3010-9
Ring Signatures of Sub-linear Size Without Random Oracles
Nishanth Chandran, Jens Groth, Amit Sahai
Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wroclaw, Poland | July 2007
ISBN: 978-3-540-73419-2
-
Upper bounds on Fourier entropy
Sourav Chakraborty, Raghav Kulkarni, Satya Lokam (satya), Nitin Saurabh
Theoretical Computer Science | November 2016, Vol 654: pp. 92-112
Privacy amplification with asymptotically optimal entropy loss
Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky, Leonid Reyzin
Journal of ACM | August 2014, Vol 61: pp. 29
Constrained Pseudorandom Functions: Verifiable and Delegatable
Nishanth Chandran, Srinivasan Raghuraman, Dhinakaran Vinayagamurthy
IACR Cryptology ePrint Archive | July 2014, Vol 2014: pp. 522
Position-Based Quantum Cryptography: Impossibility and Constructions
Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner
SIAM Journal on Computing | January 2014, Vol 43: pp. 150-178
Almost-Everywhere Secure Computation with Edge Corruptions
Nishanth Chandran, Juan A. Garay, Rafail Ostrovsky
Journal of Cryptology | December 2013, pp. 1-24
Improved Multiple Sequence Alignments Using Coupled Pattern Mining
K. S. M. Tozammel Hossain, Debprakash Patnaik, Srivatsan Laxman, Prateek Jain, Chris Bailey-Kellogg, Naren Ramakrishnan
IEEE/ACM Trans. Comput. Biology Bioinform. | November 2013, Vol 10: pp. 1098-1112
Improved algorithms for optimal embeddings
Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, Mohammad Ali Safari, Amit Sahai
ACM Transactions on Algorithms | August 2008, Vol 4
-
Nearly-optimal Robust Matrix Completion
Yeshwanth Cherapanamjeri, Kartik Gupta, Prateek Jain
MSR-TR-2016-21 | July 2016
Efficient and Consistent Robust Time Series Analysis
Kush Bhatia, Prateek Jain, Purushottam Kar, Kamalaurben Parameswaran
MSR-TR-2016-20 | June 2016