-
Notifications
You must be signed in to change notification settings - Fork 2
/
lowerbounds.bib
112 lines (96 loc) · 3.49 KB
/
lowerbounds.bib
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
%% This BibTeX bibliography file was created using BibDesk.
%% http://bibdesk.sourceforge.net/
%% Created for Jeff Erickson at 2017-09-22 10:12:21 +0900
%% Saved with string encoding Unicode (UTF-8)
@inproceedings{kpp-hlb3c-16,
Arxiv = {1407.6756},
Author = {Kopelowitz, Tsvi and Pettie, Seth and Porat, Ely},
Booktitle = {Proc 27th Ann. ACM-SIAM Symp. Discrete Algorithms},
Date-Added = {2017-09-22 01:09:43 +0000},
Date-Modified = {2017-09-22 01:11:44 +0000},
Doi = {10.1137/1.9781611974331.ch89},
Pages = {1272--1287},
Read = {1},
Title = {Higher Lower Bounds from the {3SUM} Conjecture},
Year = {2016}}
@inproceedings{p-tplbd-10,
Author = {Pătrașcu, Mihai},
Booktitle = {Proc. 42nd Ann. ACM Symp. Theory Comput.},
Date-Added = {2017-09-22 01:09:10 +0000},
Date-Modified = {2017-09-22 01:09:10 +0000},
Doi = {10.1145/1806689.1806772},
Pages = {603--610},
Read = {1},
Title = {Towards Polynomial Lower Bounds for Dynamic Problems},
Year = {2010},
Bdsk-Url-1 = {http://dx.doi.org/10.1145/1806689.1806772}}
@article{sy-lbadt-82,
Author = {Steele, J. Michael and Yao, Andrew Chi-Chih},
Date-Added = {2013-11-03 22:08:03 +0000},
Date-Modified = {2013-11-03 22:10:25 +0000},
Journal = {J. Algorithms},
Pages = {1--8},
Title = {Lower bounds for algebraic decision trees},
Volume = {3},
Year = {1982}}
@inproceedings{b-lbact-83,
Author = {Ben-Or, Michael},
Booktitle = {Proc. 15th Annu. ACM Sympos. Theory Comput.},
Date-Added = {2013-11-03 22:07:29 +0000},
Date-Modified = {2013-11-03 22:07:41 +0000},
Pages = {80--86},
Title = {Lower bounds for algebraic computation trees},
Year = {1983}}
@article{dl-ccvsp-79,
Author = {Dobkin, David P. and Lipton, Richard J.},
Date-Added = {2009-07-24 13:31:49 -0500},
Date-Modified = {2009-07-24 13:32:36 -0500},
Journal = {J. Comput. Syst. Sci.},
Pages = {86--91},
Title = {On the complexity of computations under varying sets of primitives},
Volume = {18},
Year = {1979}}
@article{s-clfch-82,
Author = {Snir, Marc},
Date-Added = {2009-07-24 13:30:15 -0500},
Date-Modified = {2009-07-24 13:30:58 -0500},
Journal = {Theoret. Comput. Sci.},
Pages = {321--330},
Title = {Comparisons between linear functions can help},
Volume = {19},
Year = {1982}}
@article{r-psplf-72,
Author = {Rabin, Michael O.},
Date-Added = {2009-07-24 13:27:05 -0500},
Date-Modified = {2009-07-24 13:27:51 -0500},
Journal = {J. Comput. Syst. Sci.},
Pages = {639--650},
Title = {Proving simultaneous positivity of linear forms},
Volume = {6},
Year = {1972}}
@article{v-pcp-75,
Author = {Valiant, Leslie},
Date-Added = {2009-07-24 13:12:27 -0500},
Date-Modified = {2009-07-24 13:12:27 -0500},
Journal = {SIAM J. Comput.},
Pages = {345--348},
Title = {Parallelism in comparison problems},
Volume = {4},
Year = {1975}}
@inproceedings{yar-olbsp-77,
Author = {Yao, Andrew C. and Avis, David M. and Rivest, Ronald L.},
Booktitle = {Proc. 9th Ann. ACM Symp. Theory Ccomput.},
Date-Added = {2009-07-24 13:10:26 -0500},
Date-Modified = {2009-07-24 13:11:40 -0500},
Pages = {11--17},
Title = {An {$\Omega(n^2 \log n)$} lower bound to the shortest paths problem},
Year = {1977},
Bdsk-Url-1 = {http://doi.acm.org/10.1145/800105.803391}}
@inproceedings{y-ccplf-75,
Author = {Yao, Andrew Chi-Chih},
Booktitle = {Proc. 16th IEEE Ann. Symp. Foundations Comput. Sci.},
Date-Added = {2009-07-24 13:05:46 -0500},
Date-Modified = {2009-07-24 13:07:51 -0500},
Pages = {85--89},
Title = {On the Complexity of Comparison Problems using Linear Functions (Preliminary Report)},
Year = {1975}}