Prasad Jayanti
- AAD+93.Y. A!;?k, H. Attiya, D. Dolev, E. Gafni, M. Merritt, and N. Shavit. Atomic snapshots of sh~red memory. Journal of the A CM, 40(4):873-890, September 1993. Google Scholar
Digital Library
- Asp90.J. Aspnes. Time and space efficient randomized consensus, in Proceedings of the 9th A CM Symposium on Principles of Distributed Computing, 1990. Google ScholarDigital Library
- FHS93.F. Fich, M. Herlihy, ~nd N. Shavit. On the sp~ce complexity of randomized synchronization. In Proceedings of the 12th Annual Symposium on Principles of Distributed Computing, pages 241-249, August 1993. Google ScholarDigital Library
- HW90.M.P. Hertihy ~nd J.M. Wing. Linearizability: A correctness condition for concurrent objects. A CM TOPLAS, 12(3):463-492, 1990. Google ScholarDigital Library
- JTT96.P. Jayanti, K. Tan, and S. Toueg. Time and space lower bounds for non-blocking implementations. Technical report, Department of Computer Science, Cornell University, 1996. Also available by anonymous ftp from ftp. cs. cornell, edu in pub/j ayan~;i/podc96, ps.Google Scholar
Index Terms
- Time and space lower bounds for non-blocking implementations (preliminary version)
Recommendations
Kernelization Lower Bounds Through Colors and IDs
In parameterized complexity, each problem instance comes with a parameter k, and a parameterized problem is said to admit a polynomial kernel if there are polynomial time preprocessing rules that reduce the input instance to an instance with size ...
Lower bounds on kernelization
Preprocessing (data reduction or kernelization) to reduce instance size is one of the most commonly deployed heuristics in the implementation practice to tackle computationally hard problems. However, a systematic theoretical study of them has remained ...
Exponential lower bounds for AC0-Frege imply superpolynomial frege lower bounds
ICALP'11: Proceedings of the 38th international colloquim conference on Automata, languages and programming - Volume Part IWe give a general transformation which turns polynomialsize Frege proofs to subexponential-size AC0-Frege proofs. This indicates that proving exponential lower bounds for AC0-Frege is hard, since it is a longstanding open problem to prove super-...
Comments