×

Found 259 Documents (Results 1–100)

Quantum cryptography in Algorithmica. (English) Zbl 07844696

Saha, Barna (ed.) et al., Proceedings of the 55th annual ACM SIGACT symposium on theory of computing, STOC ’23, Orlando, FL, USA, June 20–23, 2023. New York, NY: Association for Computing Machinery (ACM). 1589-1602 (2023).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Hard languages in NP \(\cap\) coNP and NIZK proofs from unstructured hardness. (English) Zbl 07844668

Saha, Barna (ed.) et al., Proceedings of the 55th annual ACM SIGACT symposium on theory of computing, STOC ’23, Orlando, FL, USA, June 20–23, 2023. New York, NY: Association for Computing Machinery (ACM). 1243-1256 (2023).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics. (English) Zbl 07844598

Saha, Barna (ed.) et al., Proceedings of the 55th annual ACM SIGACT symposium on theory of computing, STOC ’23, Orlando, FL, USA, June 20–23, 2023. New York, NY: Association for Computing Machinery (ACM). 391-404 (2023).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Endemic oblivious transfer via random oracles, revisited. (English) Zbl 1530.94049

Hazay, Carmit (ed.) et al., Advances in cryptology – EUROCRYPT 2023. 42nd annual international conference on the theory and applications of cryptographic techniques, Lyon, France, April 23–27, 2023. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 14004, 303-329 (2023).
MSC:  94A60
PDFBibTeX XMLCite
Full Text: DOI

Fine-grained non-interactive key-exchange: constructions and lower bounds. (English) Zbl 1530.94015

Hazay, Carmit (ed.) et al., Advances in cryptology – EUROCRYPT 2023. 42nd annual international conference on the theory and applications of cryptographic techniques, Lyon, France, April 23–27, 2023. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 14004, 55-85 (2023).
MSC:  94A60
PDFBibTeX XMLCite
Full Text: DOI

Almost shortest paths with near-additive error in weighted graphs. (English) Zbl 07853695

Czumaj, Artur (ed.) et al., 18th Scandinavian symposium and workshops on algorithm theory, SWAT 2022, Tórshavn, Faroe Islands, June 27–29, 2022. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 227, Article 23, 22 p. (2022).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Fixed-parameter sensitivity oracles. (English) Zbl 07829255

Braverman, Mark (ed.), 13th innovations in theoretical computer science conference, ITCS 2022, Berkeley, CA, USA, January 31 – February 3, 2022. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 215, Article 23, 18 p. (2022).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Maintaining exact distances under multiple edge failures. (English) Zbl 07774402

Leonardi, Stefano (ed.) et al., Proceedings of the 54th annual ACM SIGACT symposium on theory of computing, STOC ’22, Rome, Italy June 20–24, 2022. New York, NY: Association for Computing Machinery (ACM). 1093-1101 (2022).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

How much randomness is needed to convert MA protocols to AM protocols? (English) Zbl 07615747

Kulikov, Alexander S. (ed.) et al., Computer science – theory and applications. 17th international computer science symposium in Russia, CSR 2022, virtual event, June 29 – July 1, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13296, 338-349 (2022).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

A unified approach for all pairs approximate shortest paths in weighted undirected graphs. (English) Zbl 07740859

Mutzel, Petra (ed.) et al., 29th annual European symposium on algorithms. ESA 2021, Lisbon, Portugal (virtual conference), September 6–8, 2021. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 204, Article 4, 18 p. (2021).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

Acyclicity programming for sigma-protocols. (English) Zbl 1512.94055

Nissim, Kobbi (ed.) et al., Theory of cryptography. 19th international conference, TCC 2021, Raleigh, NC, USA, November 8–11, 2021. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 13042, 435-465 (2021).
MSC:  94A60 68P25
PDFBibTeX XMLCite
Full Text: DOI

An efficient oracle for counting shortest paths in planar graphs. (English) Zbl 1502.68227

Wu, Weili (ed.) et al., Algorithmic aspects in information and management. 15th international conference, AAIM 2021, virtual event, December 20–22, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13153, 406-417 (2021).
MSC:  68R10 05C10 68P05
PDFBibTeX XMLCite
Full Text: DOI

