Research Interests

Cryptography
Lower Bounds in Combinatorial and Algebraic Complexity
Coding Theory
Randomness in Computation

Recent Publications

Ankit Gupta, Neeraj Kayal, and Satya Lokam, Reconstruction of Depth-4 Multilinear Circuits with top fanin two, in Symposium on Theory of Computing (STOC), ACM, 2012
Ankit Gupta, neeraj kayal, and satya lokam, Efficient Reconstruction of Random Multilinear Formulas, in Foundations of Computer Science (FOCS), IEEE, October 2011
Ankit Gupta, Neeraj Kayal, and Satya Lokam, Efficient Reconstruction of Random Multilinear Formulas, in Foundations of Computer Science (FOCS), IEEE, 2011
Satyanarayana V. Lokam, Complexity Lower Bounds using Linear Algebra, vol. 4, no. 1-2, pp. 1-155, September 2009
Raghav Bhaskar, Karthekeyan Chandrasekaran, Satyanaryana V. Lokam, Peter L. Montgomery, Ramarathnam Venkatesan, and Yacov Yacobi, An observation about variations of the Diffie-Hellman assumption, in Serdica Journal of Computing, 2009
Raghav Bhaskar, K. Chandrasekaran, Satyanarayana V. Lokam, P. L. Montgomery, R. Venkatesan, and Yacov Yacobi, Vulnerabilities in Anonymous Credential Systems, in Electr. Notes Theor. Comput. Sci., vol. 197, no. 2, pp. 141-148, Elsevier , 2008
Sanjam Garg, Raghav Bhaskar, and Satyanarayana V. Lokam, Improved Bounds on Security Reductions for Discrete Log Based Signatures, in CRYPTO, Springer, 2008
Dungjade Shiowattana and Satyanarayana V. Lokam, An optimal lower bound for 2-query locally decodable linear codes, in Inf. Process. Lett., vol. 97, no. 6, pp. 244-250, 2006
Satyanarayana V. Lokam, Quadratic Lower Bounds on Matrix Rigidity, in TAMC, Springer, 2006
Amit Deshpande, Rahul Jain, Telikepalli Kavitha, Satyanarayana V. Lokam, and Jaikumar Radhakrishnan, Lower bounds for adaptive locally decodable codes, in Random Structures and Algorithms, vol. 27, no. 3, pp. 358-378, 2005