Skip to content

Puzzle Reviews by a Puzzle Writer

September 22, 2020

Not puzzling reviews

Princeton University Press page

Jason Rosenhouse is professor in the Department of Mathematics at James Madison University. His research focuses on algebraic graph theory and analytic number theory involving exponential sums. The former includes a neat paper on expansion properties of a family of graphs associated to block designs, with two undergraduates among its authors. But besides his “real” research, he has written a number of books on puzzles such as The Monty Hall Problem: The Remarkable Story of Math’s Most Contentious Brain Teaser. Soon his book Games for Your Mind: The History and Future of Logic Puzzles is to be published.

Today Ken and I thought we would highlight his recent review of a book on math puzzles.
Read more…

Ken Regan Turned 61

September 15, 2020

Happy birthday to Ken

Ken Regan is of course my partner on GLL. He is faculty in the computer science department at the University of Buffalo. His PhD was in 1986 from Oxford University and it was titled On the separation of complexity classes. He was the PhD student of Dominic Welsh who was a student of John Hammersley.

Today I would like to wish Ken a happy birthday.

Read more…

Convex Algorithms

September 13, 2020

Continuous can beat discrete

Nisheeth Vishnoi is a professor at Yale University in the computer science department. The faculty there is impressive and includes many of the top researchers in the world. The CS faculty is pretty good too. As Nisheeth’s PhD advisor, years ago, I am proud that he is at Yale.

Today I wish to discuss a new book by Nisheeth.

The title is Algorithms for Convex Optimization. Let me jump ahead and say that I like the book and especially this insight:

One way to solve discrete problems is to apply continuous methods.

This is not a new insight, but is an important one. Continuous math is older than discrete and often is more powerful. Some examples of this are:

{\bullet} Analytic number theory is based on the behavior of continuous functions. Some of the deepest theorems on prime numbers use such methods. Think of the Riemann zeta function

\displaystyle  \zeta(s) = \sum_{n=1}^\infty \frac{1}{n^s} = \frac{1}{1^s} + \frac{1}{2^s} + \frac{1}{3^s} + \cdots

as a function of complex numbers {s}.

{\bullet} Additive number theory is based on the behavior of continuous functions. Think of generating functions and Fourier methods.

The power of continuous methods is one that I sometimes forget. Nisheeth’s book is a testament to the power of this idea.


Nisheeth’s book uses another fundamental idea from complexity theory. This is: restrict problems in some way. Allowing too large a class usually makes complexity high. For example, trees are easier in general than planar graphs, and sparse graphs are easier than general graphs. Of course “in general” must be controlled, but restricting the problem types does often reduce complexity.

Convexity adds to this tradition since convex generalizes the notion of linear. And convex problems of all kinds are abundant in practice, abundant in theory, and are important.

The MW dictionary says convex means:

: being a continuous function or part of a continuous function with the property that a line joining any two points on its graph lies on or above the graph.

Here is a passage by Roman Dwilewicz on the history of the convexity concept:

It was known to the ancient Greeks that there are only five regular convex polyhedra.

It seems that the first more rigorous definition of convexity was given by Archimedes of Syracuse, (ca 287 – ca 212 B.C.) in his treatise: On the sphere and cylinder.

These definitions and postulates of Archimedes were dormant for about two thousand years!

I say it’s lucky that Archimedes was not up for tenure.

Nisheeth’s Book

Nisheeth’s book is now available at this site. I have just started to examine it and must say I like the book. Okay, I am not an expert on convex algorithms, nor am I an expert on this type of geometric theory. But I definitely like his viewpoint. Let me explain in a moment.

First I cannot resist adding some statistics about his book created here:

No way I can read the book in nine hours. But I like seeing how many characters and so on the book has. I will have to calculate the same for other books.

Discrete vs Continuous Methods

Nisheeth in his introduction explains how continuous methods help in many combinatorial problems, like finding flows on graphs. He uses the {s}{t} flow problem as his example. The {s}{t}-maximum flow problem arises in real-world scheduling problems, but is also a fundamental combinatorial problem that can be used to find a maximum matching in a bipartite graph, for example.

Combinatorial algorithms for the maximum flow problem. He points out that by building on the Ford-Fulkerson method, various polynomial-time results were proved and other bounds were improved. But he states that the improvements stopped in 1998. Discrete methods seem to be unable to improve complexity for flow problems.

Convex programming-based algorithms. He adds:

Starting with the paper by Paul Christiano, Jonathan Kelner, Aleksander Mądry, Daniel Spielman, Shang-Hua Teng
the last decade has seen striking progress on the {s}{t} maximum flow problem. One of the keys to this success has been to abandon combinatorial approaches and view the {s}{t} maximum flow problem through the lens of continuous optimization.

