\documentclass[11pt]{cseletter}
%\usepackage{times}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}

\setlength{\textheight}{8.5in}
\setlength{\topmargin}{-0.5in}
\setlength{\headheight}{0pt}
\setlength{\footskip}{0.5in}
% \setlength{\parindent}{0.3in}   %.5in
% \setlength{\parskip}{0in}       %.1 in or .2 in or 0in
% \setlength{\partopsep}{2ex}
% \setlength{\topsep}{1ex}
% \setlength{\itemsep}{0ex} %.5ex


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\hfuzz=3pt
\vfuzz=3pt

\begin{document}
\pagestyle{empty}
\thispagestyle{fancy}  %% fancy

\date{\today}

% \address{Department of CSE\\
% University at Buffalo\\
% 226 Bell Hall\\
% Buffalo,  NY  14260--2000}

\signature{Dr. Kenneth W.\ Regan}

\begin{letter}{Lecturer Recruiting Committee\\
Department of Computer Science\\
Princeton University\\
%42 Business Center Drive, Suite 206\\
%Miramar Beach, FL 32550\\
~~~\\
Re: applicant Michael Wehar
}


\opening{
\leftline{DearLecturer Recruiting Committee:}
}

\email{regan@buffalo.edu}

\url{www.cse.buffalo.edu/{\tiny$\sim$}regan/}

\room{326}
\phone{(716) 645-4738}


\signature{Kenneth W. Regan}

