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 (webpage),

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 a 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 me to a few **new coding approaches** (slides):

- Asymmetric Numeral Systems
(**ANS**, **Wikipedia
article**, slides, PCS article) family of **entropy coders **(heart of data
compressors). Previously a compromise was required: Huffman coding allowed for
fast but suboptimal compression, arithmetic coding for nearly optimal but slow
(costly). ANS offers compression ratios as arithmetic coding, at similar speed
as Huffman coding. Here is a list of implementations and compressors switched to
ANS. For example Facebook
ZSTD and Apple LZFSE use Finite State Entropy
implementation of tANS variant, CRAM
3.0 genetic data compressor of European
Bioinformatics Institute and experimental
branch of Google VP10 video codec use rANS
variant. Additionally, chaotic behavior of tANS
makes it also perfect for simultaneous encryption,

- 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 also use statistical
constraints, for example enforcing resemblance to a given picture (grayness of
a pixel becomes probability of using 1 at this position). A natural application
are various **watermarking/steganography **purposes,
for example to generate **QR-like codes
resembling a chosen image** (implementation
, ICIP paper, IEEE
Forensics & Security paper),

- 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 individual
damage levels of packets – this knowledge is required in standard approach to
choose redundancy levels, 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.
Introduced continuous family of rates based on Renyi
entropy allow to estimate statistical behavior of decoding (Pareto
coefficient),

- 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**.

**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 **(Jaynes), or equivalently: choosing e.g. canonical
ensemble, getting recent Maximal Entropy Random Walk (MERW) and its extensions.
Thanks of constructing models finally fulfilling this
fundamental mathematical requirement, 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) (slides),

[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) (slides),

[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] J. Duda, Joint error correction enhancement of
the Fountain Codes concept, *arXiv:1505.07056* (2015),

[15] J. Duda, Normalized
rotation shape descriptors and lossy compression of
molecular shape, *arXiv:1505:09211* (2015) (slides),

[16] J. Duda, G. Korcyl, Designing dedicated data compression for physics experiments
within FPGA already used for data acquisition, *arXiv:1511.00856*
(2015),

[17] J. Duda, P. Korus, N. J. Gadgil, K.
Tahboub, E. J. Delp, Image-Like
2D Barcodes Using Generalizations Of The Kuznetsov-Tsybakov Problem, *IEEE
Transactions on Information Forensics & Security* volume 11, issue 4
(2016),

[18] J. Duda, W. Szpankowski,
A. Grama, Fundamental Bounds and Approaches to
Sequence Reconstruction from Nanopore Sequencers, *arXiv:1601.02420* (2016),

[19] J. Duda, Distortion-Resistant
Hashing for rapid search of similar DNA subsequence, *arXiv:1602.05889*
(2016),

[20] Y. Baryshnikov, J. Duda, W. Szpankowski,
Types of Markov Fields and Tilings, *IEEE
Transactions of Information Theory* volume 62, issue 8 (PDF) (2016),

[21] J. Duda, Nonuniform probability modulation for reducing energy consumption
of remote sensors, *arXiv:1608.04271** *(2016),

[22] J. Duda, Practical
estimation of rotation distance and induced partial order for binary trees, *arXiv:1610.06023*
(2016).

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),

Here are 8 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