Cai, Jin-Yi; Watanabe, Osamu Random access to advice strings and collapsing results. (English) Zbl 1100.68026 Algorithmica 46, No. 1, 43-57 (2006). MSC: 68Q05 68Q15 PDFBibTeX XMLCite \textit{J.-Y. Cai} and \textit{O. Watanabe}, Algorithmica 46, No. 1, 43--57 (2006; Zbl 1100.68026) Full Text: DOI
Cai, Jin-Yi; Watanabe, Osamu Relativized collapsing between BPP and PH under stringent oracle access. (English) Zbl 1178.68271 Inf. Process. Lett. 90, No. 3, 147-154 (2004). MSC: 68Q15 PDFBibTeX XMLCite \textit{J.-Y. Cai} and \textit{O. Watanabe}, Inf. Process. Lett. 90, No. 3, 147--154 (2004; Zbl 1178.68271) Full Text: DOI
Cai, Jin-Yi; Watanabe, Osamu Random access to advice strings and collapsing results. (English) Zbl 1116.68445 Fleischer, Rudolf (ed.) et al., Algorithms and computation. 15th international symposium, ISAAC 2004, Hong Kong, China, December 20–22, 2004. Proceedings. Berlin: Springer (ISBN 3-540-24131-0/pbk). Lecture Notes in Computer Science 3341, 209-220 (2004). MSC: 68Q05 68Q15 PDFBibTeX XMLCite \textit{J.-Y. Cai} and \textit{O. Watanabe}, Lect. Notes Comput. Sci. 3341, 209--220 (2004; Zbl 1116.68445) Full Text: DOI
Cai, Jin-Yi; Watanabe, Osamu On proving circuit lower bounds against the polynomial-time hierarchy. (English) Zbl 1105.68041 SIAM J. Comput. 33, No. 4, 984-1009 (2004). MSC: 68Q15 68Q17 PDFBibTeX XMLCite \textit{J.-Y. Cai} and \textit{O. Watanabe}, SIAM J. Comput. 33, No. 4, 984--1009 (2004; Zbl 1105.68041) Full Text: DOI
Cai, Jin-Yi; Watanabe, Osamu On proving circuit lower bounds against the polynomial-time hierarchy: positive and negative results. (English) Zbl 1276.68080 Warnow, Tandy (ed.) et al., Computing and combinatorics. 9th annual international conference, COCOON 2003, Big Sky, MT, USA, July 25–28, 2003. Proceedings. Berlin: Springer (ISBN 3-540-40534-8/pbk). Lecture Notes in Computer Science 2697, 202-211 (2003). MSC: 68Q17 68Q15 PDFBibTeX XMLCite \textit{J.-Y. Cai} and \textit{O. Watanabe}, Lect. Notes Comput. Sci. 2697, 202--211 (2003; Zbl 1276.68080) Full Text: DOI
Cai, Jin-Yi; Watanabe, Osamu Stringent relativization. (English) Zbl 1205.68163 Pandya, Paritosh K. (ed.) et al., FST TCS 2003: Foundations of software technology and theoretical computer science. 23rd conference, Mumbai, India, December 15–17, 2003. Proceedings. Berlin: Springer (ISBN 3-540-20680-9/pbk). Lect. Notes Comput. Sci. 2914, 408-419 (2003). MSC: 68Q15 PDFBibTeX XMLCite \textit{J.-Y. Cai} and \textit{O. Watanabe}, Lect. Notes Comput. Sci. 2914, 408--419 (2003; Zbl 1205.68163) Full Text: DOI