ask others

Rahul Santhanam

> Home > Persons

Refine list

refinements active!

zoomed in on ?? of ?? records

view refined list in

showing all ?? records

2010 – today

see FAQ

What is the meaning of the colors in the publication lists?

2018
[c41]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/approx/OliveiraS18
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/approx/OliveiraS18
Igor Carboni Oliveira, Rahul Santhanam:
Pseudo-Derandomizing Learning and Approximation. APPROX-RANDOM 2018: 55:1-55:19
[c40]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/coco/HiraharaOS18
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/coco/HiraharaOS18
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]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/focs/OliveiraS18
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/focs/OliveiraS18
Igor Carboni Oliveira, Rahul Santhanam:
Hardness Magnification for Natural Problems. FOCS 2018: 65-76
[c38]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/latin/ChenOS18
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/latin/ChenOS18
Ruiwen Chen, Igor Carboni Oliveira, Rahul Santhanam:
An Average-Case Lower Bound Against \mathsf ACC^0 ACC 0. LATIN 2018: 317-330
[c37]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/mfcs/RajgopalS018
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/mfcs/RajgopalS018
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]
- view
  - electronic edition @ arxiv.org
- export record
  dblp key:
  - journals/corr/abs-1806-06290
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/corr/abs-1806-06290
Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan:
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits. CoRR abs/1806.06290 (2018)
[i40]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/dagstuhl-reports/AtseriasNPS18
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/dagstuhl-reports/AtseriasNPS18
Albert Atserias, Jakob Nordström, Pavel Pudlák, Rahul Santhanam:
Proof Complexity (Dagstuhl Seminar 18051). Dagstuhl Reports 8(1): 124-157 (2018)
[i39]
- view
  - electronic edition @ weizmann.ac.il
- export record
  dblp key:
  - journals/eccc/HiraharaOS18
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/HiraharaOS18
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]
- view
  - electronic edition @ weizmann.ac.il
- export record
  dblp key:
  - journals/eccc/OliveiraS18
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/OliveiraS18
Igor Carboni Oliveira, Rahul Santhanam:
Pseudo-derandomizing learning and approximation. Electronic Colloquium on Computational Complexity (ECCC) 25: 122 (2018)
[i37]
- view
  - electronic edition @ weizmann.ac.il
- export record
  dblp key:
  - journals/eccc/OliveiraS18a
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/OliveiraS18a
Igor Carboni Oliveira, Rahul Santhanam:
Hardness Magnification for Natural Problems. Electronic Colloquium on Computational Complexity (ECCC) 25: 139 (2018)
[i36]
- view
  - electronic edition @ weizmann.ac.il
- export record
  dblp key:
  - journals/eccc/OliveiraPS18
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/OliveiraPS18
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]
- view
  - electronic edition @ weizmann.ac.il
- export record
  dblp key:
  - journals/eccc/OliveiraST18
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/OliveiraST18
Igor Carboni Oliveira, Rahul Santhanam, Roei Tell:
Expander-Based Cryptography Meets Natural Proofs. Electronic Colloquium on Computational Complexity (ECCC) 25: 159 (2018)
2017
[j13]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/iandc/FortnowS17
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/iandc/FortnowS17
Lance Fortnow, Rahul Santhanam:
Robust simulations and significant separations. Inf. Comput. 256: 149-159 (2017)
[c36]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/coco/HiraharaS17
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/coco/HiraharaS17
Shuichi Hirahara, Rahul Santhanam:
On the Average-Case Complexity of MCSP and Its Variants. Computational Complexity Conference 2017: 7:1-7:20
[c35]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/coco/OliveiraS17
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/coco/OliveiraS17
Igor Carboni Oliveira, Rahul Santhanam:
Conspiracies Between Learning Algorithms, Circuit Lower Bounds, and Pseudorandomness. Computational Complexity Conference 2017: 18:1-18:49
[c34]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/stoc/OliveiraS17
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/stoc/OliveiraS17
Igor Carboni Oliveira, Rahul Santhanam:
Pseudodeterministic constructions in subexponential time. STOC 2017: 665-677
[i34]
- view
  - electronic edition @ weizmann.ac.il
- export record
  dblp key:
  - journals/eccc/OliveiraCS17
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/OliveiraCS17
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]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/siamcomp/McGregorS16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/siamcomp/McGregorS16
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]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/coco/ChenSS16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/coco/ChenSS16
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]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/coco/FortnowS16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/coco/FortnowS16
Lance Fortnow, Rahul Santhanam:
New Non-Uniform Lower Bounds for Uniform Classes. Conference on Computational Complexity 2016: 19:1-19:14
[c31]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/esa/DruckerNS16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/esa/DruckerNS16
Andrew Drucker, Jesper Nederlof, Rahul Santhanam:
Exponential Time Paradigms Through the Polynomial Time Lens. ESA 2016: 36:1-36:14
[c30]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/innovations/ChenS16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/innovations/ChenS16
Ruiwen Chen, Rahul Santhanam:
Satisfiability on Mixed Instances. ITCS 2016: 393-402
[i33]
- view
  - electronic edition @ arxiv.org
- export record
  dblp key:
  - journals/corr/OliveiraS16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/corr/OliveiraS16
Igor Carboni Oliveira, Rahul Santhanam:
Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness. CoRR abs/1611.01190 (2016)
[i32]
- view
  - electronic edition @ arxiv.org
- export record
  dblp key:
  - journals/corr/OliveiraS16a
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/corr/OliveiraS16a
Igor Carboni Oliveira, Rahul Santhanam:
Pseudodeterministic Constructions in Subexponential Time. CoRR abs/1612.01817 (2016)
[i31]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/OliveiraS16
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/OliveiraS16
Igor Carboni Oliveira, Rahul Santhanam:
Pseudodeterministic Constructions in Subexponential Time. Electronic Colloquium on Computational Complexity (ECCC) 23: 196 (2016)
[i30]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/OliveiraS16a
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/OliveiraS16a
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]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/toct/FilmusPS15
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/toct/FilmusPS15
Yuval Filmus, Toniann Pitassi, Rahul Santhanam:
Exponential Lower Bounds for AC⁰-Frege Imply Superpolynomial Frege Lower Bounds. TOCT 7(2): 5:1-5:16 (2015)
[c29]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/coco/OliveiraS15
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/coco/OliveiraS15
Igor Carboni Oliveira, Rahul Santhanam:
Majority is Incompressible by AC^0[p] Circuits. Conference on Computational Complexity 2015: 124-157
[c28]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/sat/ChenS15
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/sat/ChenS15
Ruiwen Chen, Rahul Santhanam:
Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP. SAT 2015: 33-45
[c27]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/soda/SanthanamW15
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/soda/SanthanamW15
Rahul Santhanam, Richard Ryan Williams:
Beating Exhaustive Search for Quantified Boolean Formulas and Connections to Circuit Complexity. SODA 2015: 231-241
[i29]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ChenS15
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ChenS15
Ruiwen Chen, Rahul Santhanam:
Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP. Electronic Colloquium on Computational Complexity (ECCC) 22: 112 (2015)
[i28]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ChenSS15
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ChenSS15
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]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ChenS15a
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ChenS15a
Ruiwen Chen, Rahul Santhanam:
Satisfiability on Mixed Instances. Electronic Colloquium on Computational Complexity (ECCC) 22: 192 (2015)
2014
[j10]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/cc/SanthanamW14
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/cc/SanthanamW14
Rahul Santhanam, Ryan Williams:
On Uniformity and Circuit Lower Bounds. Computational Complexity 23(2): 177-205 (2014)
[i26]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/dagstuhl-reports/BeyersdorffHKS14
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/dagstuhl-reports/BeyersdorffHKS14
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]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/FortnowS14
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/FortnowS14
Lance Fortnow, Rahul Santhanam:
Hierarchies Against Sublinear Advice. Electronic Colloquium on Computational Complexity (ECCC) 21: 171 (2014)
[i24]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/OliveiraS14
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/OliveiraS14
Igor Carboni Oliveira, Rahul Santhanam:
Majority is incompressible by AC⁰[p] circuits. Electronic Colloquium on Computational Complexity (ECCC) 21: 173 (2014)
2013
[j9]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/iandc/JansenS13
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/iandc/JansenS13
Maurice J. Jansen, Rahul Santhanam:
Permanent does not have succinct polynomial size arithmetic circuits of constant depth. Inf. Comput. 222: 195-207 (2013)
[c26]
- view
  - electronic edition via DOI
  - electronic edition @ ieeecomputersociety.org
- export record
  dblp key:
  - conf/coco/SanthanamW13
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/coco/SanthanamW13
Rahul Santhanam, Ryan Williams:
On Medium-Uniformity and Circuit Lower Bounds. IEEE Conference on Computational Complexity 2013: 15-23
[i23]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/SanthanamW13
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/SanthanamW13
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]
- view
  - electronic edition @ eatcs.org
- export record
  dblp key:
  - journals/eatcs/Santhanam12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eatcs/Santhanam12
