Seguir
Rahul Santhanam
Título
Citado por
Citado por
Ano
Infeasibility of instance compression and succinct PCPs for NP
L Fortnow, R Santhanam
Proceedings of the fortieth annual ACM symposium on Theory of computing, 133-142, 2008
3702008
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
962010
Circuit lower bounds for Merlin-Arthur classes
R Santhanam
Proceedings of the thirty-ninth annual ACM symposium on Theory of computing …, 2007
902007
Conspiracies between learning algorithms, circuit lower bounds and pseudorandomness
IC Oliveira, R Santhanam
arXiv preprint arXiv:1611.01190, 2016
722016
Hierarchy theorems for probabilistic polynomial time
L Fortnow, R Santhanam
45th Annual IEEE Symposium on Foundations of Computer Science, 316-324, 2004
702004
Hardness magnification for natural problems
IC Oliveira, R Santhanam
2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), 65-76, 2018
592018
On the average-case complexity of MCSP and its variants
S Hirahara, R Santhanam
32nd Computational Complexity Conference (CCC 2017), 2017
562017
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
542006
Hardness magnification near state-of-the-art lower bounds
IC Oliveira, J Pich, R Santhanam
Theory of Computing 17 (CCC 2019 Special Issue), 2021
502021
Average-case lower bounds and satisfiability algorithms for small threshold circuits
R Chen, R Santhanam, S Srinivasan
arXiv preprint arXiv:1806.06290, 2018
432018
Beyond natural proofs: Hardness magnification and locality
L Chen, S Hirahara, IC Oliveira, J Pich, N Rajgopal, R Santhanam
ACM Journal of the ACM (JACM) 69 (4), 1-49, 2022
412022
Pseudodeterministic constructions in subexponential time
IC Oliveira, R Santhanam
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing …, 2017
402017
Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP
R Chen, R Santhanam
International Conference on Theory and Applications of Satisfiability …, 2015
392015
Pseudorandomness and the minimum circuit size problem
R Santhanam
LIPIcs 151, 2020
372020
NP-hardness of minimum circuit size problem for OR-AND-MOD circuits
S Hirahara, I Oliveira, R Santhanam
33rd Computational Complexity Conference (CCC 2018) 102, 2018
362018
Robust simulations and significant separations
L Fortnow, R Santhanam
International Colloquium on Automata, Languages, and Programming, 569-580, 2011
35*2011
Hierarchies for semantic classes
L Fortnow, R Santhanam, L Trevisan
Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of …, 2005
352005
Effectively Polynomial Simulations.
T Pitassi, R Santhanam
ICS, 370-382, 2010
302010
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
292012
On medium-uniformity and circuit lower bounds
R Santhanam, R Williams
2013 IEEE Conference on Computational Complexity, 15-23, 2013
282013
O sistema não pode executar a operação agora. Tente novamente mais tarde.
Artigos 1–20