5 Search Results for "Hellerstein, Lisa"


Document
Quickly Determining Who Won an Election

Authors: Lisa Hellerstein, Naifeng Liu, and Kevin Schewior

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)


Abstract
This paper considers elections in which voters choose one candidate each, independently according to known probability distributions. A candidate receiving a strict majority (absolute or relative, depending on the version) wins. After the voters have made their choices, each vote can be inspected to determine which candidate received that vote. The time (or cost) to inspect each of the votes is known in advance. The task is to (possibly adaptively) determine the order in which to inspect the votes, so as to minimize the expected time to determine which candidate has won the election. We design polynomial-time constant-factor approximation algorithms for both the absolute-majority and the relative-majority version. Both algorithms are based on a two-phase approach. In the first phase, the algorithms reduce the number of relevant candidates to O(1), and in the second phase they utilize techniques from the literature on stochastic function evaluation to handle the remaining candidates. In the case of absolute majority, we show that the same can be achieved with only two rounds of adaptivity.

Cite as

Lisa Hellerstein, Naifeng Liu, and Kevin Schewior. Quickly Determining Who Won an Election. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 61:1-61:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{hellerstein_et_al:LIPIcs.ITCS.2024.61,
  author =	{Hellerstein, Lisa and Liu, Naifeng and Schewior, Kevin},
  title =	{{Quickly Determining Who Won an Election}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{61:1--61:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.61},
  URN =		{urn:nbn:de:0030-drops-195890},
  doi =		{10.4230/LIPIcs.ITCS.2024.61},
  annote =	{Keywords: stochastic function evaluation, voting, approximation algorithms}
}
Document
A Local Search Algorithm for the Min-Sum Submodular Cover Problem

Authors: Lisa Hellerstein, Thomas Lidbetter, and R. Teal Witter

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)


Abstract
We consider the problem of solving the Min-Sum Submodular Cover problem using local search. The Min-Sum Submodular Cover problem generalizes the NP-complete Min-Sum Set Cover problem, replacing the input set cover instance with a monotone submodular set function. A simple greedy algorithm achieves an approximation factor of 4, which is tight unless P=NP [Streeter and Golovin, NeurIPS, 2008]. We complement the greedy algorithm with analysis of a local search algorithm. Building on work of Munagala et al. [ICDT, 2005], we show that, using simple initialization, a straightforward local search algorithm achieves a (4+ε)-approximate solution in time O(n³log(n/ε)), provided that the monotone submodular set function is also second-order supermodular. Second-order supermodularity has been shown to hold for a number of submodular functions of practical interest, including functions associated with set cover, matching, and facility location. We present experiments on two special cases of Min-Sum Submodular Cover and find that the local search algorithm can outperform the greedy algorithm on small data sets.

Cite as

Lisa Hellerstein, Thomas Lidbetter, and R. Teal Witter. A Local Search Algorithm for the Min-Sum Submodular Cover Problem. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 3:1-3:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{hellerstein_et_al:LIPIcs.ISAAC.2022.3,
  author =	{Hellerstein, Lisa and Lidbetter, Thomas and Witter, R. Teal},
  title =	{{A Local Search Algorithm for the Min-Sum Submodular Cover Problem}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{3:1--3:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.3},
  URN =		{urn:nbn:de:0030-drops-172880},
  doi =		{10.4230/LIPIcs.ISAAC.2022.3},
  annote =	{Keywords: Local search, submodularity, second-order supermodularity, min-sum set cover}
}
Document
The Stochastic Score Classification Problem

Authors: Dimitrios Gkenosis, Nathaniel Grammel, Lisa Hellerstein, and Devorah Kletenik

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)


Abstract
Consider the following Stochastic Score Classification Problem. A doctor is assessing a patient's risk of developing a certain disease, and can perform n tests on the patient. Each test has a binary outcome, positive or negative. A positive result is an indication of risk, and a patient's score is the total number of positive test results. Test results are accurate. The doctor needs to classify the patient into one of B risk classes, depending on the score (e.g., LOW, MEDIUM, and HIGH risk). Each of these classes corresponds to a contiguous range of scores. Test i has probability p_i of being positive, and it costs c_i to perform. To reduce costs, instead of performing all tests, the doctor will perform them sequentially and stop testing when it is possible to determine the patient's risk category. The problem is to determine the order in which the doctor should perform the tests, so as to minimize expected testing cost. We provide approximation algorithms for adaptive and non-adaptive versions of this problem, and pose a number of open questions.

Cite as