Rahul Santhanam:
Ironic Complicity: Satisfiability Algorithms and Circuit Lower Bounds. Bulletin of the EATCS 106: 31-52 (2012)
[j7]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/mst/Santhanam12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/mst/Santhanam12
Rahul Santhanam:
The Complexity of Explicit Constructions. Theory Comput. Syst. 51(3): 297-312 (2012)
[j6]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/toct/CookMWBS12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/toct/CookMWBS12
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]
- view
  - electronic edition via DOI
  - electronic edition @ ieeecomputersociety.org
- export record
  dblp key:
  - conf/focs/ChattopadhyayS12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/focs/ChattopadhyayS12
Arkadev Chattopadhyay, Rahul Santhanam:
Lower Bounds on Interactive Compressibility by Constant-Depth Circuits. FOCS 2012: 619-628
[c24]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/icalp/SanthanamS12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/icalp/SanthanamS12
Rahul Santhanam, Srikanth Srinivasan:
On the Limits of Sparsification. ICALP (1) 2012: 774-785
[c23]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/innovations/JansenS12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/innovations/JansenS12
Maurice J. Jansen, Rahul Santhanam:
Marginal hitting sets imply super-polynomial lower bounds for permanent. ITCS 2012: 496-506
[c22]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/iwpec/ChakrabortyS12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/iwpec/ChakrabortyS12
Chiranjit Chakraborty, Rahul Santhanam:
Instance Compression for the Polynomial Hierarchy and beyond. IPEC 2012: 120-134
[c21]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/stacs/JansenS12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/stacs/JansenS12
Maurice J. Jansen, Rahul Santhanam:
Stronger Lower Bounds and Randomness-Hardness Trade-Offs Using Associated Algebraic Complexity Classes. STACS 2012: 519-530
[i22]
- view
  - electronic edition @ arxiv.org
- export record
  dblp key:
  - journals/corr/abs-1204-3860
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/corr/abs-1204-3860
Subramanian Ramamoorthy, András Z. Salamon, Rahul Santhanam:
Macroscopes: models for collective decision making. CoRR abs/1204.3860 (2012)
[i21]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/SanthanamW12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/SanthanamW12
Rahul Santhanam, Ryan Williams:
Uniform Circuits, Lower Bounds, and QBF Algorithms. Electronic Colloquium on Computational Complexity (ECCC) 19: 59 (2012)
[i20]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ChakrabortyS12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ChakrabortyS12
Chiranjit Chakraborty, Rahul Santhanam:
Instance Compression for the Polynomial Hierarchy and Beyond. Electronic Colloquium on Computational Complexity (ECCC) 19: 77 (2012)
[i19]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Santhanam12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Santhanam12
Rahul Santhanam:
Ironic Complicity: Satisfiability Algorithms and Circuit Lower Bounds. Electronic Colloquium on Computational Complexity (ECCC) 19: 84 (2012)
[i18]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ChattopadhyayS12
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ChattopadhyayS12
Arkadev Chattopadhyay, Rahul Santhanam:
Lower Bounds on Interactive Compressibility by Constant-Depth Circuits. Electronic Colloquium on Computational Complexity (ECCC) 19: 108 (2012)
2011
[j5]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/jcss/FortnowS11
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/jcss/FortnowS11
Lance Fortnow, Rahul Santhanam:
Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77(1): 91-106 (2011)
[c20]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/icalp/FortnowS11
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/icalp/FortnowS11
Lance Fortnow, Rahul Santhanam:
Robust Simulations and Significant Separations. ICALP (1) 2011: 569-580
[c19]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/icalp/FilmusPS11
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/icalp/FilmusPS11
Yuval Filmus, Toniann Pitassi, Rahul Santhanam:
Exponential Lower Bounds for AC⁰-Frege Imply Superpolynomial Frege Lower Bounds. ICALP (1) 2011: 618-629
[c18]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/icalp/JansenS11
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/icalp/JansenS11
Maurice J. Jansen, Rahul Santhanam:
Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth. ICALP (1) 2011: 724-735
[i17]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/SanthanamS11
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/SanthanamS11
Rahul Santhanam, Srikanth Srinivasan:
On the Limits of Sparsification. Electronic Colloquium on Computational Complexity (ECCC) 18: 131 (2011)
[i16]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/JansenS11
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/JansenS11
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]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/JansenS11a
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/JansenS11a
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]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/cie/Santhanam10
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/cie/Santhanam10
Rahul Santhanam:
The Complexity of Explicit Constructions. CiE 2010: 372-375
[c16]
- view
  - electronic edition via DOI
  - electronic edition @ ieeecomputersociety.org
