Prahladh Harsha
Citado por
Citado por
Robust PCPs of proximity, shorter PCPs and applications to coding
E Ben-Sasson, O Goldreich, P Harsha, M Sudan, S Vadhan
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing …, 2004
Some 3CNF properties are hard to test
E Ben-Sasson, P Harsha, S Raskhodnikova
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing …, 2003
The communication complexity of correlation
P Harsha, R Jain, D McAllester, J Radhakrishnan
Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), 10-23, 2007
Complexity of inference in graphical models
V Chandrasekaran, N Srebro, P Harsha
arXiv preprint arXiv:1206.3240, 2012
Short PCPs verifiable in polylogarithmic time
E Ben-Sasson, O Goldreich, P Harsha, M Sudan, S Vadhan
Computational Complexity, 2005. Proceedings. Twentieth Annual IEEE …, 2005
Bounding the sensitivity of polynomial threshold functions
P Harsha, A Klivans, R Meka
arXiv preprint arXiv:0909.5175, 2009
Composition of low-error 2-query PCPs using decodable PCPs
I Dinur, P Harsha
SIAM Journal on Computing 42 (6), 2452-2486, 2013
Small PCPs with low query complexity
P Harsha, M Sudan
Computational Complexity 9 (3), 157-201, 2000
Distributed processing in automata
K Krithivasan, NS BALAN, P Harsha
International Journal of Foundations of Computer Science 10 (04), 443-463, 1999
An invariance principle for polytopes
P Harsha, A Klivans, R Meka
Journal of the ACM (JACM) 59 (6), 1-25, 2013
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes
V Guruswami, P Harsha, J Håstad, S Srinivasan, G Varma
SIAM Journal on Computing 46 (1), 132-159, 2017
Sound 3-query PCPPs are long
E Ben-Sasson, P Harsha, O Lachish, A Matsliah
ACM Transactions on Computation Theory (TOCT) 1 (2), 1-49, 2009
On polynomial approximations to AC
P Harsha, S Srinivasan
Random Structures & Algorithms 54 (2), 289-303, 2019
List-Decoding with Double Samplers
I Dinur, P Harsha, T Kaufman, IL Navon, A Ta-Shma
SIAM Journal on Computing 50 (2), 301-349, 2021
Minimizing average latency in oblivious routing
P Harsha, TP Hayes, H Narayanan, H Räcke, J Radhakrishnan
Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete …, 2008
Communication vs. computation
P Harsha, Y Ishai, J Kilian, K Nissim, S Venkatesh
computational complexity 16 (1), 1-33, 2007
Boolean functions on high-dimensional expanders
Y Dikstein, I Dinur, Y Filmus, P Harsha
arXiv preprint arXiv:1804.08155, 2018
Polynomially low error PCPs with polyloglog n queries via modular composition
I Dinur, P Harsha, G Kindler
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing …, 2015
Almost settling the hardness of noncommutative determinant
S Chien, P Harsha, A Sinclair, S Srinivasan
Proceedings of the forty-third annual ACM symposium on Theory of computing …, 2011
Rigid Matrices From Rectangular PCPs or: Hard Claims Have Complex Proofs
A Bhangale, P Harsha, O Paradise, A Tal
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS …, 2020
El sistema no puede realizar la operación en estos momentos. Inténtalo de nuevo más tarde.
Artículos 1–20