Theory that really DOES apply: Security.

I recently read and wrote a review of

                               Math for Security by Daniel Reilly.

(For the review see here. It will appear in SIGACT News at some later point. For the amazon link see here. Disclosure: Lance and I are Amazon Affiliates.)

The book had great example of using THEORY for PRACTICAL problems of security (NOT what you think as you will see later). Since I am always surprised (possibly because of my ignorance) when theory REALLY applied to PRACTICE I asked the author some questions which he answered. Our conversation is below.

BILL: I was surprised that a book called Math for Security didn't have crypto in it. Why was that?

DANIEL:
There's a plethora of excellent material that already covers the topic very well. Cracking codes and analyzing ciphers is the first thing most people think of when they think of the relationship between math and security. There are so many other topics where a little creativity and math can open up new avenues and approaches to unique problems we face in security. As an analyst and consultant, a very small percentage of my time goes into cryptographic systems, but I'm regularly asked other questions.  I'm hoping to show that anyone can apply a little math to start making better (or at least more informed) decisions in many of these areas, not just cryptography.

BILL: Many theorists dream of the day when someone comes along to REALLY use their stuff. For example---

DANIEL: (Cuts Bill off) That's funny. As an analyst I'm always hoping to define a theory which explains some system I've been analyzing. Something like Kim Rossmo's formula in Forensics
(see here). Understanding what your data is telling you is good, but discovering why, that's the pinnacle of accomplishment! I guess the grass is always greener on the other side of the fence!

BILL: The first time I saw the problem of determining the Betweeness Centrality of a node is, it was in a paper showing that it was APSP-hard (so likely not in subcubic time).  Hence I was AMAZED that you use it FOR REAL. How hard was it to take the THEORY that you found in the literature and APPLY it.

DANIEL: For the graph theory in the book, and in general, I think it comes down to some basic statistics and understanding the underlying system being modeled. Betweenness centrality is a great example. It's really easy to calculate, but what it means in practice is wholly dependent on what generated the data. A high Betweenness score in a social network is the result of a different underlying structure than in a computer network. This is one reason graph theory made sense as the place to start. There are so many problems that can be represented as a graph with very little change to the methodology needed, but it does show the need to be flexible in your interpretation of theory.
For the programming side, NetworkX is really well designed so I didn't have to do much to implement the algorithms. That made it easy to focus on showing off how the library could be used when analyzing a real data set. Of course, whenever you're taking a general theory and applying it to a specific problem, you'll always have some pieces you need to build. The pieces that glue the theory
and the data together in a useful way. For me, that is the fun part. The art behind the science. You can give 5 analysts the same problem and get back 10 possible approaches!

BILL: I recently looked at the Complexity of the Art Gallery Problem- it is ER-Complete (see Wikipedia entry on Existential Theory of the Reals) which is between NP and PSPACE. Hence I was AMAZED that you use it for REAL. How hard was it to take the THEORY that you found in the literature and APPLY it. For example, the Guards, unlike the Who (see here) cannot see for miles and miles and miles and miles and miles.  (NOTE: Spell check thinks that NP is a word, but PSPACE is not a word. Odd!)

DANIEL: You sound like a broken record. But still a good question. The Art Gallery Project was the one that kicked off the idea to write the book in the first place. I was looking for a method to analyze physical security layouts and I came across a paper describing the problem as it related to security camera placement. That led me to the original paper and then Fisk's paper using the greedy coloring algorithm. I think I read one or two more pieces about how greedy coloring is implemented in NetworkX, but that was it. Once you understand the basic problem formulation, and Fisk's method of solving for n-vertex polygons, you quickly move out of what the theory was designed for. The Art Gallery project therefore represents what I think is a more typical scenario. I'll often start with a
theoretical solution that makes a lot of simplifying assumptions and then remove the simplifications a little at a time by adding in other theoretical bits (such as adding a function to compute a more realistic guess at what area a guard can protect). Sometimes I will find complimentary research on modeling something like walking speed. Other times I rely on my experiences and best guess (like assigning the space for people at an event). At it's core though, the algorithm solving the layout is the same one suggested by Fisk and implemented in NetworkX.

