Rahul 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
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