4 Search Results for "Smith, Spencer"

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.10
The (Im)possibility of Simple Search-To-Decision Reductions for Approximation Problems

Authors: Alexander Golovnev, Siyao Guo, Spencer Peters, and Noah Stephens-Davidowitz

Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)

Abstract
We study the question of when an approximate search optimization problem is harder than the associated decision problem. Specifically, we study a natural and quite general model of black-box search-to-decision reductions, which we call branch-and-bound reductions (in analogy with branch-and-bound algorithms). In this model, an algorithm attempts to minimize (or maximize) a function f: D → ℝ_{≥ 0} by making oracle queries to h_f : 𝒮 → ℝ_{≥ 0} satisfying min_{x ∈ S} f(x) ≤ h_f(S) ≤ γ ⋅ min_{x ∈ S} f(x) (*) for some γ ≥ 1 and any subset S in some allowed class of subsets 𝒮 of the domain D. (When the goal is to maximize f, h_f instead yields an approximation to the maximal value of f over S.) We show tight upper and lower bounds on the number of queries q needed to find even a γ'-approximate minimizer (or maximizer) for quite large γ' in a number of interesting settings, as follows. - For arbitrary functions f : {0,1}ⁿ → ℝ_{≥ 0}, where 𝒮 contains all subsets of the domain, we show that no branch-and-bound reduction can achieve γ' ≲ γ^{n/log q}, while a simple greedy approach achieves essentially γ^{n/log q}. - For a large class of MAX-CSPs, where 𝒮 := {S_w} contains each set of assignments to the variables induced by a partial assignment w, we show that no branch-and-bound reduction can do significantly better than essentially a random guess, even when the oracle h_f guarantees an approximation factor of γ ≈ 1+√{log(q)/n}. - For the Traveling Salesperson Problem (TSP), where 𝒮 := {S_p} contains each set of tours extending a path p, we show that no branch-and-bound reduction can achieve γ' ≲ (γ-1) n/log q. We also prove a nearly matching upper bound in our model. These results show an oracle model in which approximate search and decision are strongly separated. (In particular, our result for TSP can be viewed as a negative answer to a question posed by Bellare and Goldwasser (SIAM J. Comput. 1994), though only in an oracle model.) We also note two alternative interpretations of our results. First, if we view h_f as a data structure, then our results unconditionally rule out black-box search-to-decision reductions for certain data structure problems. Second, if we view h_f as an efficiently computable heuristic, then our results show that any reasonably efficient branch-and-bound algorithm requires more guarantees from its heuristic than simply Eq. (*). Behind our results is a "useless oracle lemma," which allows us to argue that under certain conditions the oracle h_f is "useless," and which might be of independent interest. See also the full version [Alexander Golovnev et al., 2022].
Cite as

