Introduction to the theory of computation

By E. Gurari. 1989

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Entropy-SGD: biasing gradient descent into wide valleys (2016, background): “In discrete optimization problems, such wide local minima are dense clusters of solutions in the parameter space where nearby parameters have similar energy, say, the number of clauses violated in k-SAT (Sipser, 2006; Achlioptas & Ricci-Tersenghi, 2006).”
On the Computational Efficiency of Training Neural Networks (2014, background): “, [22]), and the fact that we can simulate the standard boolean gates using a fixed number of neurons.”
Abstract Syntax Networks for Code Generation and Semantic Parsing (2017, methodology): “Direct evaluation of functional equivalence is of course impossible in general (Sipser, 2006), and practically challenging even for the HEARTHSTONE dataset because it requires integrating with the game engine.”
Ether: malware analysis via hardware virtualization extensions (2008, background): “In automata theory, the above problem would be formally represented as the problem of determining whether the language of two Turing machines ( L and L’ ) are equal; it is otherwise known as the undecidable problem EQ TM [41].”
The Book Review Column (2000, unknown): “exam, Martin [Mar91] for teaching in the past, and having decided to teach using Sipser [Sip97] in the future, I was pleasantly surprised to discover that most of the presentation, if not the topics, in Pippenger’s book were new to me.”
Entrusting Private Computation and Data to Untrusted Networks (2013, methodology): “3 shows the 64 possible types of tiles of the 3-SATsolving assembly.”
Meta-learning of Sequential Strategies (2019, methodology): “That is, the recursive function f ∗ implements a state machine [Sipser, 2006] (or transducer) in which the states correspond to memory states, the transitions are the changes of the memory state caused by an input, and where the outputs are the predictions.”
Most Tensor Problems Are NP-Hard (2009, methodology): “We refer the reader to [Sipser 2012] for a proper treatment and to [Poonen 2012] for an extensive list of undecidable problems arising from many areas of modern mathematics.”
Limits on fundamental limits to computation (2014, background): “Limits formulated in such crude terms (unsolvability in polynomial time on any computer) are powerful [75]: the hardness of number-factoring underpins Internet commerce, while”
HVLearn: Automated Black-Box Analysis of Hostname Verification in SSL/TLS Implementations (2017, methodology): “We compute the product DFA using standard automata algorithms [60].”
Quantum walks: a comprehensive review (2012, background): “optimization problems, typically within the sphere of NP-hard problems [351,410], can be seen as ‘detect and/or identify object(s)’ problems whose solutions ask for search algorithms).”
TIP: Typifying the Interpretability of Procedures (2017, background): “Should that inform our notion of interpretability? Taking inspiration from the theory of computation [46] where a language is classified as regular, context free, or something else based on the strength of the machine (i.”