Thus, at this point it may seem like we are heading in the wrong direction. We started off with a combinatorial problem that is a special type of a linear programming problem, and here we are with a nonlinear optimization formulation for it. Thus the questions arise: which formulation should we chose? and, why should this convex optimization approach lead us to faster algorithms?


Open Problems

Take a look at Nisheeth’s site for the answers.

I wish I were better informed about continuous methods in general. They are powerful and pretty. Maybe I could solve an open problem that I have thought about if I knew this material better. Hmmm. Maybe it will help you solve some open problem of your own. Take a look at his book.


Hybrid Versus Remote Teaching

September 10, 2020

Which is best for students?

Cropped from Wikipedia src

Moshe Vardi holds multiple professorships at Rice University. He is also the Senior Editor of Communications of the ACM. His is therefore a voice to be reckoned with in the current debate over how best to teach during the pandemic. Much of the debate is over whether all should hear his voice the same way, or some hear it in the classroom while others hear it remotely.

Today we note his recent column for Medium advocating the former. Then I (Ken) give some of my own impressions.

His September 5 column followed an August 8 opinion given to the Rice student newspaper. Both begin with concern over the conflict between safety and value for students. Much of the value of college—most according to statistics he cites—comes from being collegial: outside the classroom. But many such activities, not only evening parties but informal games and gatherings, are the most unsafe.

We will focus however on what Moshe says about the nature of instruction for lecture courses. Certainly for laboratory courses there is a sharp trade-off between safety and in-person interaction. But we focus here on what he says about the nature of teaching in the lecture hall, where one can take safety as a given requirement.

An In-Person Remoteness Paradox

I have just returned from sabbatical at the University at Buffalo (UB) and am teaching this fall a small elective 4xx/5xx theory course. It has 15 students, smaller than the 25 in the hypothetical class Moshe describes but of the same order of magnitude. In the spring I will be teaching a larger undergraduate course which is also on target for his concerns. I have taught such a class every spring for a decade. While this assignment is not a new to me, the issue of safety raises tough choices about the delivery options. My options are:

  1. remote-only;

  2. in-person only;

  3. hybrid use of 1 and 2 for designated course components;

  4. hybrid-flexible, meaning 1 and 2 are conducted simultaneously with students free to choose either option, even on a per-lecture basis.

I have committed to hybrid-flexible. For my current fall course, I made this commitment in early summer when there was uncertainty over in-person instruction requirements for student visas and registration. I believe that my larger course will be implemented as safely in a large room as my current course. The question is quality.

Moshe notes right away a paradox for his hypothetical class that could apply to any of modes 2–4; to include the last expressly, I’ve inserted the word “even”:

…I realized that [even] the students in the classroom will have to be communicating with me on Zoom, to be heard and recorded. All this, while both the students and I are wearing face masks. It dawned on me then that I will be conducting remote teaching in the classroom.

Business Insider source—yet another variation

In fact, I have one volunteer now in the room logging into Zoom to help with interaction from those attending remotely. This helps because my podium has less space to catch faces and detect questions right away. I do repeat questions so they are picked up in the recording and often redirect them to the class. Still, the mere fact of my not seeing faces alongside the notes and interactive drawings I am sharing makes me feel Moshe’s paradox all the time. This is even though my room allows denser spacing than at Rice, so a class of 25 could sit closer. Let me, however, say why I love stand-up teaching before addressing his paramount question of what is best for the students at this time.

From Whiteboards to Tutorials

Dick once wrote a post, “In Praise of Chalk Talks.” First, with reference to talks pre-made using PowerPoint or LaTeX slides, Dick wrote:

Such talks can be informative and easy to follow, yet sometimes PowerPoint is not well suited to giving a proof. The slides do not hold enough state for us to easily follow the argument.

Moreover, when I contributed to the open-problems session of the workshop at IAS in Princeton, NJ that we covered two years ago, Avi Wigderson insisted that everyone use chalk, not slides. I’ve used slides for UB’s data-structures and programming languages courses, but I think students benefit from seeing proofs and problem-solving ideas grow.

I find furthermore that the feel of immersion in a process of discovery is enhanced by an in-person presence. I had this in mind when I followed Dick’s post with a long one imagining Kurt Gödel expounding the distinctive points of his set theory (joint with Paul Bernays and John von Neumann), all on one chalkboard. My classes are not as interactive as in that post, but I prepare junctures in lectures for posing questions and doing a little bit of Socratic method. And I try to lead this with body language as well as voice inflection, whether at a whiteboard or drawing on hard paper via a document camera.