BILL: Anything else you want to add?

DANIEL: There is a quote I love that gets thrown around in System Dynamics a lot It's better for a model to be useful, than accurate I think that idea applies really well when you're building proof-of-concept systems. For example, a model that is very accurate at predicting an adversary's behavior may not be very useful if it is too complex and expensive to use. Ultimately, the best model is the one that is most useful for solving the problem at hand. This means that it is important to consider other factors than accuracy, such as interpretability, cost, and ease of use, when developing your proofs. It's important to remember the goal is not to perfectly model the system your studying, but to model enough of the key components to get a useful response.

Saving Grace

The Grace Hopper Conference has grown to one of the largest in computer science, pushing past 25,000 attendees. Most women in computing, whether a student, faculty or working in industry, are usually in a minority. Grace Hopper gives them the chance to see and be part of a strong community of woman in our field in a safe and comforting environment.

Or so it was supposed to be. At the Expo part of last month's conference, where many companies come to recruit, men made up about 40% of the attendees according to an NPR report. Now Grace Hopper welcomes male allyship but these were no allies. Rather they acted, often aggressively, to reach recruiters and making the experience uncomfortable for the attendees who came for the conference's purpose.

The conference organizers released a statement and a blog post noting they can't legally limit registration based on gender but will work on other approaches to ensure a good conference in the future.

I know there are, in particular, graduating international students desperate to find a job so they can remain in the country. And I've argued that CS needs a full annual meeting, which like Grace Hopper exists to bring people together not to focus on research but to focus on each other. But none of this justifies ruining the experience of those who attend a conference for what it is. 

If you don't have respect, don't come to the party.

When did Math Get So Hard- Part 2

Click here for When did Math Get so Hard-Part 1, though it was not called Part 1 at the time. 

This post is not so much about WHEN math got so hard but an example of math BEING hard. The main issue is that so much is known that the PREREQUISITE knowledge can be overwhelming.

My interest in Hilbert's tenth problem (see here) and an email from Timothy Chow (reproduced in that article) lead me to the book

                               Rational Points on Varieties 

                                  by Bjorn Poonen

(see here for amazon link. Disclosure: Lance and I are amazon affiliates).

Here is the prerequisite for the book as stated in the preface: 

------------------------------------------

A person interesting in reading this book should have the following background:

1) Algebraic Geometry (e.g. [Har77]: up to Chapter II, Section 8 as a minimum, but familiarity with later chapters is also needed at time)--- this is not needed so much in our Chapter 1. 

2) Algebraic Number Theory (e.g., [Cas67], Fro67] or [Lan94, Part One] or [Neu99 Chapters I and II).

3) Some Group Co-homology (e.g. [AW67] or [Mil13], Chaper 2]). 

[AW67] M.F. Atiyah and I.G. Macdonald. Introduction to Commutative  Algebra, Addison-Wesley, 1969

[Cas67] J.W.S Cassels. Global Fields, Algebraic Number Theory (Proc. Instructional  Conf, Brighton), 1965), 1967, 42-84

