Archive for Language and mathematics

The paradox of hard and easy

If you're interested in one-way functions and Kolmogorov complexity, you'll probably want to read this mind-crunching article:

"Researchers Identify ‘Master Problem’ Underlying All Cryptography", by Erica Klarreich, Quanta Magazine (April 6, 2022)

The existence of secure cryptography depends on one of the oldest questions in computational complexity.

To ease our way, here are brief descriptions of the two key terms:

In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems. Not being one-to-one is not considered sufficient for a function to be called one-way….


In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of a shortest computer program (in a predetermined programming language) that produces the object as output. It is a measure of the computational resources needed to specify the object, and is also known as algorithmic complexity, Solomonoff–Kolmogorov–Chaitin complexity, program-size complexity, descriptive complexity, or algorithmic entropy. It is named after Andrey Kolmogorov, who first published on the subject in 1963.


Read the rest of this entry »

Comments (17)

Kurt Reillag and House of Cats and Dogs

A recent email from my colleague Jean Gallier explains why the new edition of Discrete Mathematics is available on his website:

A bit more that three years ago, Springer suggested that I revise my
“Discrete Mathematics” (published in 2010).
Unfortunately, Jocelyn and I
waited too long and now that we are done
Springer no longer wants it.

I added a chapter on probability theory and made some
significant changes (improvements!). I also changed the title.
There is even an intro to the simply-typed lambda-calculus!
In any case, temporarily I am falling back on the little known publisher
“Kurt Reillag and House of Cats and Dogs”.

Interested readers may observe a certain relationship between "Reillag" and "Gallier", and in any case web search will turn up Reillag's home page — which provides this post's main linguistic relevance.

Read the rest of this entry »

Comments (9)

Odevity or parity

[This is a guest post by Jeffrey Shallit]

A Chinese student here at Waterloo used the term "odevity" for what English-speaking computer scientists typically call "parity" — the property of an integer being odd or even.

I had never heard this term before, so I used Google Scholar to look at where it is being used.  It is used almost exclusively by Chinese engineers, mathematicians, and computer scientists.  The first usage I was able to find with Google Book Search was in 1972, obtained with this search.

Read the rest of this entry »

Comments (23)