Edit Profile Santhanam, Rahul Compute Distance To: Compute Author ID: santhanam.rahul Published as: Santhanam, R.; Santhanam, Rahul Documents Indexed: 45 Publications since 1993 all top 5 Co-Authors 6 single-authored 7 Fortnow, Lance J. 5 Chen, Ruiwen 5 Oliveira, Igor Carboni 4 Jansen, Maurice J. 3 Braverman, Mark 3 Cook, Stephen Arthur 3 McKenzie, Pierre 3 Srinivasan, Srikanth 3 Wehr, Dustin 2 Filmus, Yuval 2 Hirahara, Shuichi 2 Krithivasan, Kamala 2 Pitassi, Toniann 2 Williams, Richard Ryan 1 Allender, Eric W. 1 Arvind, Vikraman 1 Buhrman, Harry 1 Chakraborty, Chiranjit 1 Dayanand, S. 1 Drucker, Andrew 1 Foley, Thomas A. 1 McGregor, Andrew 1 Nederlof, Jesper 1 Pavan, Aduri 1 Trevisan, Luca 1 van Melkebeek, Dieter 1 Vinodchandran, N. Variyam 1 Wang, Fengming all top 5 Serials 3 SIAM Journal on Computing 2 Information and Computation 2 ACM Transactions on Computation Theory 1 Discrete Applied Mathematics 1 Information Processing Letters 1 Journal of Computer and System Sciences 1 Computational Complexity 1 Theory of Computing Systems 1 Bulletin of the European Association for Theoretical Computer Science EATCS 1 Philosophical Transactions of the Royal Society of London. Series A. Mathematical, Physical and Engineering Sciences 1 Theory of Computing all top 5 Fields 44 Computer science (68-XX) 6 Information and communication theory, circuits (94-XX) 4 Mathematical logic and foundations (03-XX) 3 Combinatorics (05-XX) 1 General and overarching topics; collections (00-XX) 1 Number theory (11-XX) 1 Linear and multilinear algebra; matrix theory (15-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH 32 Publications have been cited 173 times in 147 Documents Cited by ▼ Year ▼ Infeasibility of instance compression and succinct PCPs for NP. Zbl 1233.68144Fortnow, Lance; Santhanam, Rahul 69 2011 Infeasibility of instance compression and succinct PCPs for NP. Zbl 1231.68133Fortnow, Lance; Santhanam, Rahul 32 2008 Circuit lower bounds for Merlin – Arthur classes. Zbl 1192.68302Santhanam, Rahul 7 2009 On uniformity and circuit lower bounds. Zbl 1314.68139Santhanam, Rahul; Williams, Ryan 5 2014 On the limits of sparsification. Zbl 1272.68161Santhanam, Rahul; Srinivasan, Srikanth 5 2012 New non-uniform lower bounds for uniform classes. Zbl 1380.68196Fortnow, Lance; Santhanam, Rahul 4 2016 Improved algorithms for sparse MAX-SAT and MAX-\(k\)-CSP. Zbl 06512563Chen, Ruiwen; Santhanam, Rahul 4 2015 Ironic complicity: satisfiability algorithms and circuit lower bounds. Zbl 1261.68062Santhanam, Rahul 4 2012 Robust simulations and significant separations. Zbl 1333.68118Fortnow, Lance; Santhanam, Rahul 4 2011 Unconditional lower bounds against advice. Zbl 1248.68212Buhrman, Harry; Fortnow, Lance; Santhanam, Rahul 4 2009 Circult lower bounds for Merlin-Arthur classes. Zbl 1232.68058Santhanam, Rahul 4 2007 Stronger lower bounds and randomness-hardness trade-offs using associated algebraic complexity classes. Zbl 1245.68088Jansen, Maurice; Santhanam, Rahul 3 2012 Permanent does not have succinct polynomial size arithmetic circuits of constant depth. Zbl 1333.68123Jansen, Maurice; Santhanam, Rahul 3 2011 Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness. Zbl 1440.68083Oliveira, Igor C.; Santhanam, Rahul 2 2017 On the average-case complexity of MCSP and its variants. Zbl 1435.68089Hirahara, Shuichi; Santhanam, Rahul 2 2017 Robust simulations and significant separations. Zbl 1376.68049Fortnow, Lance; Santhanam, Rahul 2 2017 Marginal hitting sets imply super-polynomial lower bounds for permanent. Zbl 1347.68161Jansen, Maurice; Santhanam, Rahul 2 2012 Hierarchies for semantic classes (extended abstract). Zbl 1192.68292Fortnow, Lance; Santhanam, Rahul; Trevisan, Luca 2 2005 Holographic proofs and derandomization. Zbl 1086.68044van Melkebeek, Dieter; Santhanam, Rahul 2 2005 Average-case lower bounds and satisfiability algorithms for small threshold circuits. Zbl 1395.68138Chen, Ruiwen; Santhanam, Rahul; Srinivasan, Srikanth 1 2018 Pseudodeterministic constructions in subexponential time. Zbl 1370.68326Oliveira, Igor C.; Santhanam, Rahul 1 2017 Exponential time paradigms through the polynomial time lens. Zbl 1397.68097Drucker, Andrew; Nederlof, Jesper; Santhanam, Rahul 1 2016 Average-case lower bounds and satisfiability algorithms for small threshold circuits. Zbl 1380.68191Chen, Ruiwen; Santhanam, Rahul; Srinivasan, Srikanth 1 2016 Majority is incompressible by \(\mathrm{AC}^0[p]\) circuits. Zbl 1388.68063Oliveira, Igor Carboni; Santhanam, Rahul 1 2015 Permanent does not have succinct polynomial size arithmetic circuits of constant depth. Zbl 1272.68137Jansen, Maurice; Santhanam, Rahul 1 2013 Uniform derandomization from pathetic lower bounds. Zbl 1328.68079Allender, Eric; Arvind, V.; Santhanam, Rahul; Wang, Fengming 1 2012 The complexity of explicit constructions. Zbl 1282.68178Santhanam, Rahul 1 2012 Exponential lower bounds for \(\mathrm{AC}^{0}\)-Frege imply superpolynomial Frege lower bounds. Zbl 1280.03055Filmus, Yuval; Pitassi, Toniann; Santhanam, Rahul 1 2011 Branching programs for tree evaluation. Zbl 1250.68106Braverman, Mark; Cook, Stephen; McKenzie, Pierre; Santhanam, Rahul; Wehr, Dustin 1 2009 Some results on average-case hardness within the polynomial hierarchy. Zbl 1177.68096Pavan, A.; Santhanam, Rahul; Vinodchandran, N. V. 1 2006 Graph splicing systems. Zbl 1095.68088Santhanam, Rahul; Krithivasan, Kamala 1 2006 Cross boundary derivatives for transfinite triangular patches. Zbl 0852.68088Foley, T. A.; Dayanand, S.; Santhanam, R. 1 1993 Average-case lower bounds and satisfiability algorithms for small threshold circuits. Zbl 1395.68138Chen, Ruiwen; Santhanam, Rahul; Srinivasan, Srikanth 1 2018 Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness. Zbl 1440.68083Oliveira, Igor C.; Santhanam, Rahul 2 2017 On the average-case complexity of MCSP and its variants. Zbl 1435.68089Hirahara, Shuichi; Santhanam, Rahul 2 2017 Robust simulations and significant separations. Zbl 1376.68049Fortnow, Lance; Santhanam, Rahul 2 2017 Pseudodeterministic constructions in subexponential time. Zbl 1370.68326Oliveira, Igor C.; Santhanam, Rahul 1 2017 New non-uniform lower bounds for uniform classes. Zbl 1380.68196Fortnow, Lance; Santhanam, Rahul 4 2016 Exponential time paradigms through the polynomial time lens. Zbl 1397.68097Drucker, Andrew; Nederlof, Jesper; Santhanam, Rahul 1 2016 Average-case lower bounds and satisfiability algorithms for small threshold circuits. Zbl 1380.68191Chen, Ruiwen; Santhanam, Rahul; Srinivasan, Srikanth 1 2016 Improved algorithms for sparse MAX-SAT and MAX-\(k\)-CSP. Zbl 06512563Chen, Ruiwen; Santhanam, Rahul 4 2015 Majority is incompressible by \(\mathrm{AC}^0[p]\) circuits. Zbl 1388.68063Oliveira, Igor Carboni; Santhanam, Rahul 1 2015 On uniformity and circuit lower bounds. Zbl 1314.68139Santhanam, Rahul; Williams, Ryan 5 2014 Permanent does not have succinct polynomial size arithmetic circuits of constant depth. Zbl 1272.68137Jansen, Maurice; Santhanam, Rahul 1 2013 On the limits of sparsification. Zbl 1272.68161Santhanam, Rahul; Srinivasan, Srikanth 5 2012 Ironic complicity: satisfiability algorithms and circuit lower bounds. Zbl 1261.68062Santhanam, Rahul 4 2012 Stronger lower bounds and randomness-hardness trade-offs using associated algebraic complexity classes. Zbl 1245.68088Jansen, Maurice; Santhanam, Rahul 3 2012 Marginal hitting sets imply super-polynomial lower bounds for permanent. Zbl 1347.68161Jansen, Maurice; Santhanam, Rahul 2 2012 Uniform derandomization from pathetic lower bounds. Zbl 1328.68079Allender, Eric; Arvind, V.; Santhanam, Rahul; Wang, Fengming 1 2012 The complexity of explicit constructions. Zbl 1282.68178Santhanam, Rahul 1 2012 Infeasibility of instance compression and succinct PCPs for NP. Zbl 1233.68144Fortnow, Lance; Santhanam, Rahul 69 2011 Robust simulations and significant separations. Zbl 1333.68118Fortnow, Lance; Santhanam, Rahul 4 2011 Permanent does not have succinct polynomial size arithmetic circuits of constant depth. Zbl 1333.68123Jansen, Maurice; Santhanam, Rahul 3 2011 Exponential lower bounds for \(\mathrm{AC}^{0}\)-Frege imply superpolynomial Frege lower bounds. Zbl 1280.03055Filmus, Yuval; Pitassi, Toniann; Santhanam, Rahul 1 2011 Circuit lower bounds for Merlin – Arthur classes. Zbl 1192.68302Santhanam, Rahul 7 2009 Unconditional lower bounds against advice. Zbl 1248.68212Buhrman, Harry; Fortnow, Lance; Santhanam, Rahul 4 2009 Branching programs for tree evaluation. Zbl 1250.68106Braverman, Mark; Cook, Stephen; McKenzie, Pierre; Santhanam, Rahul; Wehr, Dustin 1 2009 Infeasibility of instance compression and succinct PCPs for NP. Zbl 1231.68133Fortnow, Lance; Santhanam, Rahul 32 2008 Circult lower bounds for Merlin-Arthur classes. Zbl 1232.68058Santhanam, Rahul 4 2007 Some results on average-case hardness within the polynomial hierarchy. Zbl 1177.68096Pavan, A.; Santhanam, Rahul; Vinodchandran, N. V. 1 2006 Graph splicing systems. Zbl 1095.68088Santhanam, Rahul; Krithivasan, Kamala 1 2006 Hierarchies for semantic classes (extended abstract). Zbl 1192.68292Fortnow, Lance; Santhanam, Rahul; Trevisan, Luca 2 2005 Holographic proofs and derandomization. Zbl 1086.68044van Melkebeek, Dieter; Santhanam, Rahul 2 2005 Cross boundary derivatives for transfinite triangular patches. Zbl 0852.68088Foley, T. A.; Dayanand, S.; Santhanam, R. 1 1993 all cited Publications top 5 cited Publications all top 5 Cited by 213 Authors 16 Saurabh, Saket 15 Kratsch, Stefan 12 Jansen, Bart M. P. 10 Cygan, Marek 8 Lokshtanov, Daniel 8 Pilipczuk, Marcin 8 Pilipczuk, Michał 7 Bodlaender, Hans L. 7 Hermelin, Danny 7 Misra, Neeldhara 6 Fellows, Michael Ralph 6 Raman, Venkatesh 6 Wahlström, Magnus 5 Fomin, Fedor V. 5 Fortnow, Lance J. 5 Santhanam, Rahul 5 Williams, Richard Ryan 4 Heggernes, Pinar 4 Müller, Moritz 4 Niedermeier, Rolf 4 Ramanujan, M. S. 4 Szeider, Stefan 3 Bredereck, Robert 3 Cai, Leizhen 3 Chen, Yijia 3 Dell, Holger 3 Downey, Rodney Graham 3 Fernau, Henning 3 Flum, Jörg 3 Hitchcock, John M. 3 Jonsson, Peter A. 3 Majumdar, Diptapriyo 3 Marx, Dániel 3 Panolan, Fahad 3 Paul, Christophe 3 Philip, Geevarghese 3 Rai, Ashutosh 3 Tamaki, Suguru 3 Van Leeuwen, Erik Jan 3 van ’t Hof, Pim 3 Villanger, Yngve 2 Allender, Eric W. 2 Basavaraju, Manu 2 Betzler, Nadja 2 Bonizzoni, Paola 2 Chini, Peter 2 Chopin, Morgan 2 Dondi, Riccardo 2 Drucker, Andrew 2 Fournier, Hervé 2 Ganian, Robert 2 Gaspers, Serge 2 Guillemot, Sylvain 2 Hartung, Sepp 2 Hirsch, Edward A. 2 Huang, Chien-Chung 2 Jansen, Maurice J. 2 Kawachi, Akinori 2 Kinne, Jeff 2 Lagerkvist, Victor 2 Meyer, Roland 2 Moser, Hannes 2 Nichterlein, André 2 Pavan, Aduri 2 Perez, Anthony 2 Pieterse, Astrid 2 Protti, Fábio 2 Rosamond, Frances A. 2 Rossmanith, Peter 2 Saivasan, Prakash 2 Sakai, Takayuki 2 Sau, Ignasi 2 Seto, Kazuhisa 2 Shaltiel, Ronen 2 Teruyama, Junichi 2 van Melkebeek, Dieter 2 Wojtaszczyk, Jakub Onufry 2 Wu, Xi 2 Ye, Junjie 1 Abramsky, Samson 1 Agarwal, Akanksha 1 Aghighi, Meysam 1 Agrawal, Akanksha 1 Ambalath, Abhimanyu M. 1 Applebaum, Benny 1 Araújo, Júlio César Silva 1 Artemenko, Sergei 1 Ashok, Pradeesha 1 Aydinlioǧlu, Bariş 1 Bäckström, Christer 1 Balasundaram, Radheshyam 1 Bang-Jensen, Jørgen 1 Banik, Aritra 1 Bazgan, Cristina 1 Berend, Daniel 1 Blin, Guillaume 1 Bliznets, Ivan A. 1 Bougeret, Marin 1 Bringmann, Karl 1 Bydžovský, Jan ...and 113 more Authors all top 5 Cited in 26 Serials 22 Algorithmica 16 Journal of Computer and System Sciences 14 Theoretical Computer Science 8 Theory of Computing Systems 6 Discrete Applied Mathematics 6 Information Processing Letters 6 Computational Complexity 5 SIAM Journal on Computing 4 SIAM Journal on Discrete Mathematics 4 ACM Transactions on Computation Theory 3 Artificial Intelligence 3 Information and Computation 2 Journal of the ACM 2 Discrete Optimization 1 Annals of Pure and Applied Logic 1 Computer Aided Geometric Design 1 Journal of Automated Reasoning 1 International Journal of Computer Mathematics 1 Archive for Mathematical Logic 1 Journal of Mathematical Sciences (New York) 1 Annals of Mathematics and Artificial Intelligence 1 Philosophical Transactions of the Royal Society of London. Series A. Mathematical, Physical and Engineering Sciences 1 Optimization Letters 1 Algorithms 1 Theory of Computing 1 Computer Science Review all top 5 Cited in 17 Fields 137 Computer science (68-XX) 56 Combinatorics (05-XX) 15 Information and communication theory, circuits (94-XX) 8 Operations research, mathematical programming (90-XX) 7 Mathematical logic and foundations (03-XX) 3 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 3 Biology and other natural sciences (92-XX) 2 History and biography (01-XX) 2 Linear and multilinear algebra; matrix theory (15-XX) 1 General and overarching topics; collections (00-XX) 1 Order, lattices, ordered algebraic structures (06-XX) 1 General algebraic systems (08-XX) 1 Commutative algebra (13-XX) 1 Algebraic geometry (14-XX) 1 Group theory and generalizations (20-XX) 1 Approximations and expansions (41-XX) 1 Numerical analysis (65-XX) Citations by Year