×

zbMATH — the first resource for mathematics

Santhanam, Rahul

Compute Distance To:
Author ID: santhanam.rahul Recent zbMATH articles by "Santhanam, Rahul"
Published as: Santhanam, R.; Santhanam, Rahul
Documents Indexed: 45 Publications since 1993

Publications by Year

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.68144
Fortnow, Lance; Santhanam, Rahul
69
2011
Infeasibility of instance compression and succinct PCPs for NP. Zbl 1231.68133
Fortnow, Lance; Santhanam, Rahul
32
2008
Circuit lower bounds for Merlin – Arthur classes. Zbl 1192.68302
Santhanam, Rahul
7
2009
On uniformity and circuit lower bounds. Zbl 1314.68139
Santhanam, Rahul; Williams, Ryan
5
2014
On the limits of sparsification. Zbl 1272.68161
Santhanam, Rahul; Srinivasan, Srikanth
5
2012
New non-uniform lower bounds for uniform classes. Zbl 1380.68196
Fortnow, Lance; Santhanam, Rahul
4
2016
Improved algorithms for sparse MAX-SAT and MAX-\(k\)-CSP. Zbl 06512563
Chen, Ruiwen; Santhanam, Rahul
4
2015
Ironic complicity: satisfiability algorithms and circuit lower bounds. Zbl 1261.68062
Santhanam, Rahul
4
2012
Robust simulations and significant separations. Zbl 1333.68118
Fortnow, Lance; Santhanam, Rahul
4
2011
Unconditional lower bounds against advice. Zbl 1248.68212
Buhrman, Harry; Fortnow, Lance; Santhanam, Rahul
4
2009
Circult lower bounds for Merlin-Arthur classes. Zbl 1232.68058
Santhanam, Rahul
4
2007
Stronger lower bounds and randomness-hardness trade-offs using associated algebraic complexity classes. Zbl 1245.68088
Jansen, Maurice; Santhanam, Rahul
3
2012
Permanent does not have succinct polynomial size arithmetic circuits of constant depth. Zbl 1333.68123
Jansen, Maurice; Santhanam, Rahul
3
2011
Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness. Zbl 1440.68083
Oliveira, Igor C.; Santhanam, Rahul
2
2017
On the average-case complexity of MCSP and its variants. Zbl 1435.68089
Hirahara, Shuichi; Santhanam, Rahul
2
2017
Robust simulations and significant separations. Zbl 1376.68049
Fortnow, Lance; Santhanam, Rahul
2
2017
Marginal hitting sets imply super-polynomial lower bounds for permanent. Zbl 1347.68161
Jansen, Maurice; Santhanam, Rahul
2
2012
Hierarchies for semantic classes (extended abstract). Zbl 1192.68292
Fortnow, Lance; Santhanam, Rahul; Trevisan, Luca
2
2005
Holographic proofs and derandomization. Zbl 1086.68044
van Melkebeek, Dieter; Santhanam, Rahul
2
2005
Average-case lower bounds and satisfiability algorithms for small threshold circuits. Zbl 1395.68138
Chen, Ruiwen; Santhanam, Rahul; Srinivasan, Srikanth
1
2018
Pseudodeterministic constructions in subexponential time. Zbl 1370.68326
Oliveira, Igor C.; Santhanam, Rahul
1
2017
Exponential time paradigms through the polynomial time lens. Zbl 1397.68097
Drucker, Andrew; Nederlof, Jesper; Santhanam, Rahul
1
2016
Average-case lower bounds and satisfiability algorithms for small threshold circuits. Zbl 1380.68191
Chen, Ruiwen; Santhanam, Rahul; Srinivasan, Srikanth
1
2016
Majority is incompressible by \(\mathrm{AC}^0[p]\) circuits. Zbl 1388.68063
Oliveira, Igor Carboni; Santhanam, Rahul
1
2015
Permanent does not have succinct polynomial size arithmetic circuits of constant depth. Zbl 1272.68137
Jansen, Maurice; Santhanam, Rahul
1
2013
Uniform derandomization from pathetic lower bounds. Zbl 1328.68079
Allender, Eric; Arvind, V.; Santhanam, Rahul; Wang, Fengming
1
2012
The complexity of explicit constructions. Zbl 1282.68178
Santhanam, Rahul
1
2012
Exponential lower bounds for \(\mathrm{AC}^{0}\)-Frege imply superpolynomial Frege lower bounds. Zbl 1280.03055
Filmus, Yuval; Pitassi, Toniann; Santhanam, Rahul
1
2011
Branching programs for tree evaluation. Zbl 1250.68106
Braverman, Mark; Cook, Stephen; McKenzie, Pierre; Santhanam, Rahul; Wehr, Dustin
1
2009
Some results on average-case hardness within the polynomial hierarchy. Zbl 1177.68096
Pavan, A.; Santhanam, Rahul; Vinodchandran, N. V.
1
2006
Graph splicing systems. Zbl 1095.68088
Santhanam, Rahul; Krithivasan, Kamala
1
2006
Cross boundary derivatives for transfinite triangular patches. Zbl 0852.68088
Foley, T. A.; Dayanand, S.; Santhanam, R.
1
1993
Average-case lower bounds and satisfiability algorithms for small threshold circuits. Zbl 1395.68138
Chen, Ruiwen; Santhanam, Rahul; Srinivasan, Srikanth
1
2018
Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness. Zbl 1440.68083
Oliveira, Igor C.; Santhanam, Rahul
2
2017
On the average-case complexity of MCSP and its variants. Zbl 1435.68089
Hirahara, Shuichi; Santhanam, Rahul
2
2017
Robust simulations and significant separations. Zbl 1376.68049
Fortnow, Lance; Santhanam, Rahul
2
2017
Pseudodeterministic constructions in subexponential time. Zbl 1370.68326
Oliveira, Igor C.; Santhanam, Rahul
1
2017
New non-uniform lower bounds for uniform classes. Zbl 1380.68196
Fortnow, Lance; Santhanam, Rahul
4
2016
Exponential time paradigms through the polynomial time lens. Zbl 1397.68097
Drucker, Andrew; Nederlof, Jesper; Santhanam, Rahul
1
2016
Average-case lower bounds and satisfiability algorithms for small threshold circuits. Zbl 1380.68191
Chen, Ruiwen; Santhanam, Rahul; Srinivasan, Srikanth
1
2016
Improved algorithms for sparse MAX-SAT and MAX-\(k\)-CSP. Zbl 06512563
Chen, Ruiwen; Santhanam, Rahul
4
2015
Majority is incompressible by \(\mathrm{AC}^0[p]\) circuits. Zbl 1388.68063
Oliveira, Igor Carboni; Santhanam, Rahul
1
2015
On uniformity and circuit lower bounds. Zbl 1314.68139
Santhanam, Rahul; Williams, Ryan
5
2014
Permanent does not have succinct polynomial size arithmetic circuits of constant depth. Zbl 1272.68137
Jansen, Maurice; Santhanam, Rahul
1
2013
On the limits of sparsification. Zbl 1272.68161
Santhanam, Rahul; Srinivasan, Srikanth
5
2012
Ironic complicity: satisfiability algorithms and circuit lower bounds. Zbl 1261.68062
Santhanam, Rahul
4
2012
Stronger lower bounds and randomness-hardness trade-offs using associated algebraic complexity classes. Zbl 1245.68088
Jansen, Maurice; Santhanam, Rahul
3
2012
Marginal hitting sets imply super-polynomial lower bounds for permanent. Zbl 1347.68161
Jansen, Maurice; Santhanam, Rahul
2
2012
Uniform derandomization from pathetic lower bounds. Zbl 1328.68079
Allender, Eric; Arvind, V.; Santhanam, Rahul; Wang, Fengming
1
2012
The complexity of explicit constructions. Zbl 1282.68178
Santhanam, Rahul
1
2012
Infeasibility of instance compression and succinct PCPs for NP. Zbl 1233.68144
Fortnow, Lance; Santhanam, Rahul
69
2011
Robust simulations and significant separations. Zbl 1333.68118
Fortnow, Lance; Santhanam, Rahul
4
2011
Permanent does not have succinct polynomial size arithmetic circuits of constant depth. Zbl 1333.68123
Jansen, Maurice; Santhanam, Rahul
3
2011
Exponential lower bounds for \(\mathrm{AC}^{0}\)-Frege imply superpolynomial Frege lower bounds. Zbl 1280.03055
Filmus, Yuval; Pitassi, Toniann; Santhanam, Rahul
1
2011
Circuit lower bounds for Merlin – Arthur classes. Zbl 1192.68302
Santhanam, Rahul
7
2009
Unconditional lower bounds against advice. Zbl 1248.68212
Buhrman, Harry; Fortnow, Lance; Santhanam, Rahul
4
2009
Branching programs for tree evaluation. Zbl 1250.68106
Braverman, Mark; Cook, Stephen; McKenzie, Pierre; Santhanam, Rahul; Wehr, Dustin
1
2009
Infeasibility of instance compression and succinct PCPs for NP. Zbl 1231.68133
Fortnow, Lance; Santhanam, Rahul
32
2008
Circult lower bounds for Merlin-Arthur classes. Zbl 1232.68058
Santhanam, Rahul
4
2007
Some results on average-case hardness within the polynomial hierarchy. Zbl 1177.68096
Pavan, A.; Santhanam, Rahul; Vinodchandran, N. V.
1
2006
Graph splicing systems. Zbl 1095.68088
Santhanam, Rahul; Krithivasan, Kamala
1
2006
Hierarchies for semantic classes (extended abstract). Zbl 1192.68292
Fortnow, Lance; Santhanam, Rahul; Trevisan, Luca
2
2005
Holographic proofs and derandomization. Zbl 1086.68044
van Melkebeek, Dieter; Santhanam, Rahul
2
2005
Cross boundary derivatives for transfinite triangular patches. Zbl 0852.68088
Foley, T. A.; Dayanand, S.; Santhanam, R.
1
1993
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

Citations by Year