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,
20132014 Purdue University, Center for Science of
Information, Postdoctoral researcher,
20062012 Jagiellonian University, Cracow, PhD in
Theoretical Physics (thesis)
20042010 Jagiellonian University, Cracow, PhD in
Theoretical Computer Science (thesis)
20012006 Jagiellonian University, Cracow, MSc in
Theoretical Physics (thesis)
20002005 Jagiellonian University, Cracow, MSc in
Theoretical Mathematics (thesis)
19992004 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 to my
work on a few new coding approaches
(slides):

Asymmetric
Numeral Systems (ANS, slides, PCS article) family of entropy coders. 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 Apple LZFSE (= LempelZiv +
Finite State Entropy), which is
the default compressor since iOS9 and OS X 10.11, uses 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 KuznetsovTsybakov 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 QRlike 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 reallife 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 stateofart
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 MScs)
: 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 continuoustime 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,
Fourdimensional 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 hashorigin 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),
[17] J. Duda, P. Korus, N. J. Gadgil, K. Tahboub, E. J. Delp, ImageLike 2D Barcodes Using Generalizations Of The KuznetsovTsybakov 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),
[20] Y. Baryshnikov, J. Duda,
W. Szpankowski, Types of Markov
Fields and Tilings, IEEE
Transactions of Information Theory volume 62, issue 8 (PDF)
(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 KuznetsovTsybakov
problem for generating imagelike 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 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