Fakultät für Informatik
-
Technische Universität München
Lehrstuhl für Effiziente Algorithmen
Die bibliographische Datenbank LEABib
Suchen
•
Liste der Journale
•
Liste der Serien
•
Liste der Konferenzen
•
Ausgewählte Publikationen
Hilfe
Suche: Author="Santhanam, Rahul"
Als [
bib
] [
pdf
] [
ps
] [
dvi
] [
xml
] herunterladen.
Permanent does not have succinct polynomial size arithmetic circuits of constant depth
Maurice Jansen
,
Rahul Santhanam
Information and Computation
222
, 2013, pp. 195-207
Stronger lower bounds and randomness-hardness trade-offs using associated algebraic complexity classes
Maurice Jansen
,
Rahul Santhanam
Leibniz International Proceedings in Informatics (LIPIcs)
14
, 2012, pp. 519-530
On the limits of sparsification
Rahul Santhanam
,
Srikanth Srinivasan
Lecture Notes in Computer Science
7391
, 2012, pp. 774-785
Exponential lower bounds for AC
^{\small\mbox{0}}
-Frege imply superpolynomial frege lower bounds
Yuval Filmus
,
Toniann Pitassi
,
Rahul Santhanam
Lecture Notes in Computer Science
6755
, 2011, pp. 618-629
Infeasibility of instance compression and succinct PCPs for
NP
Lance Fortnow
,
Rahul Santhanam
Journal of Computer and System Sciences
77
(1), 2011, pp. 91-106
Robust simulations and significant separations
Lance Fortnow
,
Rahul Santhanam
Lecture Notes in Computer Science
6755
, 2011, pp. 569-580
Permanent does not have succinct polynomial size arithmetic circuits of constant depth
Maurice Jansen
,
Rahul Santhanam
Lecture Notes in Computer Science
6755
, 2011, pp. 724-735
Branching programs for tree evaluation
Mark Braverman
,
Stephen Cook
,
Pierre McKenzie
,
Rahul Santhanam
,
Dustin Wehr
Lecture Notes in Computer Science
5734
, 2009, pp. 175-186
Fractional pebbling and thrifty branching programs
Mark Braverman
,
Cook Stephen
,
Pierre McKenzie
,
Rahul Santhanam
,
Dustin Wehr
Leibniz International Proceedings in Informatics (LIPIcs)
4
, 2009, pp. 109-120
Unconditional lower bounds against advice
Harry Buhrman
,
Lance Fortnow
,
Rahul Santhanam
Lecture Notes in Computer Science
5555
, 2009, pp. 195-209
Circuit lower bounds for Merlin-Arthur classes
Rahul Santhanam
SIAM Journal on Computing
39
(3), 2009, pp. 1038-1061
Infeasibility of instance compression and succinct PCPs for
NP
Lance Fortnow
,
Rahul Santhanam
Proceedings of the 40th International ACM Symposium on Theory of Computing, STOC'2008 (Victoria, BC, Canada, May 17-20, 2008)
, 2008, pp. 133-142
Circuit lower bounds for Merlin-Arthur classes
Rahul Santhanam
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, STOC'2007 (San Diego, CA, USA, June 11-13, 2007)
, 2007, pp. 275-283
Some results on average-case hardness within the polynomial hierarchy
A. Pavan
,
Rahul Santhanam
,
N.V. Vinodchandran
Lecture Notes in Computer Science
4337
, 2006, pp. 188-199
Hierarchies for semantic classes
Lance Fortnow
,
Rahul Santhanam
,
Luca Trevisan
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, STOC'2005 (Baltimore, Maryland, USA, May 22-24, 2005)
, 2005, pp. 348-355
Holographic proofs and derandomization
Dieter van Melkebeek
,
Rahul Santhanam
SIAM Journal on Computing
35
(1), 2005, pp. 59-90
Lower bounds on the complexity of recognizing SAT by Turing machines
Rahul Santhanam
Information Processing Letters
79
(5), 2001, pp. 243-247
On segregators, separators and time versus space
Rahul Santhanam
Technical Report (TR01-022), 2001
On separators, segregators and time versus space
Rahul Santhanam
Proceedings of the 16th Annual IEEE Conference on Computational Complexity (Chicago, Illinois, June 18-21, 2001)
, 2000, pp. 286-294