Impact of W's on grad school admissions in CS theory (TCS) I'm an undergrad at the University of Maryland College Park who just finished a computer science bachelors a few days ago. Unfortunately, I didn't realize how much I liked theory (algorithms, combinatorics, graph theory) and math until this past semester. As a result, I plan to work for a few years while self-studying upper-division math and getting the necessary TCS research experience (I plan to reach out to professors at the local university once I'm ready).

My question is whether or not my undergrad academic performance is salvageable from the perspective of grad school admissions. Although I ended up with a 3.895 cumulative GPA with relatively good grades in TCS-related classes (e.g. A- in discrete math, A in algorithms, A in number theory, A in cryptography, B+ in advanced data structures), I have 4 W's (withdrawn designations) on my transcript across different semesters. Moreover, these W's are all in math classes (euclidean &amp; non-euclidean geometry, numerical analysis, combinatorics &amp; graph theory, machine learning). However, with the exception of the geometry class, I dropped all of them since I didn't meet the official prerequisites. I had originally requested prerequisite overrides to register for the courses, but left due to not being able to catch up.

Also, due to COVID-19 I opted for the pass/fail grading system this past semester. Therefore, even though I took theory of computation and combinatorics &amp; graph theory and scored an A, A- respectively, these classes show up as P's on my transcript. Thus, I'm wondering (a) if a master's will help my case and (b) if one is necessary. If at all possible, I'd prefer to apply directly to PhD programs after getting some research experience.

Additionally, would having a publication by the time of application change any of those answers? I know theory programs in machine learning and computer vision basically require publications these days in order to be considered, but I'm not sure if the same holds for subfields like combinatorial optimization and graph algorithms.
First, I strongly suggest that you talk directly with the theory profs in your own CS department.  First, they are the people who actually taught you and are best placed to understand the circumstances of your withdrawals.  Second, they are the people who make graduate admissions decisions for your department, in your target subfield.  (Third, they are the people most likely to provide you with recommendation letters, so making contacting with them early can only help you.)

Opinions on W's differ, but as far as I can tell, most people treat them as no-ops.  Students drop classes for all sorts of reasons.  Some faculty might wonder why you waited until after the drop deadline to withdraw from these classes, especially if the W's were spread over several semesters, but that would be a minor concern, especially if you retook the same classes later and did well.  But it really doesn't matter; the W's are already on your transcript.  You can't do anything about it, so you shouldn't worry about it.

COVID-19 hit everyone, everywhere.  Every graduate admissions committee still has to figure out how to make admissions decisions with a full semester of grades missing, or at least obscured by a myriad of different pass/fail and Credit/No-Credit options.  Different people and places are going to interpret this semester's (and the next several semesters') records differently, some with more sympathy and others with more strictness.  You can't do anything about it, so you shouldn't worry about it.

A master's degree is a somewhat risky option.  At least in the US, PhD applicants who have graduate experience are held to a higher standard than applicants who do not.  Students applying from masters programs are compared with each other, not with undergraduates, and considerably more of those masters-level applicants will have research publications.  To first approximation, publications are a de-facto requirement for masters-level PhD applicants.

Persistent rumors notwithstanding, publications are not a de-facto requirement for undergraduate PhD applicants, even in hot fields like machine learning, even in top departments.  Research experience is necessary to get into a top PhD program; research papers are not.  Yes, a significant fraction of new PhD students in ML have publications, but an equally significant fraction do not.  

All that said, a strong research publication is definitely a advantage in PhD applications, especially if the recommendation letters make it clear both that the work is good and how the student made it happen, and the topic of the paper meshes well with the research interests of the faculty where you're applying.  Good research results can overcome all sorts of other weaknesses in your application.

On the gripping hand, nothing in your question suggests that you have any weaknesses in your PhD application.  Your GPA is high enough to draw the attention of human reviewers.  At that point, your research statement and recommendation letters matter far more than anything else.