[Fro67] A. Frolich, Local Fields, Algebraic Number Theory ((Proc. Instructional Conf, Brighton, 1965), 1967, 1-41.

[Har77] Robin Hartshore, Algebraic Geometry, Springer-Verlag, 1977, Graduate Texts in Mathematics, No. 52

[Lan94] Serge Lang, Algebraic Number Theory, 2nd ed. Grad Texts in Mathematics, Springer-Verlag. , 1994.

[Mil13] J.S. Milne, Class field theory (v4.02), March 23, 2013. Available at here

[Neu99] Jurgen Neukirch. Algebraic Number Theory,  Fundamental Principles of Mathematical Sciences Vol 332. 1999.

-------------------------------------------

This seems like quite steep prerequisites. I don't have them so perhaps they are easier than they look. 

But in any case, Some parts of math are hard because, over time, so much math is known that builds on earlier math, that just getting through the background material is hard. Comp Sci hasn't been around as long, but its been around in the 20th and 21st century when more was being produces, so its also gotten hard, as I discussed here. Note also that computer science uses some of that hard math, and is also an inspiration for some hard math.

Fall Jobs Post 2023

In the 2022 Fall Jobs Post I talked about the effect of generative AI and that was two weeks before Open AI released ChatGPT to the public. A year later, how will AI change CS faculty hiring? Not much this year but change will come soon enough.

CS enrollment remains strong and computer science departments have not been able to keep up with the demand. Many see programming, rightly or wrongly, as one of the first careers that AI will displace, which may reduce enrollment in the future, as offshoring fears drove CS enrollment down 20 years ago. There will be newish majors, whether Data Science, Artificial Intelligence, Machine Learning or something else that will draw students away from traditional CS degrees. But for now many CS departments still need to grow their faculty. 

Having some knowledge and being willing to teach ML will definitely help in the job search but I expect we'll see demand in all areas, including theoretical computer science. There will also be more people on the market, especially as the major tech leaders aren't yet brought back hiring in CS to its previous levels.

Should you use AI to help you apply? I wouldn't use AI to write your personal statement or other materials--it's style is just too recognizable. But do use AI to read over what you wrote and give suggestions. You might be surprised on what it recommends.

CS departments are not yet using AI to screen faculty job applications. So you are writing for humans. There are many applicants so focus on what makes you stand out.

As always, have a well-designed web page with all your job materials. Make sure your Google Scholar and LinkedIn pages are accurate and up to date. Add yourself you the CRA's CV Database.

Some departments are starting the search earlier, so don't delay your applications.

Most CS faculty jobs are posted to the CRA and ACM. The CRA focuses on jobs for PhDs, the ACM mixes it up with general industry jobs. For theorists, check out TCS Jobs and Theory Announcements. 

If you have a job to announce, please post to the above and/or feel free to leave a comment on this post. 

Paper is a tech-free way to preserve writing. Is there a tech-free way to preserve sound (e.g., music)

I blogged about ACM going mostly paper-free, and had some PROS and CONS about paper-free, in this blog here. One of my many astute readers named Abigail pointed out that paper does not go obsolete: we can still read books written many years ago without having to use some technology. (The first paper in Harry Lewis's book Ideas that Created the Future: Classic Papers in Computer Science was by Aristotle. See here for amazon link to the book and here for my review of the book). By contrast, there are stories of material being lost forever since they are on floppy disks. I wonder if pdf will suffer the same fate. 

However, that is not the theme of this post (do my posts have coherent themes?)

The point is 

PAPER is TECH-FREE and is good at preserving WRITING.

What about SOUND? Is there a Tech-Free way to preserve sound? I am thinking about music, though one can also wonder how old poetry was supposed to sound when read out loud. But back to music:

1) The Bible Psalms- we know the words, but not the medley. Psalms 45 has the following right before it: For the director of music. To the Tune of ``Lilies'' Of the Sons of Korah. A maskit. A wedding song. In my bible there is a footnote saying that maskit is Probably a literary or music term. Not helpful to a 21st century singer.

2) The first Rap Song is from the Bible, in 1 Samuel 18:7. The words are

Saul has slain his thousands and David his tens of thousands.

And again, we don't know the melody or the cadence or the rhythm. I have done a rendition of it for my Bible study group but they complained it was not authentic. They also told me to not quit my day job. 

3) When music went from 

Wax Cylinder to Vinyl and audio cassettes to CD to MP3 to Spotify (and similar systems)

some music was lost in each transition. Indeed, the inspiration for this post is the following personal story:

One of my hobbies is collecting and listening to  novelty songs (this has been mentioned in the following posts: here, here, here,,  here, here, here, here, here) Some are audio tape, some are CDs. A subgenre of novelty songs is Filk Music, which are folk songs with a science fiction (its been expanded to science) theme. They are often  sung at science fiction conventions. It is filklore that an early science fiction convention mistyped folk as filk and they decided to keep it.

