@conference {15620,
	title = {Tight lower bounds for halfspace range searching},
	booktitle = {Proceedings of the 2010 annual symposium on Computational geometry},
	series = {SoCG {\textquoteright}10},
	year = {2010},
	month = {2010///},
	pages = {29 - 37},
	publisher = {ACM},
	organization = {ACM},
	address = {New York, NY, USA},
	abstract = {We establish two new lower bounds for the halfspace range searching problem: Given a set of n points in ℜd, where each point is associated with a weight from a commutative semigroup, compute the semigroup sum of the weights of the points lying within any query halfspace. Letting $m$ denote the space requirements, we prove a lower bound for general semigroups of Ω(n1-1/(d+1)/m1/(d+1)) and for integral semigroups of Ω(n/m1/d). Our lower bounds are proved in the semigroup arithmetic model. Neglecting logarithmic factors, our result for integral semigroups matches the best known upper bound due to Matou{\v s}ek. Our result for general semigroups improves upon the best known lower bound due to Br{\"o}nnimann, Chazelle, and Pach. Moreover, Fonseca and Mount have recently shown that, given uniformly distributed points, halfspace range queries over idempotent semigroups can be answered in O(n1-1/(d+1)/m1/(d+1)) time in the semigroup arithmetic model. As our lower bounds are established for uniformly distributed point sets, it follows that they also resolve the computational complexity of halfspace range searching over idempotent semigroups in this important special case.},
	keywords = {Idempotence, lower bounds, Range searching},
	isbn = {978-1-4503-0016-2},
	doi = {10.1145/1810959.1810964},
	url = {http://doi.acm.org/10.1145/1810959.1810964},
	author = {Arya,Sunil and Mount, Dave and Xia,Jian}
}
@conference {15146,
	title = {Lower bounds on the efficiency of encryption and digital signature schemes},
	booktitle = {Proceedings of the thirty-fifth annual ACM symposium on Theory of computing},
	series = {STOC {\textquoteright}03},
	year = {2003},
	month = {2003///},
	pages = {417 - 425},
	publisher = {ACM},
	organization = {ACM},
	address = {New York, NY, USA},
	abstract = {A central focus of modern cryptography is to investigate the weakest possible assumptions under which various cryptographic algorithms exist. Typically, a proof that a "weak" primitive (e.g., a one-way function) implies the existence of a "strong" algorithm (e.g., a private-key encryption scheme) proceeds by giving an explicit construction of the latter from the former. In addition to showing the existence of such a construction, an equally important research direction is to explore the efficiency of such constructions.Among the most fundamental cryptographic algorithms are digital signature schemes and schemes for public- or private-key encryption. Here, we show the first lower bounds on the efficiency of any encryption or signature construction based on black-box access to one-way or trapdoor one-way permutations. If S is the assumed security of the permutation π (i.e., no adversary of size S can invert π on a fraction larger than 1/S of its inputs), our results show that:Any public-key encryption scheme for m-bit messages must query π at least Ω(m log S) times.Any private-key encryption scheme for m-bit messages (with k-bit keys) must query π at least Ω(m-k/log S) times.Any signature verification algorithm for m-bit messages must query π at least Ω(m log S) times.Our bounds match known upper bounds for the case of encryption.We prove our results in an extension of the Impagliazzo-Rudich model. That is, we show that any black-box construction beating our lower bounds would imply the unconditional existence of a one-way function.},
	keywords = {black-box, digital signatures, encryption, lower bounds},
	isbn = {1-58113-674-9},
	doi = {10.1145/780542.780604},
	url = {http://doi.acm.org/10.1145/780542.780604},
	author = {Gennaro,Rosario and Gertner,Yael and Katz, Jonathan}
}
@article {14997,
	title = {On the difficulty of Manhattan channel routing},
	journal = {Information Processing Letters},
	volume = {44},
	year = {1992},
	month = {1992/12/21/},
	pages = {281 - 284},
	abstract = {We show that channel routing in the Manhattan model remains difficult even when all nets are single-sided. Given a set of n single-sided nets, we consider the problem of determining the minimum number of tracks required to obtain a dogleg-free routing. In addition to showing that the decision version of the problem isNP-complete, we show that there are problems requiring at least d+Ω(n) tracks, where d is the density. This existential lower bound does not follow from any of the known lower bounds in the literature.},
	keywords = {combinatorial problems, computational complexity, lower bounds, VLSI channel routing},
	isbn = {0020-0190},
	doi = {10.1016/0020-0190(92)90214-G},
	url = {http://www.sciencedirect.com/science/article/pii/002001909290214G},
	author = {Greenberg,Ronald and JaJa, Joseph F. and Krishnamurthy,Sridhar}
}
