Dr Jarosław
Duda (Jarek Duda)
Assistant professor at Institute of
Computer Science (adiunkt),
Jagiellonian University
email:
jaroslaw.duda[at]uj.edu.pl
arXiv,
GitHub, lectures, LinkedIn, ORCID, RGate, Scholar,
stack, USOS, Wikipedia,
Wolfram –
introductions to some my topics with demonstrations and basic code
Short CV:
2015- Jagiellonian
University, Institute of Computer Science, assistant professor,
2013-2014 Purdue
University, NSF 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)
Recent main 3 research directions:
1) 2WQC: two-way quantum computers (intro,
XPRIZE team, 3-SAT solver, slides,
talk) – improvement
adding CPT analog of state preparation (postparation) e.g. by reversing EM
impulse used for state preparation. In theory 2WQC is much more powerful, e.g.
allowing to solve NP problems.
2) Multidirectional joint distribution
neural networks (paper, intro to HCR, to HCRNN, slides,
talk) based on HCR
(hierarchical correlation reconstruction) with 3 biology-like properties:
multidirectional propagation, of values and probability distributions, with
additional training approaches like information
bottleneck.
3) Particle models as liquid
crystal-like topological excitations (paper, intro, slides,
talk) – while current
view on Standard Model is through perturbative approximations, more fundamental
would be non-perturbative: asking for field configurations of all the
particles, to finally consider their Feynman ensembles. Liquid crystals bring
surprisingly good correspondence with the Standard Model, starting with charge
quantization as topological, explored here through Landau-de Gennes-like model
with EM-like/skymion Lagrangian.
Other research topics:
Information theory/statistical physics - for my last MSc ([1] is its
translation) I have worked on optimal encoding with constraints on a lattice
(multidimensional generalization of Fibonacci coding), for example to improve
storage capacity by more precise head positioning. The maximizing capacity way
to choose statistical model (Maximal
Entropy Random Walk – Wikipedia,
2018 article) was further
developed for applications in physics as my second PhD. This 2006 MSc thesis
has also started ANS coding and has lead me to a few new coding approaches (slides):
-
Asymmetric Numeral Systems (ANS,
Wikipedia,
PLlinks, materials, JU
promotional animation, poster, introduction)
family of entropy coders (heart of
data compressors). Previously a compromise was needed: Huffman coding allowed
for fast but suboptimal compression, arithmetic coding for nearly optimal but
slow (costly). ANS offers compression ratio as arithmetic coding, at similar
speed/cost as Huffman coding. For example Facebook ZSTD (also used e.g. in
Linux kernel, Android
operating system, was standardized
for email/html) and Apple LZFSE (default in macOS and iOS) use Finite State Entropy implementation of tANS variant, CRAM DNA compressor of European Bioinformatics Institute, Google Draco and JPEG XL next generation image compression,
Dropbox
DivANS 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
use statistical constraints, for example enforcing resemblance with a given
picture (grayness of a pixel becomes probability of using 1 in its position).
Natural applications 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
levels 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.
Machine learning – searching for mathematically more sophisticated, but
still practical methods. For example molecular
shape descriptors (slides) for
virtual screening – parametrization of shape by fitting general bending of
molecule, then modelling cross-section as evolving ellipse.
-
Hierarchical Correlation Reconstruction (HCR, slides, talk, introduction)
family of methods for prediction of (multivariate) probability densities by
spitting dependencies into mixed moments, their time evolution. Perfect e.g.
for systematic enhancement of ARMA/ARCH-like models: with proper tail handling,
approaching any real joint distribution, allowing to model its time evolution
for non-stationary time series – for example for predicting probability distribution of
values in time series, also multivariate
and credibility evaluation by
modelling conditional distribution, nonstationarity
analysis, multi-feature
(auto)correlation analysis, and many others.
-
SGD Online Gradient Regression (OGR, slides, github, talk, introduction)
optimizer family e.g for neural network training - currently dominated by 1st
order methods with heuristic modifications like ADAM updating 2 averages. OGR
approaches update e.g. 4 averages instead, this way providing real 2nd order
method: ideally optimizing parabolas/paraboloids in a single steps, providing
much faster convergence.
Maximal Entropy Random Walk (Wikipedia,
last
PhD, 2018 article, slides, talk, introduction, application to 2D Ising model, electron diffusion p-n junction (diode)
model, introduction):
standard stochastic models are based on philosophy that the object performs
successive random decisions using probabilities chosen arbitrarily by us. In
contrast, in statistical physics 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 contrast 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. Here is conductance
simulator to compare both philosophies.
Complex Base Numeral Systems (first two MSc-s, slides, presentation, introduction) :
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].
Other interests and hobbies:
-
P vs NP, graph isomorphism
problem, (also for quantum
computing), Markov
fields, DNA reconstruction.
-
Biology, e.g. evolutionism, neurobiology, biochemistry. For
example chiral life concept (Wikipedia) – as
a computer scientist, while starting studying genetics I thought about
modifying the rules how triples of nucleotides are translated into amino-acids,
to get immunity by incompatibility with our viruses. This approach has a lot of
issues, but later in 2007 it has lead me to the possibility of synthesizing
mirror version of standard cells (original forum post). It turns out that the race has recently started,
e.g. in 2016 reaching synthesis of mirror polymerase (enantiomer). While mirror
life carries enormous new possibilities including pathogen-immune humans, the
dangers of such synthetic life may include eradication of our life – mirror
photosynthesizing cyanobacteria could dominate our ecosystem. Hence, I believe
there is now required a wide discussion about the ongoing race to this
synthesis.
-
Others: dancing, climbing, 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) (slides)
[13] J. Duda, From Maximal Entropy Random
Walk to quantum thermodynamics, J. Phys.: Conf. Ser. 361 012039 (2012)
[14] J. Duda, Asymmetric numeral systems:
entropy coding combining speed of Huffman coding with compression rate of
arithmetic coding, arXiv:1311.2540 (2013) (slides)
[15] Y. Baryshnikov, J. Duda, W.
Szpankowski, Markov Fields Types and Tilings, ISIT
2014 (2014)
[16] J. Duda, N. Gadgil, K. Tahboud, E. J.
Delp, Generalizations of the Kuznetsov-Tsybakov problem for generating
image-like 2D barcodes, ICIP 2014 (2014)
[17] J. Duda, Joint error
correction enhancement of the Fountain Codes concept, arXiv:1505.07056 (2015)
[18] J. Duda, Normalized rotation shape descriptors and
lossy compression of molecular shape, arXiv:1505:09211 (2015) (slides)
[19] 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)
[20] J. Duda, G. Korcyl, Designing
dedicated data compression for physics experiments within FPGA already used for
data acquisition, arXiv:1511.00856 (2015)
[21] 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)
[22] J. Duda, W.
Szpankowski, A. Grama, Fundamental Bounds and Approaches to Sequence
Reconstruction from Nanopore Sequencers, arXiv:1601.02420 (2016)
[23] J. Duda, Distortion-Resistant Hashing for rapid
search of similar DNA subsequence, arXiv:1602.05889 (2016)
[24] Y. Baryshnikov, J. Duda, W. Szpankowski, Types of Markov Fields
and Tilings, IEEE
Transactions of Information Theory volume 62, issue 8 (PDF) (2016)
[25] J. Duda, Nonuniform probability modulation for
reducing energy consumption of remote sensors, arXiv:1608.04271
(2016)
[26] J. Duda, Practical estimation of rotation distance
and induced partial order for binary trees, arXiv:1610.06023 (2016)
[27] A. Magner,
J. Duda, W. Szpankowski, A. Grama, Fundamental Bounds for Sequence
Reconstruction from Nanopore Sequencers, IEEE Transactions on
Molecular, Biological, and Multi-Scale Communications (2016)
[31] J. Duda, Improving Pyramid Vector
Quantizer with power projection, arXiv:1705.05285 (2017)
[32] J. Duda, Four-dimensional
understanding of quantum mechanics and computation, arXiv:0910.2724v2
(2017)
[33] J. Duda, Polynomial-based rotation
invariant features, arXiv:1801.01058 (2018)
[34] J. Duda, Hierarchical correlation
reconstruction with missing data, for example for biology-inspired neuron, arXiv:1804.06218
(2018) (slides)
[36] J. Duda, M. Snarska, Modeling joint probability
distribution of yield curve parameters, arXiv:1807.11743 (2018)
[37] J. Duda, Gaussian Auto-Encoder, arXiv:1811.04751
(2018) (slides)
[38] J. Duda, A. Szulc, Credibility evaluation
of income data with hierarchical correlation reconstruction, arXiv:1812.08040
(2018) (slides)
[64] J. Duda, S. Podlewska, Prediction of
probability distributions of molecular properties: towards more efficient
virtual screening and better understanding of compound representations, Molecular
Diversity (2022)
[65] J. Duda, M. Niemiec, Lightweight
compression with encryption based on asymmetric numeral systems, AMCS vol 33
(2023)
[66] J. Duda, Adaptive Student’s
t-distribution with method of moments moving estimator for nonstationary time
series, arXiv:2304.03069
(2023) (slides,
talk)
[67] J. Duda, Time delay multi-feature
correlation analysis to extract subtle dependencies from EEG signals, arXiv:2305.09478 (2023)
[68] J. Duda, Two-way quantum computers adding CPT analog of state preparation,
arXiv:2308.13522 (2023) (slides,
talk)
[69] J. Duda, Extracting individual
variable information for their decoupling, direct mutual information and
multi-feature Granger causality, arXiv:2311.13431
(2023)
[70] J. Duda, Phase space maximal entropy
random walk: Langevin-like ensemble of physical trajectories, arXiv:2401.01239 (2024)
[71] J. Duda, Simple inexpensive vertex
and edge invariants distinguishing dataset strongly regular graphs, arXiv:2402.04916 (2024)
[72] J. Duda, J. Leśkow, P. Pawlik, W.
Cioch, CMAFI — Copula-based Multifeature Autocorrelation Fault Identification
of rolling bearing, Mechanical
Systems and Signal Processing (2024)
[73] J. Duda, G. Bhatta, Predicting
conditional probability distributions of redshifts of Active Galactic Nuclei
using Hierarchical Correlation Reconstruction, Monthly
Notices of the Royal Astronomical Society Main Journal (2024)
[74] J. Duda, Biology-inspired joint
distribution neurons based on Hierarchical Correlation Reconstruction allowing
for multidirectional neural networks, arXiv:2405.05097 (2024) (slides,
talk)
[75] M. Noor, J. Duda, No-cloning theorem for 2WQC and postselection, arXiv:2407.15623 (2024)
[76] J. Duda, 3-SAT solver for two-way
quantum computers, arXiv:2408.05812
(2024)
[77] A. Mahboubi, S. Camtepe, K. Ansari,
M. Pawłowski, P. Morawiecki, H. Aboutorab, J. Pieprzyk, J. Duda, Shared file
protection against unauthorised encryption using a Buffer-Based Signature
Verification Method, Journal
of Information Security and Applications (2024)
[78] A. Mahboubi, S. Camtepe, K. Ansari, M. Pawłowski, P. Morawiecki, J. Duda,
J. Pieprzyk, File System Shield (FSS): A Pass-Through Strategy Against Unwanted
Encryption in Network File Systems, Advances
in Information and Computer Security (2024)
[79] J. Duda, Testing stimulated emission
photon direction, arXiv:2409.15399 (2024)
My interactive demonstrations
presenting some my work in intuitive way: https://community.wolfram.com/web/dudaj
:
Some my implementations: https://github.com/JarekDuda,
video lectures: https://www.youtube.com/channel/UCbajruVGXJ7lsJKHPcqE7Cw
Quantum foundations seminar
(old), now QM Foundations
& Nature of Time seminar