Beame, Paul; Liew, Vincent; Pǎtraşcu, Mihai Finding the median (obliviously) with bounded space. (English) Zbl 1440.68346 Halldórsson, Magnús M. (ed.) et al., Automata, languages, and programming. 42nd international colloquium, ICALP 2015, Kyoto, Japan, July 6–10, 2015. Proceedings. Part I. Berlin: Springer. Lect. Notes Comput. Sci. 9134, 103-115 (2015). MSC: 68W40 68P05 68Q15 68Q17 PDFBibTeX XMLCite \textit{P. Beame} et al., Lect. Notes Comput. Sci. 9134, 103--115 (2015; Zbl 1440.68346) Full Text: DOI arXiv
Beame, Paul; Jayram, T. S.; Saks, Michael Time-space tradeoffs for branching programs. (English) Zbl 1052.68049 J. Comput. Syst. Sci. 63, No. 4, 542-572 (2001). MSC: 68Q15 68Q17 PDFBibTeX XMLCite \textit{P. Beame} et al., J. Comput. Syst. Sci. 63, No. 4, 542--572 (2001; Zbl 1052.68049) Full Text: DOI
Beame, Paul; Cook, Stephen; Edmonds, Jeff; Impagliazzo, Russell; Pitassi, Toniann The relative complexity of NP search problems. (English) Zbl 0920.68051 J. Comput. Syst. Sci. 57, No. 1, 3-19 (1998). MSC: 68Q15 PDFBibTeX XMLCite \textit{P. Beame} et al., J. Comput. Syst. Sci. 57, No. 1, 3--19 (1998; Zbl 0920.68051) Full Text: DOI
Beame, Paul; Fich, Faith E.; Sinha, Rakesh K. Separating the power of EREW and CREW PRAMs with small communication width. (English) Zbl 0889.68069 Inf. Comput. 138, No. 1, 89-99 (1997). MSC: 68W15 68Q15 PDFBibTeX XMLCite \textit{P. Beame} et al., Inf. Comput. 138, No. 1, 89--99 (1997; Zbl 0889.68069) Full Text: DOI
Beame, Paul; Pitassi, Toniann An exponential separation between the parity principle and the pigeonhole principle. (English) Zbl 0866.03029 Ann. Pure Appl. Logic 80, No. 3, 195-228 (1996). MSC: 03F20 68Q15 68Q25 PDFBibTeX XMLCite \textit{P. Beame} and \textit{T. Pitassi}, Ann. Pure Appl. Logic 80, No. 3, 195--228 (1996; Zbl 0866.03029) Full Text: DOI
Beame, Paul; Fich, Faith E.; Sinha, Rakesh K. Separating the power of EREW and CREW PRAMs with small communication width. (English) Zbl 1504.68072 Dehne, Frank (ed.) et al., Algorithms and data structures. 3rd workshop, WADS ’93. Montréal, Canada 11–13, 1993. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 709, 163-174 (1993). MSC: 68Q10 68Q25 PDFBibTeX XMLCite \textit{P. Beame} et al., Lect. Notes Comput. Sci. 709, 163--174 (1993; Zbl 1504.68072) Full Text: DOI
Pitassi, Toniann; Beame, Paul; Impagliazzo, Russell Exponential lower bounds for the pigeonhole principle. (English) Zbl 0784.03034 Comput. Complexity 3, No. 2, 97-140 (1993). Reviewer: P.Jančar (Ostrava) MSC: 03F20 68Q99 68R05 06E30 PDFBibTeX XMLCite \textit{T. Pitassi} et al., Comput. Complexity 3, No. 2, 97--140 (1993; Zbl 0784.03034) Full Text: DOI
Beame, Paul Limits on the power of concurrent-write parallel machines. (English) Zbl 0645.68060 Inf. Comput. 76, No. 1, 13-28 (1988). MSC: 68Q25 68N25 PDFBibTeX XMLCite \textit{P. Beame}, Inf. Comput. 76, No. 1, 13--28 (1988; Zbl 0645.68060) Full Text: DOI