Still, it exactly this “extra” that gets diminished for those who are remote. When I share my screen for notes or a drawing (both in MathCha), they see my movements only in a small second window if at all. They do hear my voice—but I do not hear theirs even if they unmute themselves. Nor can I read their state of following as I do in the room. Without reiterating the safety factor as Moshe does, I can reformulate his key question as:

Does the non-uniformity and inequality of hybrid delivery outweigh the benefits of making in-person instruction available to some?

I must quickly add that in-person teaching is perceived as a collective need at UB. The web form I filled for Spring 2021 stated that some in-person classes must be available at all levels, 1xx through 7xx. I am happy to oblige. But the fact that I chose a flexible structure, especially in a small class, does allow the students to give opinion on this question, as well as on something Moshe says next:

“Remote teaching” actually can do a better job of reproducing the intimacy that we take for granted in small classes.

Toward this end, I am implementing a remote version of the tutorial system I was part of for two eight-week terms at Oxford while a junior fellow of Merton College. When Cambridge University declared already last May that there would be no in-person lectures all the way through summer 2021, this is because most lectures there are formally optional anyway. The heart of required teaching is via weekly tutorial hours in groups of one-to-three students. They are organized separately by each of thirty-plus constituent colleges rather than by department-centered staff, so the numbers are divided to be manageable. In my math-course tutorials the expectation was for each student to present a solved problem and participate in discussions that build on the methods.

I am doing this every other week this fall, alternating with weeks of problem-set review that will be strictly optional and classed as enhanced office hours. All UB office hours must be remote anyway. The tutorial requirement was agreed by student voice-vote in a tradeoff with lowering the material in timed exams to compensate for differences in home situations. After a few weeks of this, the class will take stock for opinions on which delivery options work best. UB has already committed to being remote-only after Thanksgiving, and it is possible that the on-campus medical situation will trigger an earlier conversion anyway.

Open Problems

We would like to throw the floor open for comment on Moshe’s matters that we’ve highlighted and on his other opinions about the university mission amid the current crisis more generally.

[edited to reflect that at Rice too, the hypothetical class could be in any of modes 2–4, and that spacing is further than in my UB room. “Princeton IAS” -> “IAS in Princeton, NJ”]

Closing An Open Problem

September 5, 2020

Crawl, then walk, then run.

Bogdan Grechuk is a lecturer in the math department at the University of Leicester. His office is in the Michael Atiyah Building. Pretty cool. He works in risk analysis, but is more broadly interested in math of all kinds. See his wonderful book Theorems of the 21st Century. Or go to his web site.

Today Ken and I want to talk about solving open problems.
Read more…

Mea Culpa

August 31, 2020

Plus more on the separating word problem

Mea Culpa is not someone we introduced on the blog before. She does not come from the same world as Lofa Polir or Neil L. As in the French movie poster at right, the meaning is “my fault.”

Today we apologize for some oversights and hasty omissions regarding the last post. Then we will explain Dick’s “laws with errors”.
Read more…

20,000 Comments and More

August 29, 2020

With more about the Separating Words Problem

I.I.T. Madras page

Anoop S K M is a PhD student in the theory group of I.I.T. Madras in Chennai, India. His comment two weeks ago Monday was the 20,000th reader comment (including trackbacks) on this blog.

Today we thank Anoop and all our readers and say more about the subject of his comment.
Read more…

Logical Complexity of Proofs

August 19, 2020

If you cannot find proofs, talk about them.

Robert Reckhow with his advsior Stephen Cook famously started the formal study of the complexity of proofs with their 1979 paper. They were interested in the length of the shortest proofs of propositional statements. Georg Kreisel and others may have looked at proof length earlier, but one of the key insights of Reckhow and Cook is that low level propositional logic is important.

Today I thought we might look at the complexity of proofs.
Read more…

Thanks to An Explainer

August 13, 2020

Conrad explains all

Keith Conrad is a professor in the mathematics department at UCONN—the University of Connecticut. My dear wife Kathryn Farley and I are about to move to join him—not as faculty but as another resident of the “Constitution State.”

Today we thank him for his work on explaining mathematics.
Read more…

Fran Allen: 1932-2020

August 8, 2020

We lost a great computer scientist.

Frances Allen was one of the leaders who helped create the field of compilers research. Fran was an elite researcher at IBM, and won a Turing Award for this pioneering work. Allen also collected other awards.

Perhaps the coolest award is one that Fran could never win: The Frances E. Allen award created this year by the IEEE:

For innovative work in computing leading to lasting impact on other fields of engineering, technology, or science.

Today we will talk about Fran, who sadly just passed away.
Read more…