324 research outputs found
A new strategy for querying priced information.
No full textCicalese F, Laber ES. A new strategy for querying priced information. In: Proc. 37th Annual ACM Symposium on Theory of Computing (STOC 2005). 2005: 674-683
Searching for Jumbled Patterns in Strings
No full textCicalese F, Fici G, Lipták Z. Searching for Jumbled Patterns in Strings. In: Proc. of the Prague Stringology Conference 2009. 2009: 105-117
Competitive evaluation of threshold functions in the priced information model
No full textCicalese F, Milanic M. Competitive evaluation of threshold functions in the priced information model. Annals of Operations Research. 2009;188(1):111-132
Computing with Priced Information: game trees and the value dependent cost model
No full textCicalese F, Milanivc M. Computing with Priced Information: game trees and the value dependent cost model. Forschungsberichte der Technischen Fakultät, Abteilung Informationstechnik / Universität Bielefeld. Bielefeld: Universität Bielefeld, Technische Fakultät; 2008.We study the function evaluation problem in the priced information framework introduced in [Charikar et al. 2002]. We characterize the best possible extremal competitive ratio for the class of game tree functions. Moreover, we extend the above result to the case when the cost of reading a variable depends on the value of the variable. In this new value dependent cost variant of the problem, we also exactly evaluate the extremal competitive ratio for the whole class of monotone Boolean functions
A Note on Approximation of Uniform Distributions from Variable-to-Fixed Length Codes
No full textCicalese F, Gargano L, Vaccaro U. A Note on Approximation of Uniform Distributions from Variable-to-Fixed Length Codes. IEEE Transactions on Information Theory. 2006;52(8):3772-3777
Efficient Reconstruction of RC-Equivalent Strings
No full textCicalese F, Erdős PLP, Lipták Z. Efficient Reconstruction of RC-Equivalent Strings. In: Proc. WOCA. Vol 6460. Berlin, Heidelberg: Springer Berlin Heidelberg; 2011: 349-362
On the Competitive Ratio of Evaluating Priced Functions
No full textCicalese F, Laber E. On the Competitive Ratio of Evaluating Priced Functions. In: Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006). 2006: 944-953
2-Stage Fault Tolerant Interval Group Testing
No full textCicalese F, Quitzau JAA. 2-Stage Fault Tolerant Interval Group Testing. Forschungsberichte der Technischen Fakultät, Abteilung Informationstechnik / Universität Bielefeld. Bielefeld: Universität Bielefeld, Technische Fakultät; 2007
Q-ary Ulam-Rényi game with constrained lies
No full textCicalese F, Deppe C. Q-ary Ulam-Rényi game with constrained lies. In: Ahlswede R, Bäumer L, Cai N, et al., eds. General Theory of Information Transfer and Combinatorics. Lecture notes in computer science. Vol 4123. Berlin, Heidelberg: Springer; 2006: 663-679
Faster Deterministic Communication in Radio Networks
No full textCicalese F, Manne F, Xin Q. Faster Deterministic Communication in Radio Networks. Algorithmica. 2009;54(2):226-242.We study the communication primitives of broadcasting (one-to-all communication) and gossiping (all-to-all communication) in known topology radio networks, i.e., where for each primitive the schedule of transmissions is precomputed based on full knowledge about the size and the topology of the network. We show that gossiping can be completed in O(D + Delta log n/log Delta-log log n) time units in any radio network of size n, diameter D, and maximum degree Delta = Omega(log n). This is an almost optimal schedule in the sense that there exists a radio network topology, specifically Delta-regular tree, in which the radio gossiping cannot be completed in less than Omega(D + Delta log n/log Delta) units of time. Moreover, we show a D + O(log(3) n/log log n) schedule for the broadcast task. Both our transmission schemes significantly improve upon the currently best known schedules by G. asieniec, Peleg, and Xin (Proceedings of the 24th Annual ACM SIGACT-SIGOPS PODC, pp. 129-137, 2005), i. e., a O(D + Delta log n) time schedule for gossiping and a D + O(log(3) n) time schedule for broadcast. Our broadcasting schedule also improves, for large D, a very recent O(D + log(2) n) time broadcasting schedule by Kowalski and Pelc
- …
