×

Found 135 Documents (Results 1–100)

100
MathJax

\(O(\log^2 k/\log\log k)\)-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm. (English) Zbl 1433.68614

Charikar, Moses (ed.) et al., Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC ’19, Phoenix, AZ, USA, June 23–26, 2019. New York, NY: Association for Computing Machinery (ACM). 253-264 (2019).
PDF BibTeX XML Cite
Full Text: DOI arXiv

Another proof that \(\mathcal{BPP}\subseteq \mathcal{PH}\) (and more). (English) Zbl 1343.68085

Goldreich, Oded (ed.), Studies in complexity and cryptography. Miscellanea on the interplay between randomness and computation. In collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 40-53 (2011).
MSC:  68Q15
PDF BibTeX XML Cite
Full Text: DOI

The interaction between geometry and physics. (English) Zbl 1118.58002

Etingof, Pavel (ed.) et al., The unity of mathematics. In honor of the ninetieth birthday of I. M. Gelfand. Papers from the conference held in Cambridge, MA, USA, August 31–September 4, 2003. Boston, MA: Birkhäuser (ISBN 0-8176-4076-2/hbk). Progress in Mathematics 244, 1-15 (2006).
MSC:  58-02 53-02 81-02
PDF BibTeX XML Cite

On existentially first-order definable languages and their relation to NP. (English) Zbl 0917.68076

Larsen, Kim G. (ed.) et al., Automata, languages and programming. 25th international colloquium, ICALP ’98. Aalborg, Denmark, July 13–17, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1443, 17-28 (1998).
MSC:  68Q15 68Q45
PDF BibTeX XML Cite

Ranking arithmetic proofs by implicit ramification. (English) Zbl 0890.03034

Beame, Paul W. (ed.) et al., Proof complexity and feasible arithmetics. Papers from the DIMACS workshop, Rutgers, NJ, USA, April 21–24, 1996. Providence, RI: American Mathematical Society. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 39, 37-57 (1998).
PDF BibTeX XML Cite

On randomized versus deterministic computation. (English) Zbl 1420.68091

Lingas, Andrzej (ed.) et al., Automata, languages and programming. 20th international colloquium, ICALP 93, Lund, Sweden, July 5–9, 1993. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 700, 227-240 (1993).
MSC:  68Q15 68Q10 68Q25
PDF BibTeX XML Cite
Full Text: DOI

How intractable is the discrete logarithm for a general finite group? (English) Zbl 0801.68089

Rueppel, Rainer A. (ed.), Advances in cryptology – EUROCRYPT ’92. Workshop on the theory and applications of cryptographic techniques, Balatonfüred, Hungary, May 24-28, 1992. Proceedings. Berlin: Springer- Verlag. Lect. Notes Comput. Sci. 658, 420-428 (1993).
MSC:  68Q25 68W30 68P25 20B40
PDF BibTeX XML Cite

Filter Results by …

Document Type

Reviewing State

all top 5

Author

all top 5

Year of Publication

all top 3

Classification