Demystifying Pythia: a survey of ChainLink oracles usage on Ethereum. (English) Zbl 1492.91451

Bernhard, Matthew (ed.) et al., Financial cryptography and data security. FC 2021 international workshops. Codecfin, DeFi, VOTING, and WTSC, virtual event, March 5, 2021. Revised selected papers. Berlin: Springer. Lect. Notes Comput. Sci. 12676, 115-123 (2021).
MSC:  91G99 94A60
PDFBibTeX XMLCite
Full Text: DOI arXiv

Lattice reduction with approximate enumeration oracles. Practical algorithms and concrete performance. (English) Zbl 1486.94075

Malkin, Tal (ed.) et al., Advances in cryptology – CRYPTO 2021. 41st annual international cryptology conference, CRYPTO 2021, virtual event, August 16–20, 2021. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 12826, 732-759 (2021).
MSC:  94A60
PDFBibTeX XMLCite
Full Text: DOI

Distance oracles for interval graphs via breadth-first rank/select in succinct trees. (English) Zbl 07765383

Cao, Yixin (ed.) et al., 31st international symposium on algorithms and computation, ISAAC 2020, Hong Kong, China, virtual conference, December 14–18, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 181, Article 25, 18 p. (2020).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Non-interactive composition of sigma-protocols via Share-then-Hash. (English) Zbl 1511.94034

Moriai, Shiho (ed.) et al., Advances in cryptology – ASIACRYPT 2020. 26th international conference on the theory and application of cryptology and information security, Daejeon, South Korea, December 7–11, 2020. Proceedings. Part III. Cham: Springer. Lect. Notes Comput. Sci. 12493, 749-773 (2020).
MSC:  94A60 94A62
PDFBibTeX XMLCite
Full Text: DOI

Cutting bamboo down to size. (English) Zbl 1515.68378

Farach-Colton, Martin (ed.) et al., 10th international conference on fun with algorithms. FUN 2021, May 30 – June 1, 2021, Favignana Island, Sicily, Italy. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 157, Article 5, 18 p. (2020).
MSC:  68W25 68P05 90B35
PDFBibTeX XMLCite
Full Text: DOI

Massively parallel approximate distance sketches. (English) Zbl 07650885

Felber, Pascal (ed.) et al., 23rd international conference on principles of distributed systems, OPODIS 2019, Neuchâtel, Switzerland, December 17–19, 2019. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 153, Article 35, 17 p. (2020).
MSC:  68M14 68M20
PDFBibTeX XMLCite
Full Text: DOI arXiv

Tight verifiable delay functions. (English) Zbl 1506.94040

Galdi, Clemente (ed.) et al., Security and cryptography for networks. 12th international conference, SCN 2020, Amalfi, Italy, September 14–16, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12238, 65-84 (2020).
MSC:  94A60 68P25 68N20
PDFBibTeX XMLCite
Full Text: DOI

The power of Leibniz-like functions as oracles. (English) Zbl 07603927

Fernau, Henning, Computer science – theory and applications. 15th international computer science symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12159, 263-275 (2020).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Efficient simulation of random states and random unitaries. (English) Zbl 1480.81026

Canteaut, Anne (ed.) et al., Advances in cryptology – EUROCRYPT 2020. 39th annual international conference on the theory and applications of cryptographic techniques, Zagreb, Croatia, May 10–14, 2020. Proceedings. Part III. Cham: Springer. Lect. Notes Comput. Sci. 12107, 759-787 (2020).
MSC:  81P68 81P94 68Q87
PDFBibTeX XMLCite
Full Text: DOI arXiv

Inverse problems, constraint satisfaction, reversible logic, invertible logic and Grover quantum oracles for practical problems. (English) Zbl 07368045

Lanese, Ivan (ed.) et al., Reversible computation. 12th international conference, RC 2020, Oslo, Norway, July 9–10, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12227, 3-32 (2020).
MSC:  68Q09 68Q10 81P68
PDFBibTeX XMLCite
Full Text: DOI

