Output-sensitive algorithms for sumset and sparse polynomial multiplication [PDF]
Proceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation, 2015 Submitted to ISSAC ...
Andrew Arnold, Daniel S. Roche
semanticscholar +7 more sources
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries [PDF]
Discrete & Computational Geometry, 2005 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
David Avis +6 more
semanticscholar +5 more sources
Reactive Synthesis: Towards Output-Sensitive Algorithms [PDF]
Dependable Software Systems Engineering, 2018 Reactive synthesis is a technology for the automatic construction of reactive systems from logical specifications. In these lecture notes, we study different algorithms for the reactive synthesis problem of linear-time temporal logic (LTL). The classic game-based synthesis algorithm is input-sensitive in the sense that its performance is asymptotically
Bernd Finkbeiner, F. Klein
semanticscholar +5 more sources
Designing Output Sensitive Algorithms for Subgraph Enumeration [PDF]
From Strings to Graphs, and Back AgainThe enumeration of all subgraphs respecting some structural property is a fundamental task in theoretical computer science, with practical applications in many branches of data mining and network analysis. It is often of interest to only consider solutions (subgraphs) that are maximal under inclusion, and to achieve output-sensitive complexity, i.e ...
Conte, Alessio +5 more
semanticscholar +4 more sources
09171 Abstracts Collection – Adaptive, Output Sensitive, Online and Parameterized Algorithms [PDF]
, 2009 From 19.01. to 24.04.2009, the Dagstuhl Seminar 09171 ``Adaptive, Output Sensitive, Online and Parameterized Algorithms '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed.
Jérémy Barbay +3 more
core +6 more sources
Competing output-sensitive frame algorithms
Computational Geometry, 2011 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
José H. Dulá, Francisco J. López
semanticscholar +4 more sources
A Time-Efficient Output-Sensitive Quantum Algorithm for Boolean Matrix Multiplication [PDF]
International Symposium on Algorithms and Computation, 2012 This paper presents a quantum algorithm that computes the product of two $n\times n$ Boolean matrices in $\tilde O(n\sqrt{\ell}+\ell\sqrt{n})$ time, where $\ell$ is the number of non-zero entries in the product. This improves the previous output-sensitive quantum algorithms for Boolean matrix multiplication in the time complexity setting by Buhrman and
François Le Gall
semanticscholar +5 more sources
Optimal output-sensitive convex hull algorithms in two and three dimensions [PDF]
Discrete & Computational Geometry, 1996 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Timothy M. Chan
semanticscholar +5 more sources
Output sensitive algorithms for approximate incidences and their\n applications [PDF]
Computational Geometry, 2020 A preliminary version of this work appeared in Proc. 25th European Sympos.
Dror Aiger, Haim Kaplan, Micha Sharir
+8 more sources
Accelerating ERM for data-driven algorithm design using output-sensitive techniques [PDF]
Neural Information Processing Systems, 2022 Data-driven algorithm design is a promising, learning-based approach for beyond worst-case analysis of algorithms with tunable parameters. An important open problem is the design of computationally efficient data-driven algorithms for combinatorial ...
Maria-Florina Balcan +2 more
openalex +2 more sources