Jarosław Duda (Polish pronunciation: ), also known as Jarek Duda, is a Polish

computer scientist A computer scientist is a scientist who specializes in the academic study of computer science. Computer scientists typically work on the theoretical side of computation. Although computer scientists can also focus their work and research on ...

and an

assistant professor Assistant professor is an academic rank just below the rank of an associate professor used in universities or colleges, mainly in the United States, Canada, Japan, and South Korea. Overview This position is generally taken after earning a doct ...

at the Institute of Computer Science and Computational Mathematics of the

Jagiellonian University The Jagiellonian University (, UJ) is a public research university in Kraków, Poland. Founded in 1364 by Casimir III the Great, King Casimir III the Great, it is the oldest university in Poland and one of the List of oldest universities in con ...

Kraków , officially the Royal Capital City of Kraków, is the List of cities and towns in Poland, second-largest and one of the oldest cities in Poland. Situated on the Vistula River in Lesser Poland Voivodeship, the city has a population of 804,237 ...

. He is known as the inventor of

asymmetric numeral systems Asymmetric numeral systems (ANS)J. Duda, K. Tahboub, N. J. Gadil, E. J. Delp''The use of asymmetric numeral systems as an accurate replacement for Huffman coding'' Picture Coding Symposium, 2015.J. Duda''Asymmetric numeral systems: entropy coding ...

(ANS), a family of

entropy encoding In information theory, an entropy coding (or entropy encoding) is any lossless data compression method that attempts to approach the lower bound declared by Shannon's source coding theorem, which states that any lossless data compression method ...

methods widely used in

data compression In information theory, data compression, source coding, or bit-rate reduction is the process of encoding information using fewer bits than the original representation. Any particular compression is either lossy or lossless. Lossless compressi ...

Life and career

He was born in

Dębica Dębica (; ''Dembitz'') is a town in southeastern Poland with 44,692 inhabitants as of December 2021. It is the capital of Dębica County. Since 1999 it has been situated in the Podkarpackie Voivodeship; it had previously been in the Tarnów Voiv ...

Subcarpathian Voivodeship Subcarpathian Voivodeship is a Voivodeships of Poland, voivodeship, or province, in the southeastern corner of Poland. Its administrative capital and largest city is Rzeszów. Along with the Marshal, it is governed by the Subcarpathian Regional As ...

, Poland. In 1999, he graduated from King Władysław Jagiełło High School No. 1 in Dębica. In 2004, he obtained an MSc degree in computer science, in 2005 in pure mathematics, in 2006 in physics, all from the

in Kraków. In 2010, he obtained a

Doctor of Philosophy A Doctor of Philosophy (PhD, DPhil; or ) is a terminal degree that usually denotes the highest level of academic achievement in a given discipline and is awarded following a course of Postgraduate education, graduate study and original resear ...

degree in

theoretical computer science Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation. It is difficult to circumscribe the theoretical areas precisely. The Associati ...

, then in 2012 doctorate in

theoretical physics Theoretical physics is a branch of physics that employs mathematical models and abstractions of physical objects and systems to rationalize, explain, and predict List of natural phenomena, natural phenomena. This is in contrast to experimental p ...

from the same university. In 2013, he received a one-year postdoctoral fellowship at the NSF Center for Science of Information of the

Purdue University Purdue University is a Public university#United States, public Land-grant university, land-grant research university in West Lafayette, Indiana, United States, and the flagship campus of the Purdue University system. The university was founded ...

at the invitation from Wojciech Szpankowski. In 2015, he was appointed an assistant professor at the Institute of Computer Science and Computational Mathematics of the Jagiellonian University.

Invention of ANS

Between 2006 and 2014 he developed a family of

entropy coding In information theory, an entropy coding (or entropy encoding) is any lossless data compression method that attempts to approach the lower bound declared by Shannon's source coding theorem, which states that any lossless data compression method ...

methods called

, mainly used in

, which has become widely used in electronic devices due to improved performance compared to previous methods. ANS combines the compression ratio of

arithmetic coding Arithmetic coding (AC) is a form of entropy encoding used in lossless data compression. Normally, a String (computer science), string of characters is represented using a fixed number of bits per character, as in the American Standard Code for In ...

(which uses a nearly accurate

probability distribution In probability theory and statistics, a probability distribution is a Function (mathematics), function that gives the probabilities of occurrence of possible events for an Experiment (probability theory), experiment. It is a mathematical descri ...

), with a processing cost similar to that of

Huffman coding In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The process of finding or using such a code is Huffman coding, an algorithm developed by ...

. In the tabled ANS (tANS) variant, this is achieved by constructing a

finite-state machine A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...

to operate on a large alphabet without using multiplication. ANS is used in many products of leading technology companies such as

Apple An apple is a round, edible fruit produced by an apple tree (''Malus'' spp.). Fruit trees of the orchard or domestic apple (''Malus domestica''), the most widely grown in the genus, are agriculture, cultivated worldwide. The tree originated ...

Facebook Facebook is a social media and social networking service owned by the American technology conglomerate Meta Platforms, Meta. Created in 2004 by Mark Zuckerberg with four other Harvard College students and roommates, Eduardo Saverin, Andre ...

Google Google LLC (, ) is an American multinational corporation and technology company focusing on online advertising, search engine technology, cloud computing, computer software, quantum computing, e-commerce, consumer electronics, and artificial ...

, and

Linux Linux ( ) is a family of open source Unix-like operating systems based on the Linux kernel, an kernel (operating system), operating system kernel first released on September 17, 1991, by Linus Torvalds. Linux is typically package manager, pac ...

, for example to encode information in Facebook Zstandard, Apple LZFSE,

CRAM Cram may refer to: * Cram (surname), a surname, and list of notable persons having the surname * Cram.com, a website for creating and sharing flashcards * ''Cram'' (Australian game show), a television show * ''Cram'' (game show), a TV game show ...

JPEG XL The JPEG XL Image Coding System is a royalty-free open standard for a image compression, compressed Raster graphics, raster image format. It defines a graphics file format and the abstract device for coding JPEG XL bitstreams. It is developed by t ...

popular data compressors. Duda's intention has been to keep ANS patent-free and available for public use. In 2018, his lobbying helped convince Google to abandon its ANS-related patent claim in the US and Europe. However, in 2022,

Microsoft Microsoft Corporation is an American multinational corporation and technology company, technology conglomerate headquartered in Redmond, Washington. Founded in 1975, the company became influential in the History of personal computers#The ear ...

received a US patent covering modifications to a data-encoding technique called rANS, one of several variants in the Asymmetric Numeral System, introduced by Duda in 2013.J. Duda
''Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding''
arXiv:1311.2540, 2013. In an interview with ''The Register'', Duda raised his concerns about the potential diminished utility of ANS as software developers might try to avoid a potential infringement claim.

Awards

In 2021, he became the recipient of the annual City of Kraków Award for his exceptional achievements in computer science.

References

{{DEFAULTSORT:Duda, Jarosław Living people Polish computer scientists Polish inventors People from Dębica Jagiellonian University alumni Year of birth missing (living people)

Life and career

Invention of ANS

Awards

See also

References