On the instance optimality of detecting collisions and subgraphs

DOI10.4230/LIPICS.ICALP.2025.23MaRDI QIDQ7346454zbMATH OpenFDO

Authors Omri Ben-Eliezer, Tomer Grossman, Moni Naor

Publication date 10 September 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2025.23

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• An automatic inequality prover and instance optimal identity testing
• Collision resistant hashing for paranoids: dealing with multiple collisions
• Counting stars and other small subgraphs in sublinear-time
• scientific article; zbMATH DE number 1445373 (Why is no real title available?)
• scientific article; zbMATH DE number 7650404 (Why is no real title available?)
• Title not available (Why is no real title available?)
• Title not available (Why is no real title available?)
• Title not available (Why is no real title available?)
• Title not available (Why is no real title available?)
• Title not available (Why is no real title available?)
• Instance optimal learning of discrete distributions
• Instance-optimal geometric algorithms
• On the complexity of the parity argument and other inefficient proofs of existence
• On total functions, existence theorems and computational complexity
• Optimal adaptive algorithms for finding the nearest and farthest point on a parametric black-box curve
• Optimal aggregation algorithms for middleware.
• Universally-optimal distributed algorithms for known topologies

This page was built for publication: On the instance optimality of detecting collisions and subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7346454)