2024

Info-theory January 2024

info-theory@cs.huji.ac.il

1 participants
2 discussions

ITA seminar 29/1, 10:00 - Tomer Berg, Tel Aviv University
by Or Ordentlich 29 Jan '24

29 Jan '24

Hi all, Our next meeting in the Information Theory and Applications seminar will take place on Monday, January 29 at 10:00, in room A500. The speaker is Tomer Berg, who will tell us about how to test whether a stream of observed samples came from the uniform distribution, or from a distribution epsilon-far from uniform, using algorithms with limited memory. See you there, Or, Oron, Yuval and Alex --------------------------------------------- *Title*: On The Memory Complexity of Uniformity Testing *Abstract*: In the problem of uniformity testing with limited memory, we observe a sequence of independent identically distributed random variables drawn from a distribution p over [n], which is either uniform or is epsilon-far from uniform under the total variation distance, and our goal is to determine the correct hypothesis. At each time point we are allowed to update the state of a finite-memory machine with S states, where each state of the machine is assigned one of the hypotheses, and we are interested in obtaining an asymptotic probability of error at most delta<1/2 uniformly under both hypotheses. We derive upper and lower bounds on the number of states S needed in order to achieve a constant error probability delta, as a function of n and epsilon, where our upper bound is O(n*log(n) /epsilon) and our lower bound is Omega (n+ 1/epsilon). Prior works in the field have almost exclusively used collision counting for upper bounds but, as it turns out, in the limited memory with unlimited samples setup, counting collisions is not the best one can do. Thus, different proof techniques are needed in order to attain our bounds.

1 3

ITA seminar 15/1, 10:00 - Yonatan Yehezkeally, Technical University of Munich
by Or Ordentlich 14 Jan '24

14 Jan '24

Hi all, Our first Information Theory and Applications seminar for 2024 will take place on Monday, January 15 at 10:00, in room A500. The speaker this week is Yonatan Yehezkeally, who will tell us about problems related to using DNA for storage. See title and abstract below. See you there, Or, Oron, Yuval and Alex --------------------------------------------- Title: DNA-bases Storage Systems: Coding Theory and Algorithms Abstract: Storage (and retrieval) of information over DNA-based media raises unique challenges in contrast to contemporary digital standards, on many levels: algorithmic, computer/data scientific, information theoretic, (bio- and electrical-)engineering, biologic (and chemical). Thus, fresh (and renewed) focus on a number of rarely-studied problems in computation and information theory is necessitated, in coordination with partners from all of these disciplines. In this talk, we take an information-theoretic perspective and outline the general channel model. We will delve into a few of its components, presenting pertinent Coding-theoretic problems and the approaches that have been deployed to address them.

1 1

2024

Info-theory January 2024 ----- 2024 ----- November 2024 October 2024 September 2024 August 2024 July 2024 June 2024 May 2024 April 2024 March 2024 February 2024 January 2024

Info-theory January 2024