Rahul Santhanam
Rahul Santhanam
Verified email at cs.ox.ac.uk - Homepage
Title
Cited by
Cited by
Year
Infeasibility of instance compression and succinct PCPs for NP
L Fortnow, R Santhanam
Journal of Computer and System Sciences 77 (1), 91-106, 2011
3352011
Infeasibility of instance compression and succinct PCPs for NP
L Fortnow, R Santhanam
Journal of Computer and System Sciences 77 (1), 91-106, 2011
3352011
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
862010
Circuit lower bounds for Merlin–Arthur classes
R Santhanam
SIAM Journal on Computing 39 (3), 1038-1061, 2009
692009
Hierarchy theorems for probabilistic polynomial time
L Fortnow, R Santhanam
45th Annual IEEE Symposium on Foundations of Computer Science, 316-324, 2004
652004
Conspiracies between learning algorithms, circuit lower bounds and pseudorandomness
IC Oliveira, R Santhanam
arXiv preprint arXiv:1611.01190, 2016
482016
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
442006
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
442006
Average-case lower bounds and satisfiability algorithms for small threshold circuits
R Chen, R Santhanam, S Srinivasan
arXiv preprint arXiv:1806.06290, 2018
342018
On the average-case complexity of MCSP and its variants
S Hirahara, R Santhanam
32nd Computational Complexity Conference (CCC 2017), 2017
342017
Hierarchies for semantic classes
L Fortnow, R Santhanam, L Trevisan
Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of†…, 2005
322005
Robust simulations and significant separations
L Fortnow, R Santhanam
International Colloquium on Automata, Languages, and Programming, 569-580, 2011
31*2011
Improved algorithms for sparse MAX-SAT and MAX-k-CSP
R Chen, R Santhanam
International Conference on Theory and Applications of Satisfiability†…, 2015
302015
Hardness magnification for natural problems
IC Oliveira, R Santhanam
2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), 65-76, 2018
292018
Effectively Polynomial Simulations.
T Pitassi, R Santhanam
ICS, 370-382, 2010
262010
Hardness magnification near state-of-the-art lower bounds
IC Oliveira, J Pich, R Santhanam
34th Computational Complexity Conference (CCC 2019), 2019
252019
Pseudodeterministic constructions in subexponential time
IC Oliveira, R Santhanam
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing†…, 2017
232017
Fixed-polynomial size circuit bounds
L Fortnow, R Santhanam, R Williams
2009 24th Annual IEEE Conference on Computational Complexity, 19-26, 2009
232009
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
222012
Ironic complicity: Satisfiability algorithms and circuit lower bounds
R Santhanam
Bulletin of EATCS 1 (106), 2013
212013
The system can't perform the operation now. Try again later.
Articles 1–20