I am delighted to write a reference for Dr.\ Michael Wehar.
I first met him in May 2013 when he visited me prior to beginning
graduate study with a TA fellowship plus a supplemental Dean's Scholarship at Buffalo.
I had earlier talked with him by phone and also with Professor Rick Statman at CMU
who originally conveyed his desire to apply.  I am an Associate Professor
with many happy years at UB.  Besides my main academic work in computational
complexity theory and my second research project on human decision making
at chess, I co-manage the prominent mathematical computing
weblog \emph{G\"odel's Lost Letter and P=NP} which was originated by
Professor Richard J.\ Lipton (Dick Lipton) of Georgia Tech nine years ago.  One of our
posts in late 2012 featured Michael, and that combined with some
personal factors led him to apply to both Tech and UB while he was still
younger than most junior-year students though already taking Masters
courses and doing intern-level research at CMU.  

Michael completed his PhD dissertation in 3-1/2 years, which is basically
record time.  It was anchored by two papers at the highly competitive 
ICALP conferences in Europe in 2014 and 2015.  The former was singly authored
and won the best student paper award for the `B' track of the conference.
I'll say more about the subject matter below but let me emphasize first
that he is an incredible self-starter.  Usually job letters and committees reading
them spend time trying to ascertain how capable the recent graduate is of 
doing work ``past the advisor'' and which parts of joint papers really were
the student's initiative (if the application and letters don't spell it out fully).
Well here you have no such difficulty---I regret not having time to be more than a
sounding board while Lipton and I co-wrote a textbook on quantum computing for
MIT Press and numerous cheating cases---the highest in bridge not chess and
argued before CAS Lausanne---required
extra development of my own infrastructure which took precedence.
I was the same way with my own advisor at Oxford.  

Michael also has a dynamic array of interests.  He really wanted to take
at least a year working for a startup rather than go straight into academia.
He interned at IBM all the summer before finishing his dissertation.
His personal website http://michaelwehar.com/ has a variety of projects,
several of which have received outside recognition---I can mention
\emph{Treegle}, his accepted PyCon 2018 poster with Itay Livni,
and the Pittsburgh time-lapse painting film.  
I am very glad that he is going back into academia.
I will describe his research from my own perspective, even though this is for
primarily a teaching position.

\newpage
\pagestyle{plain}
\thispagestyle{plain}
\setlength{\headheight}{0pt}
\noindent
{\bf Michael's Research}

Computational complexity is narrowly defined as concerning the amount of time and memory and other resources required to solve computational problems, but it's really the quantitative study of apprehending information.  That wider scope is good to point to because our current knowledge of the resource requirements is pathetic.  The P=?NP question is about whether the large body of NP-complete problems require (more than) some polynomial in $n$ time as the data size $n$ grows, but the real frontier is whether any of them can be shown to require more than \emph{linear} time on a realistic model---and for the model of Boolean circuits no lower bound higher than $5.5 n$ has been proved. The main positive discovery has been that the myriad natural computational problems quantize into surprisingly few equivalence classes related by efficient \emph{reductions}.  The frontier action has anyway been in the range from linear to quadratic time (so-called ``fine-grained complexity''), in circuit complexity, randomized algorithms, and recently in \emph{parameterized} complexity---meaning that bounds are expressed in other parameter(s) $k,\dots$ besides the input length $n$.  Michael has a distinctive perch in the first and fourth of these using (nondeterministic) finite automata, which unlike the (nondeterministic) Turing machines underlying P and NP belong to the linear-time realm.

An example problem is whether a given directed graph contains a directed triangle, or in simpler terms, whether an $m \times m$ matrix $A$ of numbers has indices $i,j,k$ such that the entries $A[i,j]$, $A[j,k]$, and $A[k,i]$ are all nonzero.  The simple algorithm that loops over $i,j,k$ takes time $O(m^3)$, which is $O(n^{1.5})$ since $n = m^2$ is reckoned as the size of the matrix.  It may seem that one cannot do better but the amazing $O(m^{\omega})$ algorithm of Volker Strassen for matrix multiplication, since refined to get $\omega$ down to about $2.373$, propagates to this problem.   In terms of $n$ this is $O(n^{1.186\dots})$.  Does the special-case nature of the triangle problem, say when $G$ is undirected ($A$ is symmetric), allow $O(n)$ time, or $O(n\log n)$ time like for sorting?  Reuven Bar-Yehuda of the Technion in Haifa spent a year with my senior colleague Alan Selman in Buffalo in 1993-94 and told me he'd recently spent a \emph{year} on the problem, ``completely wasted---it's a  \emph{disease}.''  Twenty-five years since have seen no breakthrough, though MIT's Ryan Williams (second subject of my recent blog article 
https://rjlipton.wordpress.com/2018/01/23/progress-on-the-frontier/) came up with contingent results.  This is all to say: computational complexity \emph{is a hard area}.  

The fulcrum of Michael's research, on which he may now be counted the world's expert, is \emph{intersection (non-)emptiness of finite automata}.  I can frame the basic idea differently from how he does: Suppose we have $k$-many finite automata each with $n$ states and $m$ instructions.  For deterministic finite automata the number of instructions is $m = nc$ where $c$ is the alphabet size.  Our total data has $O(km)$ size.  We can combine the machines into one via the classical Cartesian product construction but that makes $n^k$ states and (in the deterministic case) as many as $cn^k$ instructions.  Now suppose there is exactly one string $x$ that all $k$ machines accept---i.e., that is in the intersection of their languages.  In the deterministic case, $x$ may have length up to $N = n^k - 1$.  But we can specify it with the original $O(km)$ data.  This means the string $x$ is pretty special among strings of length $N$, and this in turn creates ``potential energy'' that can be leveraged both for theoretical and practical work.  Indeed, Lempel-Ziv and other compression schemes that employ \emph{grammar-based codes} turn on a similar uniqueness condition for context-free grammars \emph{vis-\`a-vis} pushdown automata, which are the next class of machine up from finite automata and also belong to the linear-time realm.  Michael's latest result, with Mateus Oliveira of Bergen, Norway, in their submitted ICALP 2018 paper, connects the $k=2$, $c=2$ case to the triangle-finding problem in a new way.  The result is still conditional---as most of them are---but shows that something new could be found even in the \emph{simplest} case of his problem and that it connects to the key frontier action.

When the finite automata are nondeterministic the string(s) $x$ can be \emph{exponentially longer} and then things really get wild and woolly.  The wildness is the same order as the P=NP and the over-arching ``P=PSPACE'' questions but carries a different approach.  The main difference I appreciate is that whereas the analysis in terms of Turing machines has heretofore been wholly asymptotic, finite automata by their nature are \emph{concrete}.  This is what makes them more amenable as a basis for fine-grained complexity.  The knock on complexity theory for a young researcher has been that the guys of mine and Lipton's generations have found countless more roadblocks than breakthroughs in the avenues we tried, so that our track-`A' sectors have much of a ``built-out'' feel.   But there is plenty of new construction in Michael's area---which borders on track-`B' as referenced above (more logic + systems than algorithms + data structures).  

Michael's PhD thesis and earlier papers brought in parameterized complexity.  I wrote papers with this subfield's progenitors Rod Downey and Mike Fellows, who credit a logic-based 1989 paper of mine as a source (and my own main contribution adapted a logic-based theorem of Ron Fagin to this area), but now this subfield has been `discovered' and mushroomed by algorithms people.  Daniel Lokshtanov, also of Bergen, had an astounding 6 joint papers at this year's premier algorithms conference SODA 2018 mostly via this connection, plus 4 joint papers at ICALP 2017.  He was instrumental to inviting Michael to summarize his work in the February 2017 \emph{Parameterized Complexity Newsletter} and also hailed it in a blog-comment to my own review of Michael's thesis at https://rjlipton.wordpress.com/2017/01/18/level-by-level/ .  Michael showed that parameterized reductions are the most efficacious way to ``control'' the classification of problems according to \emph{fine-grained} levels in the older ``classical'' complexity theory.  He then showed that almost any nontrivial improvement in the parameterized bounds for these problems would have a powerful knock-on effect for their ``classical'' bounds.  Furthermore, although the parameterized reductions' property of ``cross-cutting'' classical hardness (which makes them useful as tools of analysis) is contingent, failure of the contingency would lead to breakthrough classical lower bounds.  This is as close to a `win-win' situation as we can currently establish.  These connections again are directed by the various cases of the intersection (non-)emptiness problem.

I think this work has high promise, plus he is simply brilliant.  This has been recognized by others besides his references, for instance by his selection for the 2015 China Theory Week in Shanghai (an invitational workshop for young researchers where he gave a presentation)---I had no role in that.  Now I've taught courses with 100+ undergraduates not only in theory of computation but also in our core programming languages, data structures (with full-bore C++ immersion), and discrete mathematics requirements---and I embraced them all pre-tenure---so I think I have some right to recommend someone to be \emph{more} research-selfish and do \emph{less} teaching.  As such, I'd rate Michael a favorite to match those who have recently garnered research funding and tenure at institutions on the level of my own.  But that's not who Michael is, as I'd appreciated even before he sought my blessing to spend much of summer 2015 over at RIT (70 miles away) teaching their summer theory course since a student of Selman's already had ours.  I was impressed that RIT acceded to an interloper with no input from me.  So I'll segue to his teaching.




\bigskip
\noindent
{\bf Michael's Teaching}

Behind his ever-friendly and tech-literate persona, Michael is `old-school' in an inexorable manner.  Sometimes his standards of getting everything right---applied to himself---kept him from availing shortcuts my grading scheme was designed to provide so as to deal most efficiently with 100-150-200 homework submissions each week.  Applied to the students, this means he brooks nothing less than the standards where he sets them, and often spends interactive time until the line is met.  What his teaching evaluations say about his writing in full sentences during lectures is part of the same quality.  He represents that the innate power of his subject commands best in a standard approach, rather than any ``jazz-it-up'' or ``drive to modernize'' impetus.

He was a great TA in courses with me and popular with the undergraduates.  The only tension was getting him not to consume more than my projections of no more than 16 weekly hours on defined tasks (out of 20 hours total), of which no more than 8 on grading.  Once his duties were split 10-10 with the intro-CS course since he wanted the experience and he managed that situation perfectly.  He also headed up the crew for our software-engineering course, which reminds me to say that ``despite being a theoretician'' \emph{he knows how to code} (well I code all the time for my research, 40,000+ lines of C++ and Perl in my chess work and 5,000+ with my current student for simulating quantum circuits).  All this adds up to the polar opposite of a TA who mostly grades and takes just his assigned sections.  His engagement with undergraduate students at the largest school in the NY State system shows that he can thrive and be effective in schools of any size.

Also packed into his 3.5 years was a year as president of our graduate student body which is 90\% from overseas.  I can't help mentioning that he was succeeded by a remarkable cabinet of three Iranians (plus one other) including two women---one of whom was president and ably TA-ed data structures for me her second term in Buffalo.  I don't know if Michael is conversationally fluent in any foreign languages but his knowledge of international linguistics is evinced by the \emph{Treegle} project and his wide travels abroad also speak to international experience and outlook.  He is however restricting his ambit of applications to Pennsylvania and environs for personal reasons.  

In sum I can give him my highest recommendation.  Above all, he is simply a really nice and
unassuming person to work with---up there with my best-ever student
D.\ Sivakumar in many respects.
I've given examples above of both the youthful energy and high maturity that 
augur well for success in his hire.
I will be happy to answer any further questions you may have.








\closing{Yours sincerely}

\end{letter}

\end{document}

