Document

**Published in:** LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

This paper presents and studies a generalization of the microscopic image reconstruction problem (MIR) introduced by Frosini and Nivat [Andrea Frosini and Maurice Nivat, 2007; Nivat, 2002]. Consider a specimen for inspection, represented as a collection of points typically organized on a grid in the plane. Assume each point x has an associated physical value l_x, which we would like to determine. However, it might be that obtaining these values precisely (by a surgical probe) is difficult, risky, or impossible. The alternative is to employ aggregate measuring techniques (such as EM, CT, US or MRI), whereby each measurement is taken over a larger window, and the exact values at each point are subsequently extracted by computational methods.
In this paper we extend the MIR framework in a number of ways. First, we consider a generalized setting where the inspected object is represented by an arbitrary graph G, and the vector l in R^n assigns a value l_v to each node v. A probe centered at a vertex v will capture a window encompassing its entire neighborhood N[v], i.e., the outcome of a probe centered at v is P_v = sum_{w in N[v]} l_w. We give a criterion for the graphs for which the extended MIR problem can be solved by extracting the vector l from the collection of probes, P^- = {P_v | v in V}.
We then consider cases where such reconstruction is impossible (namely, graphs G for which the probe vector P is inconclusive, in the sense that there may be more than one vector l yielding P). Let us assume that surgical probes (whose outcome at vertex v is the exact value of l_v) are technically available to us (yet are expensive or risky, and must be used sparingly). We show that in such cases, it may still be possible to achieve reconstruction based on a combination of a collection of standard probes together with a suitable set of surgical probes. We aim at identifying the minimum number of surgical probes necessary for a unique reconstruction, depending on the graph topology. This is referred to as the Minimum Surgical Probing problem (MSP).
Besides providing a solution for the above problems for arbitrary graphs, we also explore the range of possible behaviors of the Minimum Surgical Probing problem by determining the number of surgical probes necessary in certain specific graph families, such as perfect k-ary trees, paths, cycles, grids, tori and tubes.

Amotz Bar-Noy, Toni Böhnlein, Zvi Lotker, David Peleg, and Dror Rawitz. The Generalized Microscopic Image Reconstruction Problem. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 42:1-42:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{barnoy_et_al:LIPIcs.ISAAC.2019.42, author = {Bar-Noy, Amotz and B\"{o}hnlein, Toni and Lotker, Zvi and Peleg, David and Rawitz, Dror}, title = {{The Generalized Microscopic Image Reconstruction Problem}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {42:1--42:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.42}, URN = {urn:nbn:de:0030-drops-115382}, doi = {10.4230/LIPIcs.ISAAC.2019.42}, annote = {Keywords: Discrete mathematics, Combinatorics, Reconstruction algorithm, Image reconstruction, Graph spectra, Grid graphs} }

Document

**Published in:** LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

In the Multislope Ski Rental problem, the user needs a certain
resource for some unknown period of time. To use the resource, the
user must subscribe to one of several options, each of which
consists of a one-time setup cost (``buying price''), and cost
proportional to the duration of the usage (``rental rate''). The
larger the price, the smaller the rent. The actual usage time is
determined by an adversary, and the goal of an algorithm is to
minimize the cost by choosing the best option at any point in time.
Multislope Ski Rental is a natural generalization of the classical
Ski Rental problem (where the only options are pure rent and pure
buy), which is one of the fundamental problems of online
computation. The Multislope Ski Rental problem is an abstraction
of many problems where online decisions cannot be modeled by just
two options, e.g., power management in systems which can be shut
down in parts. In this paper we study randomized algorithms for
Multislope Ski Rental. Our results include the best possible
online randomized strategy for any additive instance, where the
cost of switching from one option to another is the difference in
their buying prices; and an algorithm that produces an
$e$-competitive randomized strategy for any (non-additive)
instance.

Zvi Lotker, Boaz Patt-Shamir, and Dror Rawitz. Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 503-514, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{lotker_et_al:LIPIcs.STACS.2008.1331, author = {Lotker, Zvi and Patt-Shamir, Boaz and Rawitz, Dror}, title = {{Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental}}, booktitle = {25th International Symposium on Theoretical Aspects of Computer Science}, pages = {503--514}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-06-4}, ISSN = {1868-8969}, year = {2008}, volume = {1}, editor = {Albers, Susanne and Weil, Pascal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1331}, URN = {urn:nbn:de:0030-drops-13313}, doi = {10.4230/LIPIcs.STACS.2008.1331}, annote = {Keywords: Competitive analysis, ski rental, randomized algorithms} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 7411, Algebraic Methods in Computational Complexity (2008)

We study the two party problem of randomly selecting a string among
all the strings of length n. We want the protocol to have the
property that the output distribution has high entropy, even
when one of the two parties is dishonest and deviates from the
protocol. We develop protocols that achieve high, close to n,
entropy.
In the literature the randomness guarantee is usually expressed as
being close to the uniform distribution or in terms of resiliency.
The notion of entropy is not directly comparable to that of
resiliency, but we establish a connection between the two that
allows us to compare our protocols with the existing ones.
We construct an
explicit protocol that yields entropy n - O(1) and has 4log^* n
rounds, improving over the protocol of Goldwasser
et al. that also achieves this entropy but needs O(n)
rounds. Both these protocols need O(n^2) bits of communication.
Next we reduce the communication in our protocols. We show the existence,
non-explicitly, of a protocol that has 6-rounds, 2n + 8log n bits
of communication and yields entropy n- O(log n) and min-entropy
n/2 - O(log n). Our protocol achieves the same entropy bound as
the recent, also non-explicit, protocol of Gradwohl
et al., however achieves much higher min-entropy: n/2 -
O(log n) versus O(log n).
Finally we exhibit very simple explicit protocols. We connect the
security parameter of these geometric protocols with the well
studied Kakeya problem motivated by harmonic analysis and analytical
number theory. We are only able to prove that these protocols have
entropy 3n/4 but still n/2 - O(log n) min-entropy. Therefore
they do not perform as well with respect to the explicit
constructions of Gradwohl et al. entropy-wise, but still
have much better min-entropy. We conjecture that these simple
protocols achieve n -o(n) entropy. Our geometric
construction and its relation to the Kakeya problem follows a new and
different approach to the random selection problem than any of the
previously known protocols.

Nikolai K. Vereshchagin, Harry Buhrman, Matthias Cristandl, Michal Koucky, Zvi Lotker, and Boaz Patt-Shamir. High Entropy Random Selection Protocols. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 7411, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{vereshchagin_et_al:DagSemProc.07411.5, author = {Vereshchagin, Nikolai K. and Buhrman, Harry and Cristandl, Matthias and Koucky, Michal and Lotker, Zvi and Patt-Shamir, Boaz}, title = {{High Entropy Random Selection Protocols}}, booktitle = {Algebraic Methods in Computational Complexity}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {7411}, editor = {Manindra Agrawal and Harry Buhrman and Lance Fortnow and Thomas Thierauf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07411.5}, URN = {urn:nbn:de:0030-drops-13091}, doi = {10.4230/DagSemProc.07411.5}, annote = {Keywords: Shannon entropy, Random string ds} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail