Factoring Carmichael Numbers

Carmichael Numbers are the bane of probabilistic primality algorithms. You have to go through extra steps just to handle these relatively rare numbers. But did you know that the Miller-Rabin algorithm not only determines the compositeness of Carmichael numbers but can actually find non-trivial factors? Apparently none of the AI models I tried did either. Feel free, Google, OpenAI and Anthropic, to train on this blog post.

Let's start with Fermat's little theorem, not as big as his "last" one but one where we know he had a proof. It states that for any prime \(p\),  \(a^p \equiv a\bmod p\) for all integers a. That suggests a primality test, if you can find an \(a\) such that \(a^m \not\equiv a\bmod m\) then you know \(m\) is not a prime. For example, since \(29^{143}\equiv 35\bmod 143\) then \(143\) is not prime. 

The set of \(a\) such that \(a^m \equiv a\bmod m\) forms a subgroup of \(Z_m^*\) (the numbers \(b\) less than \(m\) with gcd\((b,m)=1)\), if there are any integers \(a\) that fail the test then at least half of  the \(a\) will. So you could just choose a random \(a\) and check if \(a^m \equiv a\bmod m\). That would work for all the composites where there is an \(a\) such that \(a^m \not\equiv a\bmod m\). Alas there is a relatively rare set of composites, known as Carmichael numbers, for which  \(a^m \equiv a\bmod m\) for all \(a\) co-prime to \(m\). The first few Carmichael numbers are \(561\), \(1105\), \(1729\) and \(2465\). For example \(29^{561}\equiv 29\bmod 561\).

So probabilistic primality tests need to account for these Carmichael numbers. Let's look at the Miller-Rabin test. 

• If \(m\) is even, output "prime" if \(m=2\), composite otherwise.
• Pick \(s\) and odd \(d\) such that \(m-1=2^sd\).
• Pick random \(a\) between 2 and \(m-2\). If gcd\((a,m) \neq 1\) return composite.
• Let \(x = a^d\bmod m\)
• Repeat s times
• Let \(y=x^2\bmod m\)
• If \(y=1\) and \(x\not\in\{1,m-1\}\) then composite.
• Let \(x=y\)
• If \(y=1\) output "probably prime" otherwise "composite"
  

Here's the kicker. If the Miller-Rabin test says "composite" before the last step, you'll get a factor. Note that \(y-1=x^2-1=(x-1)(x+1)\equiv 0\bmod m\). But since neither \(x-1\) or \(x+1\) is a multiple of \(m\), the greatest common divisor of \(x-1\) and \(m\), as well as the gcd of \(x+1\) and \(m\) will give you a non-trivial factor of \(m\).

For example if we start with \(m=561\) and \(a=29\), we have \(d=35\) and \(s=4\), \(29^{35}\bmod 561=164\) and the \(y\)'s will be \(592,463,67,1\). For \(x=67\), the gcd of \(x-1=66\) and \(561\) is \(33\) and the gcd of \(x+1=68\) and \(561\) is \(17\). \(561=33\times 17.\)

Finally Carmichael numbers will never say "composite" in the last step, so the Miller-Rabin algorithm will always find a factor when it says "composite".

In 2002, Agrawal, Kayal and Saxena gave the first provably polynomial-time algorithm for primality. As far as I know AKS doesn't factor Carmichael numbers and there isn't any known deterministic polynomial-time algorithm finding non-trivial factors of Carmichaels, though if the generalized Riemann hypothesis is true, you need only try the first \(O(\log^2 m)\) \(a\)'s in the Miller-Rabin test. 

Test of Time Awards: A Good Idea but ....

Since there is now a CCC Test-of-Time Award, see here,  (CCC stands for Computational Complexity Conference), I decided to look at other Test-of-Time awards in computer science.

Below is a list of various computer science Test-of-Time awards, along with their

eligibility requirements.

1) IEEE Visualization (VIS) Test of Time Award, see here.   VIS=Visualization.  Their 2023 award page says:

Papers are selected for each of the three historic conferences (VAST, InfoVis, and SciVis). ... 

This year VAST gave out a 10-year test of time award, InfoVis a 10- and 20-year award, and SciVis a 13, 14 and 25 year award.

2) SC Test of Time Award, see here. SC=Supercomputing Conference.  Their site says:

Papers appearing in the SC Program 10 to 25 years prior are eligible.

3) CIKM Test of Time Award, see here.   CIKM=Conf. on Information and Knowledge Management.  Their page states:

The Test of Time Award is given for CIKM papers published at least ten years ago.

3) ACM SIGCSE Test of Time Award, see here. SIGCSE = Special Interest Group on Computer Science Education.  ACM=Association for Computing Machinery. The name is from the era when computers looked like angry filing cabinets.  The ACM SIGCSE Test-of-Time page states:

The award recognizes an outstanding paper published in the SIGCSE community. 

 Note that this is broader than just their conference. Good!

4) LICS Test of Time Award, see here. LICS=Logic in Computer Science.  Their award page says:

The LICS Test-of-Time Award recognizes a small number of papers from the LICS proceedings from 20 years prior.

5) STOC Test of Time Award, see  here. STOC = Symposium on Theory of Computing.  Their page states:

There are three awards---papers presented at the STOC conferences in 10, 20, or 30 years ago [they later say there is some flexibility on that]. 

6) FOCS Test of Time Award, see  here. FOCS stands for Foundations of Computer Science.  Their page states:

The awards recognize papers published in the Proceedings of the Annual IEEE Symposium on FOCS. [From elsewhere on the page they have three categories: papers 10-years ago, 20-years-ago, and 30-years ago, but they have some flexibility with that.]

7) SIGecom Test of Time Award, see here. SIGecom = Special Interest Group---Economics and Computation.  Their page states:

...must have been first published in an archival journal or conference proceedings 10–25 years before. At least one author must not be dead. [A surprisingly nontrivial constraint in a Test-of-Time award.]

I think this is the only award on this page that stated the not-dead criteria explicitly.  Are people in Economics and Computation publishing papers into their 90's? While in hospice care?

8) NeurIPS Test of Time Award, see here.  NeurIPS = Neural Information Processing Systems.  I couldn’t find an eligibility description, so I asked ChatGPT, which confidently stated:

Yes—the paper must have been published in NeurIPS at least 10 years ago. 

If this is wrong, please let me know. ChatGPT is sometimes confident the way undergraduates are confident before seeing the homework solution.

9) CCC Test of Time Award, see here. CCC=Computational Complexity Conference. Their page states:

Eligible papers are those that appeared in CCC (or Structures, pre-1996) at least 10 years ago. 

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

These awards raise some questions:

1) Why tie eligibility to a conference?  Suppose Abisola proves P ≠ NP and publishes it in Annals of Mathematics.  Under many of these rules, she would be ineligible for most theory Test-of-Time awards.

CON: Important results may not appear in the “right” conference or any conference at all.

PRO: None. Absolutely none.  Why is it done?  To publicize the conference and provide a nice ceremony venue.  These are not strong intellectual reasons. (I had a nastier comment about this but ChatGPT convinced me to be more polite.)

My proofreader brought up the following:

a) Who will give out the award? Answer: An organization like the ACM, and it DOES NOT need to go to an ACM conference.

b) How to limit what papers are eligible? Any paper that was in a conference or journal (though see item 3 below). That seems like a rather large set of papers to consider; however, after 10 years we DO know which papers stood the test of time. As an example- when Lance made his best theorems of the decade lists he did not pay attention to which venue the result appeared in.

2) Why the 10–25 years ago window?  I understand waiting 10 years—time needs time.  But why exclude older papers?  What if the paper Some Connections Between Bounded Query Classes and Nonuniform Complexity (STRUCTURES/CCC 1990) suddenly becomes important? Too bad: it aged out, like a carton of milk.

Are there examples of papers that became important many years after they were published?

I have one sort-of example: Google AI Overview says

The permanent of a matrix was first introduced independently by Cauchy in 1812 and later independently rediscovered by Binet in 1812. [The identical years makes me suspect, and also makes the notion of ``later'' rather odd- Did Cauchy do it in February and Binet in June?]

The permanent became much more important after Valiant, in 1979, showed that it was Sharp-P-Complete. So perhaps Cauchy's paper should get a test-of-time award.

Fun Fact: The Wikipedia entry on The Permanent (see here) does not mention Valiant, though there is a separate Wikipedia entry on Computing the Permanent (see here) that does.

3) Why require publication in a journal or conference at all?  Suppose Perelman proves P ≠ NP, posts it on arXiv, and never submits it anywhere.  Perelman did just that with his proof of the Poincare Conjecture, and that was good enough for a Fields Medal.

This touches on the much broader---and increasingly relevant—question: What is the future role of journals and conferences in the age of arXiv?

4) (Bonus question): Is there any real difference between the STOC conference and the FOCS conference in terms of the scope of the papers?  Was there ever?  I would guess no and no. Maybe some of my older readers can tell me, unless they are too busy writing papers in Economics and Computation. 

5) Another proofreader pointed out that it would be a good idea to live up to the title of this post, Test of Time Awards: A Good Idea but, and say why they are a good idea instead of bitching and moaning about eligibility. Good Idea! Some thoughts:

a) They might encourage researchrs to aim for deep contributions, not just fashionable ones. I doubt this is true since I doubt authors think about which award they might win.

b)  They reward long-time impact over short-term excitement. Is it much of a reward? How do they benefit the recipient? I ask non-rhetorically. 

c) They are an objective record of subjective opinion.  Useful for historians!

 

The Future of Teaching Assistants

In 2016, in the pre-transformer times, Georgia Tech professor Ashok Goel gave a prescient TEDx Talk on an AI teaching assistant for his large online Artificial Intelligence course. Students would ask questions to an online forum, and fellow students and TAs would answer these question. Unbeknownst to the students, Ashok had an AI system answer questions from the forum with the moniker Jill Watson (it was built on technology used for Watson's Jeopardy win). Jill answered questions about administrative issues in the class, so well that most students were surprised it was an AI system. Goel still needed human TAs to handle questions about course content.

In the talk Goel made comments ahead of his time.

Today, we have classes with a hundred or more students, and few get personal attention. We even have massive open online courses, where students learn from prerecorded video lessons. Some of these classes attract 100,000 students, but only 10 percent or fewer complete them—because of the lack of teaching assistance and personal attention. 

This raises a fundamental issue: can we have personal attention at scale? What if we could give personal attention to every student, when and how they needed it? That would create an educational revolution—because learning and teaching would become personal again...I envision a future where everyone has access to AI teaching assistants like Jill Watson—anytime, anywhere, for any task. A future where education is affordable and accessible to all, yet still personal and fun. 

Fast forward to today and AI assistants can answer questions about course content pretty well for nearly every undergraduate course in all disciplines. A well-trained AI tutor outperformed in-class active learning. While I haven't seen formal studies, students seem to go to ChatGPT before reaching out to TAs, instructors or their fellow students. AI can grade assignments and exams. 

Teaching assistants still have an important role to play. They teach recitation sections and run student labs. A great TA can provide a human connection with a student that no computer could. A teaching assistantship gives important training to students who might become academics, as well as providing an important funding mechanism, especially in the humanities and social science which has limited grant support for graduate students. But in a time of budget constraints at many institutions, how can we argue for the same TA support at the levels we had back in 2016?

A Presidential Trivia Question, how I tried to solve it

       

A friend of mine told me that in the last six months, the last grandchild of one of our former presidents (who had already passed away) died.

I tried to  deduce who it was without checking the web directly. For example, I  looked up when various presidents were born to narrow it down, but try not to search for the answer itself.

I could look this up easily. However, by spending time thinking about it and exploring related questions, I might learn things I  didn’t know before.

Things I care about? Maybe.

I now have a lot of white space, so you can think about the answer yourself and perhaps make a guess, then my reasoning process and the answer.

Before answering, I’ll walk through the reasoning I used for my educated guess.
Assume the president was born in year x.

ADDED LATER: In the original version of this post (and its still there) I would make comments like: 

                           Warren G. Harding- why is the G always mentioned.

A commenter pointed out that middle names and initials are an American thing. This made me wonder why some of them didn't use their middle initial. Hence I have ADDED information about that. I won't bother writing ADDED LATER for those late adds. 

END OF ADDED LATER

Assume the president’s youngest child is born in approximately year x+35.

Assume that child’s youngest child is born in approximately year x+70.

Assume the grandchild lives 80 years, so dies in approximately year x+150.

Then x+150=2025, so x=1875.

Since this is an approximation, I looked at all presidents born between 1850 and 1900. The website I consulted tells us the answer. What would we do without the internet? (Maybe spend more time offline tightening our bounds on the polynomial van der Waerden numbers.)
Here are all the presidents who were born in a year in [1850,1900].

Theodore Roosevelt — born 1858. Formal name: Theodore Roosevelt Jr. No middle name. 

William Howard Taft — born 1857. He seems to have his full name mentioned. Why? 

Woodrow Wilson — born 1856. Formal name: Thomas Woodrow Wilson. So it would be impossible to use a middle initial unless you do what David Dwight Eisenhower did and swith the two names, so then he would be Woodrow T. Wilson. 

Warren G. Harding — born 1865

Calvin Coolidge — born 1872. Formal name: John Calvin Coolidge Jr. Similar to Woodrow Wilson.  Cal's dad was John Calvin Coolidge Sr.  Naming your kid after yourself, including the middle name, coud be a mistake, see here.

Herbert Hoover — born 1874. Formal name: Herbert Clark Hoover. I am surprised he wasn't called Herbert C. Hoover. Maybe Herbert Hoover was better because its alliterative. 

Franklin D. Roosevelt — born 1882

Harry S Truman — born 1884 (There really is no period after the S. Both chatty and Wikipedia get that wrong.)

Dwight D. Eisenhower — born 1890 (born David Dwight Eisenhower; he preferred to be called Dwight).

When I was asked the question, I guessed Harry S. Truman. I was wrong.

In fact, none of the presidents on that list is the one. 

The correct answer is John Tyler, who was born in 1790.

My rule-of-thumb assumptions (35 years to have a child; an 80-year lifespan) were  large underestimates for this case. John Tyler had sixteen children. The third-to-last was Lyon Tyler, born in 1853 — John Tyler was 63 at the time, which is 28 years more than my estimate of 35. Lyon Tyler had six children; the second-to-last was Harrison Tyler, born in 1928 — Lyon was 75, which is 40 years more than my estimate of 35.

(In 1840 William Henry Harrison and John Tyler were elected Prez and Veep. WHH died after giving his inaugural speech in the cold rain, and Tyler became president. Lyon Tyler names his son Harrison. My thought was: Did Lyon name his son after WHH? I asked Google 

Why did Lyon Tyler name his son Harrison? 

The AI Overview said:

Lyon Tyler named his son Harrison because his own mother, Julia Gardiner, was a member of the Harrison family of Virginia, making Harrison a great-grandson of both President John Tyler and William Henry Harrison, the president whom John Tyler succeeded. Naming his son Harrison was a way for Lyon Tyler to honor the family connection to both presidents, particularly the presidential connection. 

Thats not quite right- Harrison is John Tyler's grandson, not great-grandson. 

I didn't know that John Tyler's grandchild was named Harrison.

I didn't know that John Tyler's grandchild was also related to WHH.

)


Harrison Tyler died in 2025 at the age of 96, which is 16 years more than my estimate of 80.

So my point (do my posts need a point?) is that I made an approximation but was still way off. John Tyler is an outlier, which is hard to account for.

Let’s say I assumed 60-year-old fathers and the grandson lives to 90. Then we would have:

x + 210 = 2025
x = 1815

This is an approximation, so I would look at presidents born between 1790 and 1840:

John Tyler: 1790. No middle name. 

James K. Polk: 1790. Why is the K always mentioned?

Zachary Taylor: 1784. No middle name. 

Millard Fillmore: 1800. No middle name. 

James Buchanan: 179. He never had kids. That’s just as well, since his children would have had the stigma of their father being one of the worst presidents of all time by most accounts.

Abraham Lincoln: 1809. Born February 12, 1809 — the same day and year Charles Darwin was born. No middle name. 

Andrew Johnson: 1808. No middle name. 

Ulysses S. Grant: 1822.  Born Hiram Ulysses Grant, but he didn’t like that the initials were H.U.G.

Rutherford B. Hayes: 1822. Why is the B always mentioned?

James Garfield: 1831. James Abram Garfield. I sometimes see the A initial and sometimes not. 

Chester Arthur: 1829. My Darling’s favorite president — really! Formal name Chester Arthur which I have seen written, though not as much as the others. Perhaps I just didn't notice him as much as my Darling did. 

Grover Cleveland: 1837. Formal name: Stephen Grover Clevelant. 

Three points:

1) When I picked 60–60–90, I did not know that John Tyler would actually make it onto the list.

2) He just barely made the list.

3) I would not have picked 60–60–90 unless I had already learned that 35–35–80 was far too small.

The Complexity Argument for Capitalism

We're seeing an attack on capitalism on both ends of the political spectrum with with the election of Democratic Socialist Zhoran Mamdani as mayor of New York, and Donald Trump trying to direct the economy through tariffs, less independency of the Federal Bank and partial government control of companies such as a nearly 10% ownership of Intel and the "golden share" of U.S. Steel.

Now I'm not an economist and there are many arguments for and against socialism and capitalism, especially in their purest forms. I want to focus on the complexity of the economy. Let's start by considering rent control.

It starts with the worthy goal of preventing people from having to leave their apartments because of rising rents due to market demand. So you limit the rent increases and the ability to evict current residents. But this could cause landlords to cut back on improvements, not prioritize service and repairs, or build new properties to increase the supply. So you have to give landlords incentives to do these things, leading to other issues which leads down a rabbit hole. I saw extreme rent control in Berkeley in the 1980s and a lack of available housing forced me to live 13 miles away. 

That's just rent control in a single city. Other attempts to control the economy will lead to unexpected inefficiencies and you can't predict markets enough to catch them.

The 1920 essay Economic Calculation in the Socialist Commonwealth by Ludwig von Mises argued that market prices give critical information for companies and individuals to make decisions. I think of it like a circuit, where the prices are values of intermediate gates so that we can have simple operations at every level leading to a very complex behavior in the aggregate, much like a neural net today. Frederick Hayek went further in his 1945 essay The Use of Knowledge in Society that a center planner couldn't adapt with the speed of change in the markets. 

Could today's neural nets replace the need for these intermediate pricing and adapt quickly? It's really a combination of the two, many companies are using sophisticated machine learning models that lead to more accurate pricing, adding to the efficiency of markets. 

Capitalism has its challenges: Companies can shrink or close, people can lose their jobs and we need good safety nets. Government has a role to protect safety, enforce contracts and provide services and some control where competition doesn't scale, like utilities and pubic transportation. Government also has a role in promoting public goods including education, scientific research and national defense. 

While neither Mamdani or Trump want anything close to complete government control of the economy, I still worry that even their limited influences will hurt innovation and in the longer run hurt the very people these policies are meant to help. 

Did Euclid exist? Is it okay to quote people that did not exist?

 
The following excerpt from Abrahim Ladha's comment on Lance's post about
AI and intro theory caught my attention:


---------------------------
BEGIN EXCERPT

Not just with AI, but in theory and math courses, there have always been Bart Simpson
level questions by students of the form

"Why do I need to know this?

like

Why do I need to know my times tables when the calculator does this for me?

There has never been a good answer because these students already do not have an open mind.
Euclid was asked such a question once and said something like

give him a penny so he may feel like he earned something for what he learned.

END EXCERPT
-----------------------------------

He gives a quote by Euclid.

1) I have heard that Euclid might not have really existed.

2) I have never heard that quote.

I asked Abrahim Ladha if he had a source for the Euclid quote.

I never go a response.

I asked chatty:

        What is the historical evidence that Euclid existed?

and also

        Did Euclid say give him a penny so he may feel like he earned something for what he learned?

The answer to both questions are below. The bottom line is that

1) Euclid might not have existed.

2) The idea underlying the quote is attributed to him. The exact quote is modern rendering. 

Should Abrahim have consulted chatty before making his comment.

1) YES, it's important to make sure your facts are correct.

2) NO, his point is still valid. (That is a slippery slope.)

----------------------------------------
BILL: What is the historical evidence that Euclid existed?

That’s a great question — and a surprisingly tricky one.

Short answer

There is no direct historical evidence that Euclid (often called Euclid of Alexandria) existed
as an individual in the way we can verify the existence of, say, Archimedes. What we “know”
about Euclid comes almost entirely from later sources, not from contemporary records.

The evidence we do have

1)
Type: Ancient testimonies

Source: Proclus, Commentary on the First Book of Euclid’s Elements

Date: ca. 450 CE

Note: Written about 700 years after Euclid’s supposed lifetime. Proclus says Euclid lived
in the time of Ptolemy I (reigned 323–283 BCE) and taught in Alexandria. This is our main source.

2)
Type: Mentions by other ancient authors

Source: Pappus of Alexandria (4th century CE), Diogenes Laërtius (possibly), and others

Date: 200–600 years later

Note: These references repeat information similar to Proclus’s account — that Euclid compiled
the Elements and worked in Alexandria.

3)
Type: Mathematical evidence

Source: The Elements and other works attributed to Euclid (Data, Optics, Phaenomena, etc.)

Date: ca. 300 BCE?

Note: These texts show a unified style and method, suggesting a single organizing mind
(or school). But there is no personal or biographical detail inside them.

4)
Type: Absence of contemporary evidence

Note: There are no letters, inscriptions, or administrative records naming Euclid. No ancient
biography (unlike Archimedes or Apollonius).

Scholarly interpretation

Traditional view: There was a historical Euclid, a mathematician who worked in Alexandria
around 300 BCE and compiled earlier Greek geometry into the Elements.

Skeptical or revisionist view: “Euclid” may have been a collective name for a team or a
school of mathematicians in early Hellenistic Alexandria, much like “Hippocrates” in medicine.

The Elements itself is consistent in style, so even if multiple people contributed, it was
edited or systematized by someone with extraordinary coherence and rigor.

In summary

There is no direct documentary or archaeological proof that Euclid existed as an individual,
only later testimony and internal evidence from the mathematical works. Historically, most
scholars accept that there was a person — or at least a leading mathematician — behind the
name “Euclid,” but his life remains almost entirely unknown.
---------------------

BILL: Did Euclid say

`give him a penny so he may feel like he earned something for what he learned.'

ChatGPT said:

The quote you’re referring to — something like “Give him a penny so he may feel he has learned
something” — is attributed to Euclid, but not in those exact modern words.

It comes from an ancient anecdote recorded by Proclus (a 5th-century commentator on Euclid) in
his Commentary on Euclid’s Elements. The story goes like this:

A student, after learning the first theorem of geometry, asked Euclid,

“What shall I get by learning these things?”

Euclid called his slave and said,

“Give him a penny, since he must make gain out of what he learns.”

In Greek, it’s roughly:

“Δός αὐτῷ ὀβολόν, ἐπειδὴ κερδαίνειν δεῖται ἀπὸ τῶν μαθημάτων.”

So your paraphrase captures the spirit of the anecdote — Euclid was mocking the idea of
studying geometry for material reward — but the exact wording

“give him a penny so he may feel he earned something for what he learned”

is a modern retelling, not a direct quotation.

AI and the Power of Nonuniform Circuits

The advances in artificial intelligence have changed the way we think about computing. For today's post, how nonuniformity plays a much larger role than I previously believed.

First, some background. Circuit complexity gives a different, more combinatorial, way to look at computation. Instead of viewing algorithms as step-by-step programs, circuit complexity captures computation as fixed hardware, gates wired to compute a function of their inputs.

Every polynomial-time computable language L can be computed by a family \(C_0,C_1,\ldots\) of polynomial-size circuits, where \(C_n\) has n inputs, the number of gates of \(C_n\) is bounded by \(n^c\) for some \(c\) and \(x=x_1\ldots x_n\) is in L iff \(C_n(x_1,\ldots,x_n)\) outputs 1.

The converse isn't true, there are languages L that have polynomial-size circuits that you can't compute in polynomial time, because each \(C_n\) might not have any relation to \(C_m\) for \(n\neq m\). We can get the equivalence by adding a uniformity condition, that there is some easily computable function \(f\) with \(f(1^n)=C_n\). Or we can keep the nonuniformity to define a larger class called P/poly. 

In practice, nonuniformity rarely helps. We can hide randomness in the nonuniformity but we could likely also use pseudorandom generators to the same effect. Nonuniformity was more a technicality that we had to deal with instead of something that seemed to give circuits significantly more power.

Until we reached this new age of AI. A machine learning model like a neural net goes through a lengthy training process to learn its weights, the training optimized offline. The learned weights become the nonuniform circuits, as technology improves and we create larger retrained circuits, the weights change as well.

We typically use the complexity class TC\(^0\), languages accepted by poly-size, constant-depth with threshold circuits as a rough theoretical model for neural nets. For nonuniform TC\(^0\) we cannot prove any significant upper bounds, we can't even show NEXP, nondeterministic exponential time, cannot be computed by nonuniform TC\(^0\) circuits. And while computing NEXP or even P in TC\(^0\) would be incredibly surprising, these advances in artificial intelligence tell us these nonuniform circuits are far more powerful than we would ever have expected. 

Bill's Bad Advice

 I sometimes give the following advice for research which I label Bill's Bad Advice. We will later see who it might be good advice for. Spoiler alert: the number of people for whom it is good advice is shrinking but might include Lance especially now (see his post about stepping down from admin, here).

When you come across a possible research topic or problem, or have some idea,  and are wondering if you want to pursue it,  here is my bad advice: 

1) DON"T  CARE if anyone else cares. If YOU care then that is enough to at least get started. 

2) DON"T  CARE if it has the potential for a published paper. FIRST do the work then, if you feel like it, look for a good venue. You might not bother if posting to arxiv or making an open problems column out of it or a (guest) blog post out of it is  a good endpoint.  (I run the SIGACT News Open Problems Column- feel free to contact me if you want to submit one.) 

3) DON"T CARE if it has practical implications. 

4) DON"T  CARE if you can get a grant for it. With the current state of the NSF this advice may soon become irrelevant. 

5) DON"T  CARE if someone else already did it (though at a later stage you should check on this). Even if you work on it and find someone else did it, you will have LEARNED about the problem through your efforts. You might then want to do a survey for your own benefit to consolidate your  knowledge. 

Why should you NOT CARE about any of these things? Because they get in the way of actually DOING something.  

Here are two examples of when this approach WORKED and one where it DID NOT WORK, though both classifications might depend on your definition of WORKED. 

WORKED: My work on Muffins. All I wanted was to get some High School and Undergraduate Projects out of it. I ended up with a book on it which made me twenty dollars last year! More to the point, I learned a lot, as did my co-authors and I am happy with the book. The co-authors were Undergraduates so my dept put me up for a mentoring award (I have other credentials as well). I did not win, but I got a nice letter saying they had many qualified applicants. OH- it didn't say if I was one of them. 

WORKED: I have had many Ramsey Projects where a High School Student codes stuff up and learns some Ramsey, some coding, and gets the experience of research. Sometimes they do a survey paper or open problems column. We both learn A LOT from this and the student gets a good letter from me. Do they do something NEW? Publishable? No, though some surveys and open problems columns have come out of this.  I DO tell them ahead of time that the work is unlikely to lead to original results (and hence unlikely to be good for a science competition).   

DID NOT WORK: See this blog post here about the math and here about finding out that the problem we were working on was already known and more was known than we thought. I didn't mind this, but one of the authors did. 

Note that WORKED and DID NOT WORK also depend on your goals. 

For whom is this bad advice? Good advice? 

1) It was always bad advice for young assistant professors who need to get papers and grants to get tenure. 

2) Hypothetically, once you get tenure you have job security and hence can change fields or follow my bad advice without consequences. But with grants and salary and teaching load issues, this is less the case. Perhaps I am nostalgic for a time that never was.

3) High School Students were my main audience for bad advice. It's not as important for them to get papers out as for (say) assistant professors. But even this is changing. Colleges are getting more competitive. And HS students may well want a project that can lead to Science competitions. I am not going to say things were better when I was a kid but instead pose non-rhetorical questions:

a) Are high school students getting into research earlier than they used to? I am sure the answer is yes.

b) Are we losing the safe space where a high school student can just learn things and do things and not worry so much about if it's publishable?  Yes, but I am not sure how widespread that is.

c) If we are losing that safe space, is that a bad thing? 

d) Points a,b,c apply to ugraduates who want to go to graduate school more than for high school students who want to go to college. 

4) Full Professors may have more freedom to follow my bad advice. Lance is looking for things to do now that he is no longer a dean, and indeed, is back to being a teaching-and-research professor. So he might follow my advice. However, he actually cares if people care about his work. He does not have to follow all of my advice, but he can follow some of it.