Rahul Santhanam
Rahul Santhanam
Dirección de correo verificada de cs.ox.ac.uk - Página principal
Título
Citado por
Citado por
Año
Infeasibility of instance compression and succinct PCPs for NP
L Fortnow, R Santhanam
Journal of Computer and System Sciences 77 (1), 91-106, 2011
3052011
Infeasibility of instance compression and succinct PCPs for NP
L Fortnow, R Santhanam
Journal of Computer and System Sciences 77 (1), 91-106, 2011
3052011
Fighting perebor: New and improved algorithms for formula and QBF satisfiability
R Santhanam
2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 183-192, 2010
772010
Hierarchy theorems for probabilistic polynomial time
L Fortnow, R Santhanam
45th Annual IEEE Symposium on Foundations of Computer Science, 316-324, 2004
622004
Circuit lower bounds for Merlin–Arthur classes
R Santhanam
SIAM Journal on Computing 39 (3), 1038-1061, 2009
612009
Graph model selection using maximum likelihood
I Bezáková, A Kalai, R Santhanam
Proceedings of the 23rd international conference on Machine learning, 105-112, 2006
402006
Graph model selection using maximum likelihood
I Bezáková, A Kalai, R Santhanam
Proceedings of the 23rd international conference on Machine learning, 105-112, 2006
402006
Conspiracies between learning algorithms, circuit lower bounds and pseudorandomness
IC Oliveira, R Santhanam
arXiv preprint arXiv:1611.01190, 2016
312016
Hierarchies for semantic classes
L Fortnow, R Santhanam, L Trevisan
Proceedings of the thirty-seventh annual ACM symposium on Theory of …, 2005
302005
On the average-case complexity of MCSP and its variants
S Hirahara, R Santhanam
32nd Computational Complexity Conference (CCC 2017), 2017
262017
Improved algorithms for sparse MAX-SAT and MAX-k-CSP
R Chen, R Santhanam
International Conference on Theory and Applications of Satisfiability …, 2015
242015
Robust simulations and significant separations
L Fortnow, R Santhanam
International Colloquium on Automata, Languages, and Programming, 569-580, 2011
24*2011
Average-case lower bounds and satisfiability algorithms for small threshold circuits
R Chen, R Santhanam, S Srinivasan
arXiv preprint arXiv:1806.06290, 2018
202018
Ironic complicity: Satisfiability algorithms and circuit lower bounds
R Santhanam
Bulletin of EATCS 1 (106), 2013
202013
On the limits of sparsification
R Santhanam, S Srinivasan
International Colloquium on Automata, Languages, and Programming, 774-785, 2012
192012
Pebbles and branching programs for tree evaluation
S Cook, P McKenzie, D Wehr, M Braverman, R Santhanam
ACM Transactions on Computation Theory (TOCT) 3 (2), 1-43, 2012
192012
On medium-uniformity and circuit lower bounds
R Santhanam, R Williams
2013 IEEE Conference on Computational Complexity, 15-23, 2013
182013
Hardness magnification for natural problems
IC Oliveira, R Santhanam
2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), 65-76, 2018
172018
Effectively Polynomial Simulations.
T Pitassi, R Santhanam
ICS, 370-382, 2010
172010
Fixed-polynomial size circuit bounds
L Fortnow, R Santhanam, R Williams
2009 24th Annual IEEE Conference on Computational Complexity, 19-26, 2009
172009
El sistema no puede realizar la operación en estos momentos. Inténtalo de nuevo más tarde.
Artículos 1–20