Google
Google Scholar
MS Academic
CiteSeerX
CORE
Semantic ScholarRahul Santhanam
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2010 – today
- 2019
[c42]Igor Carboni Oliveira, Rahul Santhanam, Roei Tell:
Expander-Based Cryptography Meets Natural Proofs. ITCS 2019: 18:1-18:14- 2018
- [j14]Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan:
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits. Theory of Computing 14(1): 1-55 (2018) - [c41]Igor Carboni Oliveira, Rahul Santhanam:
Pseudo-Derandomizing Learning and Approximation. APPROX-RANDOM 2018: 55:1-55:19 - [c40]Shuichi Hirahara, Igor Carboni Oliveira, Rahul Santhanam:
NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits. CCC 2018: 5:1-5:31 - [c39]Igor Carboni Oliveira, Rahul Santhanam:
Hardness Magnification for Natural Problems. FOCS 2018: 65-76 - [c38]Ruiwen Chen, Igor Carboni Oliveira, Rahul Santhanam:
An Average-Case Lower Bound Against \mathsf ACC^0 ACC 0. LATIN 2018: 317-330 - [c37]Ninad Rajgopal, Rahul Santhanam, Srikanth Srinivasan:
Deterministically Counting Satisfying Assignments for Constant-Depth Circuits with Parity Gates, with Implications for Lower Bounds. MFCS 2018: 78:1-78:15 - [i41]Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan:
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits. CoRR abs/1806.06290 (2018) - [i40]Albert Atserias, Jakob Nordström, Pavel Pudlák, Rahul Santhanam:
Proof Complexity (Dagstuhl Seminar 18051). Dagstuhl Reports 8(1): 124-157 (2018) - [i39]Shuichi Hirahara, Igor Carboni Oliveira, Rahul Santhanam:
NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits. Electronic Colloquium on Computational Complexity (ECCC) 25: 30 (2018) - [i38]Igor Carboni Oliveira, Rahul Santhanam:
Pseudo-derandomizing learning and approximation. Electronic Colloquium on Computational Complexity (ECCC) 25: 122 (2018) - [i37]Igor Carboni Oliveira, Rahul Santhanam:
Hardness Magnification for Natural Problems. Electronic Colloquium on Computational Complexity (ECCC) 25: 139 (2018) - [i36]Igor Carboni Oliveira, Ján Pich, Rahul Santhanam:
Hardness magnification near state-of-the-art lower bounds. Electronic Colloquium on Computational Complexity (ECCC) 25: 158 (2018) - [i35]Igor Carboni Oliveira, Rahul Santhanam, Roei Tell:
Expander-Based Cryptography Meets Natural Proofs. Electronic Colloquium on Computational Complexity (ECCC) 25: 159 (2018) - 2017
- [j13]Lance Fortnow, Rahul Santhanam:
Robust simulations and significant separations. Inf. Comput. 256: 149-159 (2017) - [c36]Shuichi Hirahara, Rahul Santhanam:
On the Average-Case Complexity of MCSP and Its Variants. Computational Complexity Conference 2017: 7:1-7:20 - [c35]Igor Carboni Oliveira, Rahul Santhanam:
Conspiracies Between Learning Algorithms, Circuit Lower Bounds, and Pseudorandomness. Computational Complexity Conference 2017: 18:1-18:49 - [c34]Igor Carboni Oliveira, Rahul Santhanam:
Pseudodeterministic constructions in subexponential time. STOC 2017: 665-677 - [i34]Igor Carboni Oliveira, Ruiwen Chen, Rahul Santhanam:
An Average-Case Lower Bound against ACC^0. Electronic Colloquium on Computational Complexity (ECCC) 24: 173 (2017) - 2016
- [j12]Andrew McGregor, Rahul Santhanam:
Special Section on the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC 2012). SIAM J. Comput. 45(4): 1448-1449 (2016) - [c33]Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan:
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits. Conference on Computational Complexity 2016: 1:1-1:35 - [c32]Lance Fortnow, Rahul Santhanam:
New Non-Uniform Lower Bounds for Uniform Classes. Conference on Computational Complexity 2016: 19:1-19:14 - [c31]Andrew Drucker, Jesper Nederlof, Rahul Santhanam:
Exponential Time Paradigms Through the Polynomial Time Lens. ESA 2016: 36:1-36:14 - [c30]
- [i33]Igor Carboni Oliveira, Rahul Santhanam:
Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness. CoRR abs/1611.01190 (2016) - [i32]Igor Carboni Oliveira, Rahul Santhanam:
Pseudodeterministic Constructions in Subexponential Time. CoRR abs/1612.01817 (2016) - [i31]Igor Carboni Oliveira, Rahul Santhanam:
Pseudodeterministic Constructions in Subexponential Time. Electronic Colloquium on Computational Complexity (ECCC) 23: 196 (2016) - [i30]Igor Carboni Oliveira, Rahul Santhanam:
Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness. Electronic Colloquium on Computational Complexity (ECCC) 23: 197 (2016) - 2015
- [j11]Yuval Filmus, Toniann Pitassi, Rahul Santhanam:
Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds. TOCT 7(2): 5:1-5:16 (2015) - [c29]Igor Carboni Oliveira, Rahul Santhanam:
Majority is Incompressible by AC^0[p] Circuits. Conference on Computational Complexity 2015: 124-157 - [c28]
- [c27]Rahul Santhanam, Richard Ryan Williams:
Beating Exhaustive Search for Quantified Boolean Formulas and Connections to Circuit Complexity. SODA 2015: 231-241 - [i29]Ruiwen Chen, Rahul Santhanam:
Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP. Electronic Colloquium on Computational Complexity (ECCC) 22: 112 (2015) - [i28]Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan:
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits. Electronic Colloquium on Computational Complexity (ECCC) 22: 191 (2015) - [i27]Ruiwen Chen, Rahul Santhanam:
Satisfiability on Mixed Instances. Electronic Colloquium on Computational Complexity (ECCC) 22: 192 (2015) - 2014
- [j10]Rahul Santhanam, Ryan Williams:
On Uniformity and Circuit Lower Bounds. Computational Complexity 23(2): 177-205 (2014) - [i26]Olaf Beyersdorff, Edward A. Hirsch, Jan Krajícek, Rahul Santhanam:
Optimal algorithms and proofs (Dagstuhl Seminar 14421). Dagstuhl Reports 4(10): 51-68 (2014) - [i25]Lance Fortnow, Rahul Santhanam:
Hierarchies Against Sublinear Advice. Electronic Colloquium on Computational Complexity (ECCC) 21: 171 (2014) - [i24]Igor Carboni Oliveira, Rahul Santhanam:
Majority is incompressible by AC0[p] circuits. Electronic Colloquium on Computational Complexity (ECCC) 21: 173 (2014) - 2013
- [j9]Maurice J. Jansen, Rahul Santhanam:
Permanent does not have succinct polynomial size arithmetic circuits of constant depth. Inf. Comput. 222: 195-207 (2013) - [c26]Rahul Santhanam, Ryan Williams:
On Medium-Uniformity and Circuit Lower Bounds. IEEE Conference on Computational Complexity 2013: 15-23 - [i23]Rahul Santhanam, Ryan Williams:
New Algorithms for QBF Satisfiability and Implications for Circuit Complexity. Electronic Colloquium on Computational Complexity (ECCC) 20: 108 (2013) - 2012
- [j8]Rahul Santhanam:
Ironic Complicity: Satisfiability Algorithms and Circuit Lower Bounds. Bulletin of the EATCS 106: 31-52 (2012) - [j7]Rahul Santhanam:
The Complexity of Explicit Constructions. Theory Comput. Syst. 51(3): 297-312 (2012) - [j6]Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam:
Pebbles and Branching Programs for Tree Evaluation. TOCT 3(2): 4:1-4:43 (2012) - [c25]Arkadev Chattopadhyay, Rahul Santhanam:
Lower Bounds on Interactive Compressibility by Constant-Depth Circuits. FOCS 2012: 619-628 - [c24]
- [c23]Maurice J. Jansen, Rahul Santhanam:
Marginal hitting sets imply super-polynomial lower bounds for permanent. ITCS 2012: 496-506 - [c22]Chiranjit Chakraborty, Rahul Santhanam:
Instance Compression for the Polynomial Hierarchy and beyond. IPEC 2012: 120-134 - [c21]Maurice J. Jansen, Rahul Santhanam:
Stronger Lower Bounds and Randomness-Hardness Trade-Offs Using Associated Algebraic Complexity Classes. STACS 2012: 519-530 - [i22]Subramanian Ramamoorthy, András Z. Salamon, Rahul Santhanam:
Macroscopes: models for collective decision making. CoRR abs/1204.3860 (2012) - [i21]Rahul Santhanam, Ryan Williams:
Uniform Circuits, Lower Bounds, and QBF Algorithms. Electronic Colloquium on Computational Complexity (ECCC) 19: 59 (2012) - [i20]Chiranjit Chakraborty, Rahul Santhanam:
Instance Compression for the Polynomial Hierarchy and Beyond. Electronic Colloquium on Computational Complexity (ECCC) 19: 77 (2012) - [i19]Rahul Santhanam:
Ironic Complicity: Satisfiability Algorithms and Circuit Lower Bounds. Electronic Colloquium on Computational Complexity (ECCC) 19: 84 (2012) - [i18]Arkadev Chattopadhyay, Rahul Santhanam:
Lower Bounds on Interactive Compressibility by Constant-Depth Circuits. Electronic Colloquium on Computational Complexity (ECCC) 19: 108 (2012) - 2011
- [j5]Lance Fortnow, Rahul Santhanam:
Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77(1): 91-106 (2011) - [c20]Lance Fortnow, Rahul Santhanam:
Robust Simulations and Significant Separations. ICALP (1) 2011: 569-580 - [c19]Yuval Filmus, Toniann Pitassi, Rahul Santhanam:
Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds. ICALP (1) 2011: 618-629 - [c18]Maurice J. Jansen, Rahul Santhanam:
Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth. ICALP (1) 2011: 724-735 - [i17]Rahul Santhanam, Srikanth Srinivasan:
On the Limits of Sparsification. Electronic Colloquium on Computational Complexity (ECCC) 18: 131 (2011) - [i16]Maurice J. Jansen, Rahul Santhanam:
Marginal Hitting Sets Imply Super-Polynomial Lower Bounds for Permanent. Electronic Colloquium on Computational Complexity (ECCC) 18: 133 (2011) - [i15]Maurice J. Jansen, Rahul Santhanam:
Stronger Lower Bounds and Randomness-Hardness Tradeoffs using Associated Algebraic Complexity Classes. Electronic Colloquium on Computational Complexity (ECCC) 18: 135 (2011) - 2010
- [c17]
- [c16]Rahul Santhanam:
Fighting Perebor: New and Improved Algorithms for Formula and QBF Satisfiability. FOCS 2010: 183-192 - [c15]
- [c14]
- [i14]Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam:
Pebbles and Branching Programs for Tree Evaluation. CoRR abs/1005.2642 (2010) - [i13]Lance Fortnow, Rahul Santhanam:
Robust Simulations and Significant Separations. CoRR abs/1012.2034 (2010)
2000 – 2009
- 2009
- [j4]Rahul Santhanam:
Circuit Lower Bounds for Merlin--Arthur Classes. SIAM J. Comput. 39(3): 1038-1061 (2009) - [c13]Lance Fortnow, Rahul Santhanam, Ryan Williams:
Fixed-Polynomial Size Circuit Bounds. IEEE Conference on Computational Complexity 2009: 19-26 - [c12]Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr:
Fractional Pebbling and Thrifty Branching Programs. FSTTCS 2009: 109-120 - [c11]Harry Buhrman, Lance Fortnow, Rahul Santhanam:
Unconditional Lower Bounds against Advice. ICALP (1) 2009: 195-209 - [c10]Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr:
Branching Programs for Tree Evaluation. MFCS 2009: 175-186 - [i12]Harry Buhrman, Lance Fortnow, Rahul Santhanam:
Unconditional Lower Bounds against Advice. Algebraic Methods in Computational Complexity 2009 - [i11]
- [i10]Harry Buhrman, Lance Fortnow, Rahul Santhanam:
Unconditional Lower Bounds against Advice. Electronic Colloquium on Computational Complexity (ECCC) 16: 64 (2009) - 2008
- [c9]Lance Fortnow, Rahul Santhanam:
Infeasibility of instance compression and succinct PCPs for NP. STOC 2008: 133-142 - 2007
- [c8]
- [i9]Lance Fortnow, Rahul Santhanam:
Time Hierarchies: A Survey. Electronic Colloquium on Computational Complexity (ECCC) 14(004) (2007) - [i8]Rahul Santhanam:
Circuit Lower Bounds for Merlin-Arthur Classes. Electronic Colloquium on Computational Complexity (ECCC) 14(005) (2007) - [i7]Lance Fortnow, Rahul Santhanam:
Infeasibility of Instance Compression and Succinct PCPs for NP. Electronic Colloquium on Computational Complexity (ECCC) 14(096) (2007) - 2006
- [j3]Rahul Santhanam, Kamala Krithivasan:
Graph splicing systems. Discrete Applied Mathematics 154(8): 1264-1278 (2006) - [c7]Joshua Buresh-Oppenheim, Rahul Santhanam:
Making Hard Problems Harder. IEEE Conference on Computational Complexity 2006: 73-87 - [c6]Aduri Pavan, Rahul Santhanam, N. V. Vinodchandran:
Some Results on Average-Case Hardness Within the Polynomial Hierarchy. FSTTCS 2006: 188-199 - [c5]Ivona Bezáková, Adam Kalai, Rahul Santhanam:
Graph model selection using maximum likelihood. ICML 2006: 105-112 - [i6]Joshua Buresh-Oppenheim, Rahul Santhanam:
Making Hard Problems Harder. Electronic Colloquium on Computational Complexity (ECCC)(003) (2006) - [i5]Joshua Buresh-Oppenheim, Valentine Kabanets, Rahul Santhanam:
Uniform Hardness Amplification in NP via Monotone Codes. Electronic Colloquium on Computational Complexity (ECCC) 13(154) (2006) - [i4]Lance Fortnow, Rahul Santhanam:
Fixed-Polynomial Size Circuit Bounds. Electronic Colloquium on Computational Complexity (ECCC) 13(157) (2006) - 2005
- [j2]Dieter van Melkebeek, Rahul Santhanam:
Holographic Proofs and Derandmization. SIAM J. Comput. 35(1): 59-90 (2005) - [c4]
- 2004
- [c3]Lance Fortnow, Rahul Santhanam:
Hierarchy Theorems for Probabilistic Polynomial Time. FOCS 2004: 316-324 - [i3]Lance Fortnow, Rahul Santhanam, Luca Trevisan:
Promise Hierarchies. Electronic Colloquium on Computational Complexity (ECCC)(098) (2004) - 2003
- [c2]Rahul Santhanam, Dieter van Melkebeek:
Holographic Proofs and Derandomization. IEEE Conference on Computational Complexity 2003: 269-283 - 2002
- [i2]Rahul Santhanam:
Resource Tradeoffs and Derandomization. Electronic Colloquium on Computational Complexity (ECCC)(038) (2002) - 2001
- [j1]Rahul Santhanam:
Lower bounds on the complexity of recognizing SAT by Turing machines. Inf. Process. Lett. 79(5): 243-247 (2001) - [c1]Rahul Santhanam:
On Separators, Segregators and Time versus Space. IEEE Conference on Computational Complexity 2001: 286-294 - [i1]Rahul Santhanam:
On segregators, separators and time versus space. Electronic Colloquium on Computational Complexity (ECCC) 8(22) (2001)
Coauthor Index
maintained by 
, founded at 
, founded at 
last updated on 2019-01-29 23:43 CET by the dblp team
data released under the ODC-BY 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
the dblp computer science bibliography is funded by:
