Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Publication
Articles 1 - 5 of 5
Full-Text Articles in Physical Sciences and Mathematics
Mccolm’S Conjecture, Yuri Gurevich, Neil Immerman, Saharon Shelah
Mccolm’S Conjecture, Yuri Gurevich, Neil Immerman, Saharon Shelah
Neil Immerman
Gregory McColm conjectured that positive elementary inductions are bounded in a class K of finite structures if every (FO + LFP) formula is equivalent to a first-order formula in K. Here (FO + LFP) is the extension of first-order logic with the least fixed point operator. We disprove the conjecture. Our main results are two model-theoretic constructions, one deterministic and the other randomized, each of which refutes McColm’s conjecture.
On A Learnability Question Associated To Neural Networks With Continuous Activations, Bhaskar Dasgupta, Hava Siegelmann, Eduardo Sontag
On A Learnability Question Associated To Neural Networks With Continuous Activations, Bhaskar Dasgupta, Hava Siegelmann, Eduardo Sontag
Hava Siegelmann
This paper deals with learnability of concept classes defined by neural networks, showing the hardness of PAC-learning (in the complexity, not merely information-theoretic sense) for networks with a particular class of activation. The obstruction lies not with the VC dimension, which is known to grow slowly; instead, the result follows the fact that the loading problem is NP-complete. (The complexity scales badly with input dimension; the loading problem is polynomial-time if the input dimension is constant). Similar and well-known theorems had already been proved by Megiddo and by Blum and Rivest, for binary-threshold networks. It turns out the general problem …
Multithreaded Computer Architecture: A Summary Of The State Of The Art, Robert Iannucci, Guang Gao, Robert Halstead, Burton Smith
Multithreaded Computer Architecture: A Summary Of The State Of The Art, Robert Iannucci, Guang Gao, Robert Halstead, Burton Smith
Robert A Iannucci
No abstract provided.
Technology Transfer At Motorola, Robert Yacobellis
Technology Transfer At Motorola, Robert Yacobellis
Robert H Yacobellis
No abstract provided.
The Variable Elision Of Unstressed Vowels In European Portuguese: A Case Study, David James Silva
The Variable Elision Of Unstressed Vowels In European Portuguese: A Case Study, David James Silva
David Silva