I was thinking of a GREAT  filk song titled

Carl Sagan Ronald Reagan San Diegan Pagan (lyrics are here)

and I wondered

a) Do I have it in my collection? (Almost surely yes.)

b) If so can I listen to it? (If on CD then yes. If on audio tape, not sure.)  

c) In any case is it on Spotify or YouTube or...I have found obscure things on both  Spotify and YouTube  so this was plausible. Spellcheck insists I spell it YouTube not Youtube and I will of course obey the Spellcheck God.

ANSWERS

a) It is on Bayfilk Crazies, an AUDIO TAPE that I have. YEAH!

b) I have one audio tape player in my house that I had not used in years. It didn't work. BOO!

(ADDED LATER- I found at Tape Recorder where PLAY worked, though neither FF or REWIND worked. So I got to hear my song! And I was ``forced'' to hear other songs I had not heard for a while. Some were excellent gems I had forgotten about. Others... not so much. But I am happy for now.)

c) So far I cannot find it to listen to ANYWHERE on the web. BOO!

(If you find such a place please leave a comment!)

d) It does not appear to be on CD. BOO! (Again, if you can find a place to buy it on CD let me know.) 

SO, is this great song LOST TO HUMANITY? I know the tune, so I could sing it on YouTube, but there are enough badly sung songs on YouTube and I do not want to add to that. 

But my more important point is MANY SONGS ARE BEING LOST TO HUMANITY!

4) For many old songs we DO have sheet music and lyrics so someone COULD reproduce it. That's great. Is it important to have the authentic real Elvis recordings, or is a really good 21nd century Elvis Impersonator good enough? That depends what you want. And if the sheet music is only online we may have the same problem we are pondering about paper. 

 Famous songs are re-recorded a lot (To see what the most recorded song of all time is, see here. Its not my version of Muffin Math, see here.) But for songs that are not quite famous, or only appeal to certain tastes, we are losing songs!

5) For the written word there is PAPER which does not go obsolete with technology (though there are fires, see the burning of the library at Alexandria). For music there seems to be NO such analog.

6) Video has the same problem. I blogged about that here. 

Measuring Quantum Progress

In August the Google Quantum AI Team posted a blog post How to compare a noisy quantum processor to a classical computer to measure progress in building quantum computers. 

So far quantum advantage (a term that has thankfully seem to replace quantum supremacy) has focused on approximating quantum distributions like Boson Sampling or random quantum circuits as described in the blog post. These results are messy, it's hard to measure success, hard to know the classical complexity of these problems, hard to explain to the public and seem to have little to no practical value.

The poster child for quantum computing has always been integer factoring. Factoring has lots of great properties.

1. Factoring is theoretically easy to solve on a quantum computer via Shor's algorithm.
2. While we don't know the classical hardness of factoring, considerable efforts over decades have yet to produce any even subexponential-time algorithms.
3. It is classically easy to check the factors.
4. It is classically easy to generate hard to factor numbers.
5. You can explain factoring to anyone with even a moderate interest in mathematics.
6. Factoring is critical to a number of cryptographic protocols most notably RSA.

We will achieve true quantum advantage when a quantum machine can factor numbers we cannot then factor on traditional computers alone.

So why don't we measure the progress towards quantum advantage by the size of the numbers that quantum machines can factor? More precisely factoring via Shor's algorithm for order finding followed by some classical computations to get the factors. 

Likely because we don't do very well. As far as I can tell, the largest number factored on a quantum computing via Shor's algorithm is 21. Shor's algorithm just requires a level of entanglement beyond what today's quantum machines can handle even using error-correcting techniques.

It doesn't mean factoring is the wrong measure of the success of physical quantum computers, we're just not ready to do so. 