Alexander Golovnev, Siyao Guo, Spencer Peters, and Noah Stephens-Davidowitz. The (Im)possibility of Simple Search-To-Decision Reductions for Approximation Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{golovnev_et_al:LIPIcs.APPROX/RANDOM.2023.10,
  author =	{Golovnev, Alexander and Guo, Siyao and Peters, Spencer and Stephens-Davidowitz, Noah},
  title =	{{The (Im)possibility of Simple Search-To-Decision Reductions for Approximation Problems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{10:1--10:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.10},
  URN =		{urn:nbn:de:0030-drops-188351},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.10},
  annote =	{Keywords: search-to-decision reductions, oracles, constraint satisfaction, traveling salesman, discrete optimization}
}
Document
DOI: 10.4230/OASIcs.EVCS.2023.7
Generating Software for Well-Understood Domains

Authors: Jacques Carette, Spencer W. Smith, and Jason Balaci

Published in: OASIcs, Volume 109, Eelco Visser Commemorative Symposium (EVCS 2023)

Abstract
Current software development is often quite code-centric and aimed at short-term deliverables, due to various contextual forces (such as the need for new revenue streams from many individual buyers). We're interested in software where different forces drive the development. Well understood domains and long-lived software provide one such context. A crucial observation is that software artifacts that are currently handwritten contain considerable duplication. By using domain-specific languages and generative techniques, we can capture the contents of many of the artifacts of such software. Assuming an appropriate codification of domain knowledge, we find that the resulting de-duplicated sources are shorter and closer to the domain. Our prototype, Drasil, indicates improvements to traceability and change management. We're also hopeful that this could lead to long-term productivity improvements for software where these forces are at play.
Cite as

Jacques Carette, Spencer W. Smith, and Jason Balaci. Generating Software for Well-Understood Domains. In Eelco Visser Commemorative Symposium (EVCS 2023). Open Access Series in Informatics (OASIcs), Volume 109, pp. 7:1-7:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{carette_et_al:OASIcs.EVCS.2023.7,
  author =	{Carette, Jacques and Smith, Spencer W. and Balaci, Jason},
  title =	{{Generating Software for Well-Understood Domains}},
  booktitle =	{Eelco Visser Commemorative Symposium (EVCS 2023)},
  pages =	{7:1--7:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-267-9},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{109},
  editor =	{L\"{a}mmel, Ralf and Mosses, Peter D. and Steimann, Friedrich},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.EVCS.2023.7},
  URN =		{urn:nbn:de:0030-drops-177776},
  doi =		{10.4230/OASIcs.EVCS.2023.7},
  annote =	{Keywords: code generation, document generation, knowledge capture, software engineering}
}
Document
DOI: 10.4230/DagSemProc.08021.18
Second Note on Basic Interval Arithmetic for IEEE754R

Authors: John D. Pryce, George C. Corliss, R. Baker Kearfott, Ned S. Nedialkov, and Spencer Smith

Published in: Dagstuhl Seminar Proceedings, Volume 8021, Numerical Validation in Current Hardware Architectures (2008)

Abstract
The IFIP Working Group 2.5 on Numerical Software (IFIPWG2.5) wrote on 5th Septem- ber 2007 to the IEEE Standards Committee concerned with revising the IEEE Floating- Point Arithmetic Standards 754 and 854 (IEEE754R), expressing the unanimous request of IFIPWG2.5 that the following requirement be included in the future computer arithmetic standard: For the data format double precision, interval arithmetic should be made available at the speed of simple floating-point arithmetic. IEEE754R (we believe) welcomed this development. They had before them a document defining interval arithmetic operations but, to be the basis of a standards document, it needed more detail. Members of the Interval Subroutine Library (ISL) team were asked to comment, in an email from Ulrich Kulisch that enclosed one from Jim Demmel to Van Snyder raising the issue. This paper provides ISL's comments.
Cite as

John D. Pryce, George C. Corliss, R. Baker Kearfott, Ned S. Nedialkov, and Spencer Smith. Second Note on Basic Interval Arithmetic for IEEE754R. In Numerical Validation in Current Hardware Architectures. Dagstuhl Seminar Proceedings, Volume 8021, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{pryce_et_al:DagSemProc.08021.18,
  author =	{Pryce, John D. and Corliss, George C. and Kearfott, R. Baker and Nedialkov, Ned S. and Smith, Spencer},
  title =	{{Second Note on Basic Interval Arithmetic for IEEE754R}},
  booktitle =	{Numerical Validation in Current Hardware Architectures},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8021},
  editor =	{Annie Cuyt and Walter Kr\"{a}mer and Wolfram Luther and Peter Markstein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08021.18},
  URN =		{urn:nbn:de:0030-drops-14517},
  doi =		{10.4230/DagSemProc.08021.18},
  annote =	{Keywords: Interval arithmetic, validated computation, floating point, standards, exceptions, not an interval}
}
Document
DOI: 10.4230/DagSemProc.06021.7
Interval Subroutine Library Mission

Authors: George F. Corliss, R. Baker Kearfott, Ned Nedialkov, John D. Pryce, and Spencer Smith

Published in: Dagstuhl Seminar Proceedings, Volume 6021, Reliable Implementation of Real Number Algorithms: Theory and Practice (2006)

Abstract
We propose the collection, standardization, and distribution of a full-featured production quality library for reliable scientific computing with routines using interval techniques for use by the wide community of applications developers.
Cite as

George F. Corliss, R. Baker Kearfott, Ned Nedialkov, John D. Pryce, and Spencer Smith. Interval Subroutine Library Mission. In Reliable Implementation of Real Number Algorithms: Theory and Practice. Dagstuhl Seminar Proceedings, Volume 6021, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{corliss_et_al:DagSemProc.06021.7,
  author =	{Corliss, George F. and Kearfott, R. Baker and Nedialkov, Ned and Pryce, John D. and Smith, Spencer},
  title =	{{Interval Subroutine Library Mission}},
  booktitle =	{Reliable Implementation of Real Number Algorithms: Theory and Practice},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6021},
  editor =	{Peter Hertling and Christoph M. Hoffmann and Wolfram Luther and Nathalie Revol},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06021.7},
  URN =		{urn:nbn:de:0030-drops-7122},
  doi =		{10.4230/DagSemProc.06021.7},
  annote =	{Keywords: Subroutine library, problem-solving library, C++ interval standard}
}
  • Refine by Author
  • 2 Kearfott, R. Baker
  • 2 Pryce, John D.
  • 2 Smith, Spencer
  • 1 Balaci, Jason
  • 1 Carette, Jacques
  • Show More...

  • Refine by Classification
  • 1 Software and its engineering → Application specific development environments
  • 1 Software and its engineering → Automatic programming
  • 1 Software and its engineering → Requirements analysis
  • 1 Software and its engineering → Specification languages
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 1 C++ interval standard
  • 1 Interval arithmetic
  • 1 Subroutine library
  • 1 code generation
  • 1 constraint satisfaction
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2023
  • 1 2006
  • 1 2008

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact