BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Yuval Lomnitz

Yuval Lomnitz contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Information Theorymath.IT

Trust snapshot

Quick read

Trust 21 - Emerging
8works
0followers
2topics
1close collaborators

Actions

Decide how to stay connected

Follow researcher0

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

8 published item(s)

preprint2013arXiv

A Universal Probability Assignment for Prediction of Individual Sequences

Is it a good idea to use the frequency of events in the past, as a guide to their frequency in the future (as we all do anyway)? In this paper the question is attacked from the perspective of universal prediction of individual sequences. It is shown that there is a universal sequential probability assignment, such that for a large class loss functions (optimization goals), the predictor minimizing the expected loss under this probability, is a good universal predictor. The proposed probability assignment is based on randomly dithering the empirical frequencies of states in the past, and it is easy to show that randomization is essential. This yields a very simple universal prediction scheme which is similar to Follow-the-Perturbed-Leader (FPL) and works for a large class of loss functions, as well as a partial justification for using probabilistic assumptions.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Universal communication part I: modulo additive channels

Which communication rates can be attained over a channel whose output is an unknown (possibly stochastic) function of the input that may vary arbitrarily in time with no a-priori model? Following the spirit of the finite-state compressibility of a sequence, defined by Lempel and Ziv, a "capacity" is defined for such a channel as the highest rate achievable by a designer knowing the particular relation that indeed exists between the input and output for all times, yet is constrained to use a fixed finite-length block communication scheme without feedback, i.e. use the same encoder and decoder over each block. In the case of the modulo additive channel, where the output sequence is obtained by modulo addition of an unknown individual sequence to the input sequence, this capacity is upper bounded by a function of the finite state compressibility of the noise sequence. A universal communication scheme with feedback that attains this capacity universally, without prior knowledge of the noise sequence, is presented.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Universal communication part II: channels with memory

Consider communication over a channel whose probabilistic model is completely unknown vector-wise and is not assumed to be stationary. Communication over such channels is challenging because knowing the past does not indicate anything about the future. The existence of reliable feedback and common randomness is assumed. In a previous paper it was shown that the Shannon capacity cannot be attained, in general, if the channel is not known. An alternative notion of "capacity" was defined, as the maximum rate of reliable communication by any block-coding system used over consecutive blocks. This rate was shown to be achievable for the modulo-additive channel with an individual, unknown noise sequence, and not achievable for some channels with memory. In this paper this "capacity" is shown to be achievable for general channel models possibly including memory, as long as this memory fades with time. In other words, there exists a system with feedback and common randomness that, without knowledge of the channel, asymptotically performs as well as any block code, which may be designed knowing the channel. For non-fading memory channels a weaker type of "capacity" is shown to be achievable.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Communication over Individual Channels -- a general framework

We consider the problem of communicating over a channel for which no mathematical model is specified, and the achievable rates are determined as a function of the channel input and output sequences known a-posteriori, without assuming any a-priori relation between them. In a previous paper we have shown that the empirical mutual information between the input and output sequences is achievable without specifying the channel model, by using feedback and common randomness, and a similar result for real-valued input and output alphabets. In this paper, we present a unifying framework which includes the two previous results as particular cases. We characterize the region of rate functions which are achievable, and show that asymptotically the rate function is equivalent to a conditional distribution of the channel input given the output. We present a scheme that achieves these rates with asymptotically vanishing overheads.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Universal Communication over Arbitrarily Varying Channels

We consider the problem of universally communicating over an unknown and arbitrarily varying channel, using feedback. The focus of this paper is on determining the input behavior, and specifically, a prior distribution which is used to randomly generate the codebook. We pose the problem of setting the prior as a sequential universal prediction problem, that attempts to approach a given target rate, which depends on the unknown channel sequence. The main result is that, for a channel comprised of an unknown, arbitrary sequence of memoryless channels, there is a system using feedback and common randomness that asymptotically attains, with high probability, the capacity of the time-averaged channel, universally for every sequence of channels. While no prior knowledge of the channel sequence is assumed, the rate achieved meets or exceeds the traditional arbitrarily varying channel (AVC) capacity for every memoryless AVC defined over the same alphabets, and therefore the system universally attains the random code AVC capacity, without knowledge of the AVC parameters. The system we present combines rateless coding with a universal prediction scheme for the prior. We present rough upper bounds on the rates that can be achieved in this setting and lower bounds for the redundancies.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

An Achievable Rate for the MIMO Individual Channel

We consider the problem of communicating over a multiple-input multiple-output (MIMO) real valued channel for which no mathematical model is specified, and achievable rates are given as a function of the channel input and output sequences known a-posteriori. This paper extends previous results regarding individual channels by presenting a rate function for the MIMO individual channel, and showing its achievability in a fixed transmission rate communication scenario.

0 citations0 reviewsNo code linkedOpen access