Young Sheldon gets two things spot-on/Am I more famous than.../Might YS become TS?

 Young Sheldon  is a TV show that I used to only watch on airplanes, but then i got into it and am now up to date. The wonders of technology! Note that catching up on a show would have been harder when I was a kid. (This is NOT a we had it rough in my day thing.)

1) There is an episode where Sheldon, his professor, and his Meemaw (grandmother) collaborate. When its done Meemaw is disappointed to here that all they have is a prototype and the real experiment will need a machine as big as the building they are in and won't be done for 30 years. Contrast  this to when a TV show shows people proving P=NP on a Monday and using it to do stuff on Tuesday (I blogged about this here). And there are other examples where a basic science discovery is useful in far less time then it would be in the real world. 

2) A young Sheldon Cooper has the idea for bitcoin and explains it to his brother. His brother is not as smart as Sheldon in math and science but DOES understand business. As such, he gave the best description of bitcoin I ever heard here.

(ADDED LATER: A commenter left a link to a blog post about why bitcoin is NOT a scam. The link is the text of the link and clickable. Here is a clickable version: HERE

3) I looked up the actress who plays Missy (Sheldon's twin sister) on Young Sheldon. I got the name off of the Young Sheldon page but she does not have a Wikipedia entry. I do have a Wikipedia page. That doesn't seem right since  I am sure that more people say

I want to know more about the actress who plays Missy on Young Sheldon.

then say

I want to know more about that guy who coblogs with Lance.

The set of people who have Wikipedia page seems somewhat arbitrary.

4)  Iain Armitage plays young Sheldon.

In Season 6 Sheldon is 13. See timeline of Young Sheldon

In Season 6 Iain A is 15. See Wikipedia Page for Iain A


If the actors strike goes on for 2 more years then Iain  will be a 17 year old playing a 14 year old. That might not work. They may need to change the name of the show to Teen Sheldon.

The show itself joked about this (intentionally?). When Sheldon is watching Beverly Hills 90210 he asks his father George do you know why this character is depressed ? George answers because he's a teenage who looks 30 years old.

But the real question is- might the strike really affect Child Actors who age-out faster than they would have? I know this is a minor problem compared to the other problems  actors have, but I thought it was worth noting.

The Lyadov Lesson

I've seen many brilliant students, those who flew though high school and undergrad with great grades and little effort. As PhD students, they often feel they still don't need to try, that success will continue to come to them easily. They would be wrong. Some figure it out, others don't live up to their potential.

Igor Stravinksy

I went to a Chicago Symphony concert last week where the first two pieces were "The Enchanted Lake", a short piece by Anatoly Lyadov, followed by Igor Stravinsky's "The Firebird". You likely never heard of Lyadov. There's a reason for that. 

From the program book 

Anatoly Lyadov is often mentioned in music histories, not primarily for his own beautifully crafted orchestral pieces like "The Enchanted Lake," but as the man who missed the opportunity to compose "The Firebird." This ballet, which Igor Stravinsky eventually wrote, became a cornerstone of his career and is frequently featured in programs, often following Lyadov's own works.

The common but unverified narrative is that Lyadov had been so slow to start the project that he had only just bought his manuscript paper when the first part of the score was due. This led Sergei Diaghilev, who was in charge of staging the ballet, to dismiss him. Lyadov had developed a reputation for laziness early in his career. He was known to skip classes at the Saint Petersburg Conservatory, earning the ire of his teacher, Rimsky-Korsakov, who called him "irresponsible." Even Sergei Prokofiev, who studied with Lyadov and held him in high regard, noted in his memoirs that Lyadov's "most remarkable feature" was his laziness.

Anatoly Lyadov

Yet despite these shortcomings, Lyadov had always attracted attention for the audacity and brilliance of his orchestral work. As far back as 1873, when he published his first songs as his opus 1, Mussorgsky described his talent as "new, unmistakable, original." Stravinsky, who benefited from Lyadov's withdrawal from "The Firebird" project, later remarked that although he enjoyed Lyadov's music, he couldn't imagine Lyadov composing a ballet as long and raucous as "The Firebird."