Abstract A classic result of Paul, Pippenger, Szemerédi and Trotter states that ${\textsf {DTIME}}(n) \subsetneq {\textsf {NTIME}}(n)$ DTIME ( n ) ⫋ NTIME ( n ) . The natural question then arises: could the inclusion ${\textsf {DTIME}}(t(n)) \subseteq {\textsf {NTIME}}(n)$ DTIME ( t ( n ) ) ⊆ NTIME ( n ) hold for some superlinear time-constructible function t(n)? If such a function t(n) does exist, then there also exist effective nondeterministic guessing strategies to speed up deterministic computations. In this work, we prove limitations on the effectiveness of nondeterministic guessing to speed up deterministic computations by showing that the existence of effective nondeterministic guessing strategies would have unlikely consequences. In particular, we show that if a subpolynomial amount of nondeterministic guessing could be used to speed up deterministic computation by a polynomial factor, then ${\textsf {P}}~ \subsetneq {\textsf {NTIME}}(n)$ P ⫋ NTIME ( n ) . Furthermore, even achieving a logarithmic speedup at the cost of making every step nondeterministic would show that SAT ∈NTIME(n) under appropriate encodings. Of possibly independent interest, under such encodings we also show that SAT can be decided in O(nlogn) steps on a nondeterministic multitape Turing machine, improving on the well-known O(n(logn)c) bound for some constant but undetermined exponent c ≥ 1.

In this work, we focus on developing resources for group programming and software engineering education which are important topics within Computer Science curriculums. Our goal is to help educators to be able to understand and assess their students' software projects. To achieve this goal, my advisor and I have developed a web-based application that processes student code repositories and visualizes the resulting data. In our analysis, we use coding metrics such as the number of commits made and number of lines coded (this includes insertions and deletions) along with commit frequency. From this analysis, we are able to curate specific information to help the educator answer questions about fairness, timeliness, consistency, and overall contribution from each student. In the future, we hope to make our application available for all educators.

We introduce techniques for proving superlinear conditional lower bounds for polynomial time problems. In particular, we show that CircuitSAT for circuits with m gates and log(m) inputs (denoted by log-CircuitSAT) is not decidable in essentially-linear time unless the exponential time hypothesis (ETH) is false and k-Clique is decidable in essentially-linear time in terms of the graph's size for all fixed k. Such conditional lower bounds have previously only been demonstrated relative to the strong exponential time hypothesis (SETH). Our results therefore offer significant progress towards proving unconditional superlinear time complexity lower bounds for natural problems in polynomial time.

We show that any one-counter automaton with $n$ states, if its language is non-empty, accepts some word of length at most $O(n^2)$. This closes the gap between the previously known upper bound of $O(n^3)$ and lower bound of $\Omega(n^2)$. More generally, we prove a tight upper bound on the length of shortest paths between arbitrary configurations in one-counter transition systems (weaker bounds have previously appeared in the literature). Comment: 28 pages, 2 figures