Dimitrios Gkenosis, Nathaniel Grammel, Lisa Hellerstein, and Devorah Kletenik. The Stochastic Score Classification Problem. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 36:1-36:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{gkenosis_et_al:LIPIcs.ESA.2018.36,
  author =	{Gkenosis, Dimitrios and Grammel, Nathaniel and Hellerstein, Lisa and Kletenik, Devorah},
  title =	{{The Stochastic Score Classification Problem}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{36:1--36:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.36},
  URN =		{urn:nbn:de:0030-drops-94990},
  doi =		{10.4230/LIPIcs.ESA.2018.36},
  annote =	{Keywords: approximation algorithms, symmetric Boolean functions, stochastic probing, sequential testing, adaptivity}
}
Document
No complete linear term rewriting system for propositional logic

Authors: Anupam Das and Lutz Straßburger

Published in: LIPIcs, Volume 36, 26th International Conference on Rewriting Techniques and Applications (RTA 2015)


Abstract
Recently it has been observed that the set of all sound linear inference rules in propositional logic is already coNP-complete, i.e. that every Boolean tautology can be written as a (left- and right-) linear rewrite rule. This raises the question of whether there is a rewriting system on linear terms of propositional logic that is sound and complete for the set of all such rewrite rules. We show in this paper that, as long as reduction steps are polynomial-time decidable, such a rewriting system does not exist unless coNP=NP. We draw tools and concepts from term rewriting, Boolean function theory and graph theory in order to access the required intermediate results. At the same time we make several connections between these areas that, to our knowledge, have not yet been presented and constitute a rich theoretical framework for reasoning about linear TRSs for propositional logic.

Cite as

Anupam Das and Lutz Straßburger. No complete linear term rewriting system for propositional logic. In 26th International Conference on Rewriting Techniques and Applications (RTA 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 36, pp. 127-142, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.RTA.2015.127,
  author =	{Das, Anupam and Stra{\ss}burger, Lutz},
  title =	{{No complete linear term rewriting system for propositional logic}},
  booktitle =	{26th International Conference on Rewriting Techniques and Applications (RTA 2015)},
  pages =	{127--142},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-85-9},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{36},
  editor =	{Fern\'{a}ndez, Maribel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2015.127},
  URN =		{urn:nbn:de:0030-drops-51935},
  doi =		{10.4230/LIPIcs.RTA.2015.127},
  annote =	{Keywords: Linear rules, Term rewriting, Propositional logic, Proof theory, Deep inference}
}
Document
On the (Non) NP-Hardness of Computing Circuit Complexity

Authors: Cody D. Murray and R. Ryan Williams

Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)


Abstract
The Minimum Circuit Size Problem (MCSP) is: given the truth table of a Boolean function f and a size parameter k, is the circuit complexity of f at most k? This is the definitive problem of circuit synthesis, and it has been studied since the 1950s. Unlike many problems of its kind, MCSP is not known to be NP-hard, yet an efficient algorithm for this problem also seems very unlikely: for example, MCSP in P would imply there are no pseudorandom functions. Although most NP-complete problems are complete under strong "local" reduction notions such as poly-logarithmic time projections, we show that MCSP is provably not NP-hard under O(n^(1/2-epsilon))-time projections, for every epsilon > 0. We prove that the NP-hardness of MCSP under (logtime-uniform) AC0 reductions would imply extremely strong lower bounds: NP \not\subset P/poly and E \not\subset i.o.-SIZE(2^(delta * n)) for some delta > 0 (hence P = BPP also follows). We show that even the NP-hardness of MCSP under general polynomial-time reductions would separate complexity classes: EXP != NP \cap P/poly, which implies EXP != ZPP. These results help explain why it has been so difficult to prove that MCSP is NP-hard. We also consider the nondeterministic generalization of MCSP: the Nondeterministic Minimum Circuit Size Problem (NMCSP), where one wishes to compute the nondeterministic circuit complexity of a given function. We prove that the Sigma_2 P-hardness of NMCSP, even under arbitrary polynomial-time reductions, would imply EXP \not\subset P/poly.

Cite as

Cody D. Murray and R. Ryan Williams. On the (Non) NP-Hardness of Computing Circuit Complexity. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 365-380, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{murray_et_al:LIPIcs.CCC.2015.365,
  author =	{Murray, Cody D. and Williams, R. Ryan},
  title =	{{On the (Non) NP-Hardness of Computing Circuit Complexity}},
  booktitle =	{30th Conference on Computational Complexity (CCC 2015)},
  pages =	{365--380},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-81-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{33},
  editor =	{Zuckerman, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.365},
  URN =		{urn:nbn:de:0030-drops-50745},
  doi =		{10.4230/LIPIcs.CCC.2015.365},
  annote =	{Keywords: circuit lower bounds, Minimum Circuit Size Problem, NP-completeness, projections, Reductions}
}
  • Refine by Author
  • 3 Hellerstein, Lisa
  • 1 Das, Anupam
  • 1 Gkenosis, Dimitrios
  • 1 Grammel, Nathaniel
  • 1 Kletenik, Devorah
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Facility location and clustering

  • Refine by Keyword
  • 2 approximation algorithms
  • 1 Deep inference
  • 1 Linear rules
  • 1 Local search
  • 1 Minimum Circuit Size Problem
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2015
  • 1 2018
  • 1 2022
  • 1 2024

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