dr Jarosław Duda

Assistant
professor at Institute of Computer Science, Jagiellonian University

email: jaroslaw.duda[at]uj.edu.pl

Short CV:

2015- Jagiellonian University, Institute
of Computer Science, assistant professor,

2013-2014 Purdue University, Center for Science of
Information, Postdoctoral researcher,

2006-2012 Jagiellonian University, Cracow, PhD in
Theoretical Physics (thesis)

2004-2010 Jagiellonian
University, Cracow, PhD in Theoretical Computer Science (thesis)

2001-2006 Jagiellonian University, Cracow, MSc in
Theoretical Physics (thesis)

2000-2005 Jagiellonian
University, Cracow, MSc in Theoretical Mathematics (thesis)

1999-2004 Jagiellonian
University, Cracow, MSc in Computer Science (thesis)

Main
research areas:

**Information theory/statistical
physics** - for my
last MSc ([1] is its translation) I have worked on optimal encoding with
constraints on a lattice (kind of generalization of Fibonacci coding), for
example to improve storage media capacity by more precise head positioning. The
maximizing capacity way to choose the stochastic matrix (**Maximal Entropy Random Walk**) was further developed for applications
in physics as my second PhD. This thesis has also started ANS and lead to my
work on a few **new coding approaches**
(slides):

- **Asymmetric
Numeral Systems** (**ANS**, slides, PCS article): new approach to entropy
coding. Previously, Huffman coding allowed for fast but suboptimal compression,
arithmetic coding for nearly optimal but slow. ANS offers nearly optimal
compression ratio at even better speeds than Huffman coding. Here is a list of implementations and
compressors switched to ANS. For example Apple LZFSE
(= Lempel-Ziv + Finite State Entropy) compressor uses Finite State Entropy
implementation of tANS variant, CRAM 3.0 genetic data
compressor of European Bioinformatics Institute uses rANS variant. Additionally,
chaotic behavior of tANS makes it also perfect for simultaneous encryption.

- **Correction
Trees** philosophy as
improvement of sequential decoding for convolutional codes: using larger state
and bidirectional decoding, making it complementary alternative for state-of-art
method (implementation). It also allows to handle synchronization
errors like deletion channel.

- **Constrained Coding**: generalization of the Kuznetsov-Tsybakov
problem: allowing to encode a message under some constraints, which are known
only to the sender. This generalization allows to use statistical constraints,
for example enforcing resemblance to a picture (grayness of a pixel becomes
probability of using 1 at this position). It can be used for various watermarking/steganography
purposes, like to generate QR-like codes resembling given picture (implementation , ICIP article),

- **Joint Reconstruction Codes** (JRC, implementation): enhancement of the Fountain
Codes concept, which allows to reconstruct a message from any large enough
subset of packets. JRC additionally doesn’t need the sender to know the final
damage levels of packets – this knowledge is required in standard approach to
choose redundancy level, but is often inaccurate or unavailable in real-life
scenarios. For example while writing a storage medium we usually don’t know how
badly it will be damaged while reading. JRC allows the receivers to adapt to
the actual noise levels, treated as independent trust level for each packet
while their joint reconstruction/error correction. Continuous family of rates
based on Renyi entropy allow to estimate statistical behavior of decoding (Pareto
coefficient).

**Maximal Entropy Random Walk** (last PhD, here is preliminary version, here is presentation): standard
stochastic models are based on philosophy that the object performs succeeding
random decisions using probabilities assumed by us, while in thermodynamics
this randomness only represents our lack of knowledge. Such models should be based
on the maximal entropy principle, or equivalently: choosing e.g. canonical
ensemble, getting recent Maximal Entropy Random Walk (MERW) and its expansions.
Thanks of constructing models finally fulfilling these universal mathematical
principles, in opposite to standard approach (which can be seen as
approximation), we finally get agreement with thermodynamical expectations of
quantum mechanics, like thermalization to the quantum mechanical ground state
probability density and Born rule: ‘squares’ relating amplitudes and
probabilities. My work on this subject has started with my physics MSc thesis
([1] is its translation), where the equations were found for information theory
applications. The topic is continued in [5], [7], [8] and [9]. Here
is conductance simulator to compare both philosophies.

**soliton particle models **(slides)**: **Skyrme has made popular the search for alternative approach to
particle models – starting not as
usually with leading to many mathematical problems QFT perturbative
approximation, but with trying to understand the configuration of fields
building the particle (e.g. electromagnetic), which generally should maintain
its structure (be a soliton), for example because of topological constraints
for spin and charge. Standard skyrmion approach introduces separate fields to
model single mesons or baryons – the perfect situation would be having just a
single field, which soliton family corresponds to our whole particle menagerie
and their dynamics with topological charges as quantum numbers. Working on MERW
has lead me to simple model which surprisingly well fulfills these requirements
– ellipsoid field ([7]). Here is short essay about it and presentation.