Distance sensitivity oracles with subcubic preprocessing time and fast query time. (English) Zbl 1474.68213

Makarychev, Konstantin (ed.) et al., Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, STOC ’20, Chicago, IL, USA, June 22–26, 2020. New York, NY: Association for Computing Machinery (ACM). 1375-1388 (2020).
MSC:  68R10 68P05 68W40
PDFBibTeX XMLCite
Full Text: DOI

On strong diameter padded decompositions. (English) Zbl 07650073

Achlioptas, Dimitris (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques, 22nd international conference, APPROX 2019, and 23rd international conference, RANDOM 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, September 20–22, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 145, Article 6, 21 p. (2019).
MSC:  68W20 68W25 90C27
PDFBibTeX XMLCite
Full Text: DOI arXiv

Exploiting hopsets: improved distance oracles for graphs of constant highway dimension and beyond. (English) Zbl 07561636

Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 143, 15 p. (2019).
MSC:  68Nxx 68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Deterministic combinatorial replacement paths and distance sensitivity oracles. (English) Zbl 07561505

Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 12, 14 p. (2019).
MSC:  68Nxx 68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Quadratic time-space lower bounds for computing natural functions with a random oracle. (English) Zbl 07559099

Blum, Avrim (ed.), 10th innovations in theoretical computer science conference, ITCS 2019, January 10–12, 2019, San Diego, CA, USA. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 124, Article 56, 20 p. (2019).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Re: what’s up Johnny? Covert content attacks on email end-to-end encryption. (English) Zbl 1458.94272

Deng, Robert H. (ed.) et al., Applied cryptography and network security. 17th international conference, ACNS 2019, Bogota, Colombia, June 5–7, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11464, 24-42 (2019).
MSC:  94A60
PDFBibTeX XMLCite
Full Text: DOI arXiv

Almost optimal distance oracles for planar graphs. (English) Zbl 1433.68284

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). 138-151 (2019).
MSC:  68R10 68P05 68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Logarithmic-size ring signatures with tight security from the DDH assumption. (English) Zbl 1500.94073

Lopez, Javier (ed.) et al., Computer security. 23rd European symposium on research in computer security, ESORICS 2018, Barcelona, Spain, September 3–7, 2018. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 11099, 288-308 (2018).
MSC:  94A62 94A60
PDFBibTeX XMLCite
Full Text: DOI HAL

On the complexity of the (approximate) nearest colored node problem. (English) Zbl 1524.68240

Azar, Yossi (ed.) et al., 26th annual European symposium on algorithms, ESA 2018, August 20–22, 2018, Helsinki, Finland. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 112, Article 68, 14 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Near-optimal distance emulator for planar graphs. (English) Zbl 1522.68390

Azar, Yossi (ed.) et al., 26th annual European symposium on algorithms, ESA 2018, August 20–22, 2018, Helsinki, Finland. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 112, Article 16, 17 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Generic single edge fault tolerant exact distance oracle. (English) Zbl 1499.68274

Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 72, 15 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Approximate shortest paths and distance oracles in weighted unit-disk graphs. (English) Zbl 1489.68185

Speckmann, Bettina (ed.) et al., 34th international symposium on computational geometry, SoCG 2018, June 11–14, 2018, Budapest, Hungary. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 99, Article 24, 13 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI

The wonderful world of global random oracles. (English) Zbl 1423.94057

Nielsen, Jesper Buus (ed.) et al., Advances in cryptology – EUROCRYPT 2018. 37th annual international conference on the theory and applications of cryptographic techniques, Tel Aviv, Israel, April 29 – May 3, 2018. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 10820, 280-312 (2018).
MSC:  94A60
PDFBibTeX XMLCite
Full Text: DOI

Efficient dynamic approximate distance oracles for vertex-labeled planar graphs. (English) Zbl 1436.68247

Solis-Oba, Roberto (ed.) et al., Approximation and online algorithms. 15th international workshop, WAOA 2017, Vienna, Austria, September 7–8, 2017. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 10787, 269-284 (2018).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Leighton-Micali hash-based signatures in the quantum random-oracle model. (English) Zbl 1384.94060

Adams, Carlisle (ed.) et al., Selected areas in cryptography – SAC 2017. 24th international conference, Ottawa, ON, Canada, August 16–18, 2017. Revised selected papers. Cham: Springer (ISBN 978-3-319-72564-2/pbk; 978-3-319-72565-9/ebook). Lecture Notes in Computer Science 10719, 263-280 (2018).
MSC:  94A60 81P94
PDFBibTeX XMLCite
Full Text: DOI

Additive spanners and distance oracles in quadratic time. (English) Zbl 1441.68189

Chatzigiannakis, Ioannis (ed.) et al., 44th international colloquium on automata, languages, and programming, ICALP 2017, Warsaw, Poland July 10–14, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 80, Article 64, 12 p. (2017).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Approximating approximate distance oracles. (English) Zbl 1402.68033

Papadimitriou, Christos H. (ed.), 8th innovations in theoretical computer science conference, ITCS 2017, Berkeley, CA, USA, January 9–11, 2017. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-029-3). LIPIcs – Leibniz International Proceedings in Informatics 67, Article 52, 14 p. (2017).
MSC:  68P05 68W25
PDFBibTeX XMLCite
Full Text: DOI arXiv

On the power of oracle \(\varOmega ?\) for self-stabilizing leader election in population protocols. (English) Zbl 1425.68027

Bonakdarpour, Borzoo (ed.) et al., Stabilization, safety, and security of distributed systems. 18th international symposium, SSS 2016, Lyon, France, November 7–10, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10083, 20-35 (2016).
MSC:  68M12 68M14
PDFBibTeX XMLCite
Full Text: DOI

Hierarchical time-dependent oracles. (English) Zbl 1398.05078

Seok-Hee Hong (ed.), 27th international symposium on algorithms and computation, ISAAC 2016, Sydney, Australia, December 12–14, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-026-2). LIPIcs – Leibniz International Proceedings in Informatics 64, Article 47, 13 p. (2016).
MSC:  05C12 05C85 68W25
PDFBibTeX XMLCite
Full Text: DOI arXiv

All-pairs approximate shortest paths and distance oracle preprocessing. (English) Zbl 1388.68241

Chatzigiannakis, Ioannis (ed.) et al., 43rd international colloquium on automata, languages, and programming, ICALP 2016, Rome, Italy, July 12–15, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-013-2). LIPIcs – Leibniz International Proceedings in Informatics 55, Article 55, 13 p. (2016).
MSC:  68R10 05C85 68P05
PDFBibTeX XMLCite
Full Text: DOI

The nearest colored node in a tree. (English) Zbl 1380.68146

Grossi, Roberto (ed.) et al., 27th annual symposium on combinatorial pattern matching, CPM 2016, Tel Aviv, Israel, June 27–29, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-012-5). LIPIcs – Leibniz International Proceedings in Informatics 54, Article 25, 12 p. (2016).
MSC:  68P05 68R10 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Color-distance oracles and snippets. (English) Zbl 1380.68153

Grossi, Roberto (ed.) et al., 27th annual symposium on combinatorial pattern matching, CPM 2016, Tel Aviv, Israel, June 27–29, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-012-5). LIPIcs – Leibniz International Proceedings in Informatics 54, Article 24, 10 p. (2016).
PDFBibTeX XMLCite
Full Text: DOI

Brief announcement: Sublinear-space distance labeling using hubs. (English) Zbl 1376.68158

Proceedings of the 2016 ACM symposium on principles of distributed computing, PODC ’16, Chicago, IL, USA, July 25–28, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3964-3). 43-45 (2016).
MSC:  68W15 05C78 68P05
PDFBibTeX XMLCite
Full Text: DOI

The computational power of optimization in online learning. (English) Zbl 1373.68456

Wichs, Daniel (ed.) et al., Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC ’16, Cambridge, MA, USA, June 19–21, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4132-5). 128-141 (2016).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Filter Results by …

Document Type

all top 5

Author

all top 5

Serial

all top 5

Year of Publication

all top 3

Main Field

all top 3

Software