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

Bruno Bauwens

Bruno Bauwens contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Information Theorymath.ITComputational Complexitymath.LO

Trust snapshot

Quick read

Trust 17 - UnverifiedVerification L1Unclaimed author
4works
0followers
4topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

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

4 published item(s)

preprint2022arXiv

Inequalities for space-bounded Kolmogorov complexity

There is a parallelism between Shannon information theory and algorithmic information theory. In particular, the same linear inequalities are true for Shannon entropies of tuples of random variables and Kolmogorov complexities of tuples of strings (Hammer et al., 1997), as well as for sizes of subgroups and projections of sets (Chan, Yeung, Romashchenko, Shen, Vereshchagin, 1998--2002). This parallelism started with the Kolmogorov-Levin formula (1968) for the complexity of pairs of strings with logarithmic precision. Longpré (1986) proved a version of this formula for space-bounded complexities. In this paper we prove an improved version of Longpré's result with a tighter space bound, using Sipser's trick (1980). Then, using this space bound, we show that every linear inequality that is true for complexities or entropies, is also true for space-bounded Kolmogorov complexities with a polynomial space overhead.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Precise Expression for the Algorithmic Information Distance

We consider the notion of information distance between two objects $x$ and $y$ introduced by Bennett, Gács, Li, Vitányi, and Zurek in 1998 as the minimal length of a program that computes $x$ from $y$ as well as computing $y$ from $x$. In this paper, it was proven that the distance is equal to $\max (K(x|y),K(y|x))$ up to additive logarithmic terms, and it was conjectured that this could not be improved to $O(1)$ precision. We revisit subtle issues in the definition and prove this conjecture. We show that if the distance is at least logarithmic in the length, then this equality does hold with $O(1)$ precision for strings of equal length. Thus for such strings, both the triangle inequality and the characterization hold with optimal precision. Finally, we extend the result to sets $S$ of bounded size. We show that for each constant~$s$, the shortest program that prints an $s$-element set $S \subseteq \{0,1\}^n$ given any of its elements, has length at most $\max_{w \in S} K(S|w) + O(1)$, provided this maximum is at least logarithmic in~$n$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The normalized algorithmic information distance can not be approximated

It is known that the normalized algorithmic information distance $N$ is not computable and not semicomputable. We show that for all $ε< 1/2$, there exist no semicomputable functions that differ from $N$ by at most~$ε$. Moreover, for any computable function $f$ such that $|\lim_t f(x,y,t) - N(x,y)| \le ε$ and for all $n$, there exist strings $x,y$ of length $n$ such that $\sum_t |f(x,y,t+1) - f(x,y,t)| \ge Ω(\log n)$. This is optimal up to constant factors. We also show that the maximal number of oscillations of a limit approximation of $N$ is $Ω(n/\log n)$. This strengthens the $ω(1)$ lower bound from [K. Ambos-Spies, W. Merkle, and S.A. Terwijn, 2019, Normalized information distance and the oscillation hierarchy], see arXiv:1708.03583 .

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

m-sophistication

The m-sophistication of a finite binary string x is introduced as a generalization of some parameter in the proof that complexity of complexity is rare. A probabilistic near sufficient statistic of x is given which length is upper bounded by the m-sophistication of x within small additive terms. This shows that m-sophistication is lower bounded by coarse sophistication and upper bounded by sophistication within small additive terms. It is also shown that m-sophistication and coarse sophistication can not be approximated by an upper or lower semicomputable function, not even within very large error.

0 citations0 reviewsNo code linkedOpen access