Complex
Base Numeral Systems (first two
MSc-s) : probably complete family of positional numeral systems with complex
base, which are ‘proper’ – representation function from digit sequences into a complex
plane is surjective and injective everywhere but a zero measure set (it’s
unavoidable, like 0.999(9)=1.000(0) ). Fractional part occurs to be simple
Iterated Function System (fractal). I have also introduced practical methods
for arithmetic in this representation, analytical tool to work with convex hull
of such simple fractals, to get analytical
formulas for Hausdorff dimension of boundary of such sets and briefly generalization
into higher dimensions. It is described in [2] and [3], here is
presentation about it.

Other
interests and hobbies:

algorithm
complexity – family of new simple invariants for graph isomorphism problem [4],
approaches to P=NP problem (like translating into just continuous global
optimization of low degree polynomial – forum
post), to
understand the strength of quantum computation (forum
post), searching
for new physical computation concepts (like continuous-time loop computers – forum
post),

biology –
evolutionism, neurobiology, biochemistry (e.g. chiral life concept – forum
post),

Others: climbing,
salsa, biking, fencing, photography

Articles:

[1] J. Duda,
Optimal encoding on discrete lattice with translational invariant constrains
using statistical algorithms, *arXiv:0710.3861* (2007),

[2] J. Duda,
Analysis of the convex hull of the attractor of an IFS, *arXiv:0710.3863* (2007),

[3] J. Duda,
Complex base numeral systems, *arXiv:0712.1309** *(2007),

[4] J. Duda,
Combinatorial invariants for graph isomorphism problem, *arXiv:0804.3615** *(2008),

[5] Z.
Burda, J. Duda, J. M. Luck, B. Wacław, Localization of the Maximal Entropy
Random Walk, *Phys.
Rev. Lett. 102, 160602** *(2009),

[6] J. Duda,
Asymmetric numeral systems, *arXiv:0902.0271* (2009),

[7] J. Duda,
Four-dimensional understanding of quantum mechanics, *arXiv:0910.2724* (2009),

[8] Z.
Burda, J. Duda, J. M. Luck, B. Wacław, The various facets of random walk
entropy, *Acta Phys. Polon. B. 41/5* (2010),

[9] J. Duda,
From Maximal Entropy Random Walk to quantum thermodynamics, *arXiv:1111.2253* (2011) (presentation),

[10] J.
Duda, P. Korus, Correction Trees as an Alternative to Turbo Codes and Low
Density Parity Check Codes, *arXiv: 1204.5317* (2012),

[11] J.
Duda, Optimal compression of hash-origin prefix trees, *arXiv:1206.4555** *(2012) (presentation),

[12] J.
Duda, Embedding grayscale halftone pictures in QR Codes using Correction Trees,
*arXiv:1211.1572* (2012) (presentation),

[13] J.
Duda, Asymmetric numeral systems: entropy coding combining speed of Huffman
coding with compression rate of arithmetic coding, arXiv:1311.2540 (2013) (presentation),

[14] Y. Baryshnikov, J. Duda, W. Szpankowski, Types of Markov Fields and Tilings,
submitted to IEEE Transactions of Information Theory (PDF)
(2014),

[15] J. Duda, Joint error correction enhancement of the Fountain
Codes concept, arXiv:1505.07056
(2015),

Conference
papers:

[1] J. Duda,
From Maximal Entropy Random Walk to quantum thermodynamics, J. Phys.: Conf. Ser. 361 012039 (2012),

[2] Y.
Baryshnikov, J. Duda, W. Szpankowski, Markov Fields Types and Tilings, ISIT 2014 (2014),

[3] J. Duda,
N. Gadgil, K. Tahboud, E. J. Delp, Generalizations of the Kuznetsov-Tsybakov
problem for generating image-like 2D barcodes, ICIP 2014 (2014),

[4] J. Duda,
N. Gadgil, K. Tahboud, E. J. Delp, The use of Asymmetric Numeral Systems as an
accurate replacement for Huffman coding, PCS 2015, (PDF),

[5] J.
Duda, W. Szpankowski, A. Grama, Fundamental Bounds and Approaches to Sequence Reconstruction
from Nanopore Sequencers, submitted to ISMB 2015 (PDF)
(2015).

Here are 6
simulators presenting subjects I worked on in intuitive, interactive way:

http://demonstrations.wolfram.com/author.html?author=Jarek+Duda

Some my implementations: https://github.com/JarekDuda