- export record
  dblp key:
  - conf/focs/Santhanam10
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/focs/Santhanam10
Rahul Santhanam:
Fighting Perebor: New and Improved Algorithms for Formula and QBF Satisfiability. FOCS 2010: 183-192
[c15]
- view
  - electronic edition @ tsinghua.edu.cn
- export record
  dblp key:
  - conf/innovations/FortnowS10
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/innovations/FortnowS10
Lance Fortnow, Rahul Santhanam:
Bounding Rationality by Discounting Time. ICS 2010: 143-155
[c14]
- view
  - electronic edition @ tsinghua.edu.cn
- export record
  dblp key:
  - conf/innovations/PitassiS10
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/innovations/PitassiS10
Toniann Pitassi, Rahul Santhanam:
Effectively Polynomial Simulations. ICS 2010: 370-382
[i14]
- view
  - electronic edition @ arxiv.org
- export record
  dblp key:
  - journals/corr/abs-1005-2642
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/corr/abs-1005-2642
Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam:
Pebbles and Branching Programs for Tree Evaluation. CoRR abs/1005.2642 (2010)
[i13]
- view
  - electronic edition @ arxiv.org
- export record
  dblp key:
  - journals/corr/abs-1012-2034
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/corr/abs-1012-2034
Lance Fortnow, Rahul Santhanam:
Robust Simulations and Significant Separations. CoRR abs/1012.2034 (2010)

2000 – 2009

see FAQ

What is the meaning of the colors in the publication lists?

2009
[j4]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/siamcomp/Santhanam09
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/siamcomp/Santhanam09
Rahul Santhanam:
Circuit Lower Bounds for Merlin--Arthur Classes. SIAM J. Comput. 39(3): 1038-1061 (2009)
[c13]
- view
  - electronic edition via DOI
  - electronic edition @ ieeecomputersociety.org
- export record
  dblp key:
  - conf/coco/FortnowSW09
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/coco/FortnowSW09
Lance Fortnow, Rahul Santhanam, Ryan Williams:
Fixed-Polynomial Size Circuit Bounds. IEEE Conference on Computational Complexity 2009: 19-26
[c12]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/fsttcs/BravermanCMSW09
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/fsttcs/BravermanCMSW09
Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr:
Fractional Pebbling and Thrifty Branching Programs. FSTTCS 2009: 109-120
[c11]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/icalp/BuhrmanFS09
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/icalp/BuhrmanFS09
Harry Buhrman, Lance Fortnow, Rahul Santhanam:
Unconditional Lower Bounds against Advice. ICALP (1) 2009: 195-209
[c10]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/mfcs/BravermanCMSW09
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/mfcs/BravermanCMSW09
Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr:
Branching Programs for Tree Evaluation. MFCS 2009: 175-186
[i12]
- view
  - electronic edition @ dagstuhl.de
- export record
  dblp key:
  - conf/dagstuhl/BuhrmanFS09
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/dagstuhl/BuhrmanFS09
Harry Buhrman, Lance Fortnow, Rahul Santhanam:
Unconditional Lower Bounds against Advice. Algebraic Methods in Computational Complexity 2009
[i11]
- view
  - electronic edition @ arxiv.org
- export record
  dblp key:
  - journals/corr/abs-0911-3162
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/corr/abs-0911-3162
Lance Fortnow, Rahul Santhanam:
Bounding Rationality by Discounting Time. CoRR abs/0911.3162 (2009)
[i10]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/BuhrmanFS09
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/BuhrmanFS09
Harry Buhrman, Lance Fortnow, Rahul Santhanam:
Unconditional Lower Bounds against Advice. Electronic Colloquium on Computational Complexity (ECCC) 16: 64 (2009)
2008
[c9]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/stoc/FortnowS08
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/stoc/FortnowS08
Lance Fortnow, Rahul Santhanam:
Infeasibility of instance compression and succinct PCPs for NP. STOC 2008: 133-142
2007
[c8]
- view
  - electronic edition via DOI
  - electronic edition @ wikidata.org
- export record
  dblp key:
  - conf/stoc/Santhanam07
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/stoc/Santhanam07
Rahul Santhanam:
Circuit lower bounds for Merlin-Arthur classes. STOC 2007: 275-283
[i9]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/FortnowS07
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/FortnowS07
Lance Fortnow, Rahul Santhanam:
Time Hierarchies: A Survey. Electronic Colloquium on Computational Complexity (ECCC) 14(004) (2007)
[i8]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Santhanam07
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Santhanam07
Rahul Santhanam:
Circuit Lower Bounds for Merlin-Arthur Classes. Electronic Colloquium on Computational Complexity (ECCC) 14(005) (2007)
[i7]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/FortnowS07a
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/FortnowS07a
Lance Fortnow, Rahul Santhanam:
Infeasibility of Instance Compression and Succinct PCPs for NP. Electronic Colloquium on Computational Complexity (ECCC) 14(096) (2007)
2006
[j3]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/dam/SanthanamK06
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/dam/SanthanamK06
Rahul Santhanam, Kamala Krithivasan:
Graph splicing systems. Discrete Applied Mathematics 154(8): 1264-1278 (2006)
[c7]
- view
  - electronic edition via DOI
  - electronic edition @ ieeecomputersociety.org
- export record
  dblp key:
  - conf/coco/Buresh-OppenheimS06
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/coco/Buresh-OppenheimS06
Joshua Buresh-Oppenheim, Rahul Santhanam:
Making Hard Problems Harder. IEEE Conference on Computational Complexity 2006: 73-87
[c6]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/fsttcs/PavanSV06
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/fsttcs/PavanSV06
Aduri Pavan, Rahul Santhanam, N. V. Vinodchandran:
Some Results on Average-Case Hardness Within the Polynomial Hierarchy. FSTTCS 2006: 188-199
[c5]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/icml/BezakovaKS06
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/icml/BezakovaKS06
Ivona Bezáková, Adam Kalai, Rahul Santhanam:
Graph model selection using maximum likelihood. ICML 2006: 105-112
[i6]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ECCC-TR06-003
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ECCC-TR06-003
Joshua Buresh-Oppenheim, Rahul Santhanam:
Making Hard Problems Harder. Electronic Colloquium on Computational Complexity (ECCC)(003) (2006)
[i5]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/Buresh-OppenheimKS06
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/Buresh-OppenheimKS06
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]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/FortnowS06
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/FortnowS06
Lance Fortnow, Rahul Santhanam:
Fixed-Polynomial Size Circuit Bounds. Electronic Colloquium on Computational Complexity (ECCC) 13(157) (2006)
2005
[j2]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/siamcomp/MelkebeekS05
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/siamcomp/MelkebeekS05
Dieter van Melkebeek, Rahul Santhanam:
Holographic Proofs and Derandmization. SIAM J. Comput. 35(1): 59-90 (2005)
[c4]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - conf/stoc/FortnowST05
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/stoc/FortnowST05
Lance Fortnow, Rahul Santhanam, Luca Trevisan:
Hierarchies for semantic classes. STOC 2005: 348-355
2004
[c3]
- view
- export record
  dblp key:
  - conf/focs/FortnowS04
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/focs/FortnowS04
Lance Fortnow, Rahul Santhanam:
Hierarchy Theorems for Probabilistic Polynomial Time. FOCS 2004: 316-324
[i3]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ECCC-TR04-098
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ECCC-TR04-098
Lance Fortnow, Rahul Santhanam, Luca Trevisan:
Promise Hierarchies. Electronic Colloquium on Computational Complexity (ECCC)(098) (2004)
2003
[c2]
- view
  - electronic edition @ ieeecomputersociety.org
- export record
  dblp key:
  - conf/coco/SanthanamM03
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/coco/SanthanamM03
Rahul Santhanam, Dieter van Melkebeek:
Holographic Proofs and Derandomization. IEEE Conference on Computational Complexity 2003: 269-283
2002
[i2]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ECCC-TR02-038
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ECCC-TR02-038
Rahul Santhanam:
Resource Tradeoffs and Derandomization. Electronic Colloquium on Computational Complexity (ECCC)(038) (2002)
2001
[j1]
- view
  - electronic edition via DOI
- export record
  dblp key:
  - journals/ipl/Santhanam01
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/ipl/Santhanam01
Rahul Santhanam:
Lower bounds on the complexity of recognizing SAT by Turing machines. Inf. Process. Lett. 79(5): 243-247 (2001)
[c1]
- view
  - electronic edition via DOI
  - electronic edition @ ieeecomputersociety.org
- export record
  dblp key:
  - conf/coco/Santhanam01
- ask others
- share record
  short URL:
  - https://dblp.org/rec/conf/coco/Santhanam01
Rahul Santhanam:
On Separators, Segregators and Time versus Space. IEEE Conference on Computational Complexity 2001: 286-294
[i1]
- view
  - electronic edition @ hpi-web.de
- export record
  dblp key:
  - journals/eccc/ECCC-TR01-022
- ask others
- share record
  short URL:
  - https://dblp.org/rec/journals/eccc/ECCC-TR01-022
Rahul Santhanam:
On segregators, separators and time versus space. Electronic Colloquium on Computational Complexity (ECCC) 8(22) (2001)

Coauthor Index

see FAQ

maintained by

at