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="Pavan, A."
Als [
bib
] [
pdf
] [
ps
] [
dvi
] [
xml
] herunterladen.
New time-space upperbounds for directed reachability in high-genus and
H
-minor-free graphs
Diptarka Chakraborty
,
A. Pavan
,
Raghunath Tewari
,
N.V. Vinodchandran
,
Lin Forrest Yang
Leibniz International Proceedings in Informatics (LIPIcs)
29
, 2014, pp. 585-595
Separating Cook completeness from Karp-Levin completeness under a worst-case hardness hypothesis
Debasis Mandal
,
A. Pavan
,
Rajeswari Venugopalan
Leibniz International Proceedings in Informatics (LIPIcs)
29
, 2014, pp. 445-456
Length-increasing reductions for PSPACE-completeness
John M. Hitchcock
,
A. Pavan
Lecture Notes in Computer Science
8087
, 2013, pp. 540-550
Collapsing and separating completeness notions under average-case and worst-case hypotheses
Xiaoyang Gu
,
John M. Hitchcock
,
A. Pavan
Theory of Computing Systems
51
(2), 2012, pp. 248-265
A thirty year old conjecture about promise problems
Andrew Hughes
,
A. Pavan
,
Nathan Russell
,
Alan Selman
Lecture Notes in Computer Science
7391
, 2012, pp. 473-484
Extracting Kolmogorov complexity with applications to dimension zero-one laws
Lance Fortnow
,
John M. Hitchcock
,
A. Pavan
,
N.V. Vinodchandran
,
Fengming Wang
Information and Computation
209
(4), 2011, pp. 627-636
Unions of disjoint NP-complete sets
Christian Glaßer
,
John M. Hitchcock
,
A. Pavan
,
Stephen Travers
Lecture Notes in Computer Science
6842
, 2011, pp. 240-251
The fault tolerance of NP-hard problems
Christian Glaßer
,
A. Pavan
,
Stephen Travers
Information and Computation
209
(3), 2011, pp. 443-455
Proving SAT does not have small circuits with an application to the two queries problem
Lance Fortnow
,
A. Pavan
,
Samik Sengupta
Journal of Computer and System Sciences
74
(3), 2008, pp. 358-363
Splitting
NP
-complete sets
Christian Glaßer
,
A. Pavan
,
Alan L. Selman
,
Liyu Zhang
SIAM Journal on Computing
37
(5), 2008, pp. 1517-1535
Partial bi-immunity, scaled dimension, and
NP
-completeness
John M. Hitchcock
,
A. Pavan
,
N.V. Vinodchandran
Theory of Computing Systems
42
(2), 2008, pp. 131-142
Relations between average-case and worst-case complexity
A. Pavan
,
N.V. Vinodchandran
Theory of Computing Systems
42
(4), 2008, pp. 596-607
Autoreducibility, mitoticity, and immunity
Christian Glaßer
,
Mitsunori Ogihara
,
A. Pavan
,
Alan L. Selman
,
Liyu Zhang
Journal of Computer and System Sciences
73
(5), 2007, pp. 735-754
Strong reductions and isomorphism of complete sets
Ryan C. Harkins
,
John M. Hitchcock
,
A. Pavan
Lecture Notes in Computer Science
4855
, 2007, pp. 168-178
Comparing reductions to
NP
-complete sets
John M. Hitchcock
,
A. Pavan
Information and Computation
205
(5), 2007, pp. 694-706
Polylogarithmic-round interactive proofs for
coNP
collapse the exponential hierarchy
A. Pavan
,
Alan L. Selman
,
Samik Sengupta
,
N.V. Vinodchandran
Theoretical Computer Science
385
(1-3), 2007, pp. 167-178
Range-efficient counting of distinct elements in a massive data stream
A. Pavan
,
Srikanta Tirthapura
SIAM Journal on Computing
37
(2), 2007, pp. 359-379
Robustness of
P
SPACE-complete sets
A. Pavan
,
Fengming Wang
Information Processing Letters
103
(3), 2007, pp. 102-104
Extracting Kolmogorov complexity with applications to dimension zero-one laws
Lance Fortnow
,
John M. Hitchcock
,
A. Pavan
,
N.V. Vinodchandran
,
Fengming Wang
Lecture Notes in Computer Science
4051
, 2006, pp. 335-345
Properties of
NP
-complete sets
Christian Glaßer
,
A. Pavan
,
Alan L. Selman
,
Samik Sengupta
SIAM Journal on Computing
36
(2), 2006, pp. 516-542
Comparing reductions to
NP
-complete sets
John M. Hitchcock
,
A. Pavan
Lecture Notes in Computer Science
4051
, 2006, pp. 465-476
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
Some results on derandomization
Harry Buhrman
,
Lance Fortnow
,
A. Pavan
Theory of Computing Systems
38
(2), 2005, pp. 211-227
Autoreducibility, mitoticity, and immunity
Christian Glaßer
,
Mitsunori Ogihara
,
A. Pavan
,
Alan L. Selman
,
Liyu Zhang
Lecture Notes in Computer Science
3618
, 2005, pp. 387-398
Resource-bounded strong dimension versus resource-bounded category
John M. Hitchcock
,
A. Pavan
Information Processing Letters
95
(3), 2005, pp. 377-381
Seiten 1
2
>