1960年夏天斯特恩斯在位于纽约州东部的斯克内克塔迪的通用电气研究实验室，在那里他和尤里斯·哈特马尼斯开始一起研究状态指定问题。在1961年获得博士学位后，斯特恩斯加入哈特马尼斯成为通用电气研究实验室的信息学习分支的一名正式员工，受理查德·休伊管理。在研究实验室的气氛和环境鼓励了他们所热爱的自由的、不受约束的研究方式。

　　斯特恩斯和哈特马尼斯一开始在进行线性机器的分解方面的工作：简单电脑的模型如何能被分解成一些更小的线性机器的结合，且能完成相同的任务。关于这个主题他们发表了一些论文，并在1966年将他们的工作总结写入了一本书。后来他们开始研究计算复杂性，并在1965年发表了那篇让他们获得图灵奖的论文。

　　在哈特马尼斯离开通用电气而成为了康奈尔大学计算机科学系的系主任后，斯特恩斯开始和丹尼尔·卢森尔兹及菲利普·莱维斯一同工作。这个合作的一部分继续了在计算复杂性方面的研究。

　　复杂的的类层次结构所阐释的其中一点是有很多生活中的实际问题是非常复杂的以至于解决它们是不现实的。关于近似计算复杂度问题的研究表明求解有些问题的精确解会耗时非常长的时间而得到一个可以被证明与最优解很接近的近似可以被一个使用短得多的时间的算法解决。

　　卢森尔兹、莱维斯和斯特恩斯发表了一系列论文，并在1976年出版了一本关于编译器设计原理的书。一个编译器是将用高级语言写的程序翻译成指定平台机器码的程序。一个编译器设计问题是如何对某个程序语言的程序进行语法分析的问题。对于自然语言，对一个句子进行词法分析包括找到主语、谓语和宾语等等。程序语言通常使用上下文无关文法表达，而且使用这种文法写的程序必须能通过编译器的语法分析。使用上下文无关文法对一个“句子”（程序）进行语法分析的计算复杂度是n^3，这对于一个编译器来说代价太高了，不现实。这三位作者定义了一类特殊的上下文无关文法，LL(k)文法，它可以在线性时间内进行语法分析，也就是说复杂度只有n。他们用来描述对LL(k)文法进行语法分析的方法叫做自顶向下的语法分析而且现在已经是编译器设计的一个重要部分。他们还指出从程序语言到机器语言的大部分翻译工作可以在语法分析的同时完成。

　　在1978年斯特恩斯离开通用电气而去位于奥尔巴尼的纽约州立大学之后（卢森尔兹已在1977年离开去了奥尔巴尼），他继续和莱维斯一起工作。他们做了关于并发数据库系统的研究，在这种数据库中会有一些事务在同一个数据库中进行读和写操作。这种系统的目标之一是让事务尽可能并发地执行以增加系统的输出，但同时不会破坏数据库的正确性。他们写的关于这个主题的论文指出并发执行的一致性和正确性的充分必要条件是事务的可串行性——它指的是，所有并发运行事务的读写操作的影响必须和他们在某种顺序下串行运行（一个接一个）一样。在这之前已经知道可串行性是一致性的充分条件：如果执行时可串行的，结果就是对的。这篇论文指出除去一些特定的只有读操作的事务的情况，这也是一个必要条件：执行必须要可串行化才能保证正确。这个结论现在已经是所有数据库课程和数据库系统设计的核心部分。

　　在纽约州立大学，斯特恩斯开始和哈利·亨特三世进行长期合作。要证明所感兴趣的问题是很难的，通常需要将其“归约”（即映射）到那些已知很难的问题（假设P≠NP）。亨特和斯特恩斯研究了和归约相关的更深入的问题。他们试图寻找那些能将问题映射到具体情况的简单子集上的归约，因为实际感兴趣的具体情况可能都是很简单的。他们还试图寻找针对小规模问题的归约，因为规模越小，可以得到的关于复杂性的结论就越强。他们用幂指数法的概念对这些思想进行了形式化描述。除了一个一个地寻找归约，他们还尝试寻找了能被应用到多种对象的归约原理，特别是针对多种代数结构。通过这样，他们用同一个简单的理由说明了许多问题是很难的。

　　亨特和斯特恩斯还研究了和积问题，其中加法运算符和乘法运算符是来自可交换的半环。他们指出如果一个问题有像结构树所展示的那种好结构，那么这样的问题是可以用更少的运算符解决的。这里的“好结构”指的是用于自顶向下处理的小“有权深度”或自顶向上处理的“管道宽度。如果形象地来看和积问题，管道宽度是树宽的一种表现形式，但是如果用代数角度来看这个问题，用结构树就很清楚。然后，利用代数条件中的加法，他们扩展了结构树的概念以适应定量公式。他们还完成了次线性空间和受次线性树宽约束的或与问题的一个紧连接。

　　与拉维、哈利·亨特三世、丹尼尔· 卢森尔兹和马达夫·马拉地合作，斯特恩斯还有在动态系统方面的工作。

　　2000年9月，斯特恩斯退休并和他的夫人住在斯林格兰。他仍然会拜访并和大学以前的同事合作。