1,570 research outputs found
A study of the implementation of virtual instrumentation in university laboratory environments
No full textIn this work six engineering and physical science laboratory experiments were developed to enhance the learning experience for students. This was achieved by instrumenting and creating virtual instruments for these experiments. The use of virtual instrumentation is directly compared with traditional laboratory teaching techniques and pedagogical principles from which both methods have developed from are discussed. Previous work utilising Computer Based Learning (CBL) in similar projects relating to this work have been used to evaluate some of the benefits of virtual instrumentation, especially those relating to increased student interest, memory retention, understanding and ultimately performance in laboratory reports. The virtual experiments discussed in this study are redesigned versions of traditional style experiments and hence a direct comparison of newer CBL techniques to traditional style laboratories was undertaken. There was no change in concepts being between the two versions of the experiments; the only difference was in the methodology of presentation. The effectiveness of these CBL techniques was assessed by looking at the performance of students using virtual instrumentation against that of other students from the same class undertaking the traditional mode of the experiments. All students were assessed by report submission, multiple choice questions relating to their experiment and questionnaires. The results of this study were also compared to other related studies within the field of CBL
On the Structure, Covering, and Learning of Poisson Multinomial Distributions
No full textAn (n, k)-Poisson Multinomial Distribution (PMD) is the distribution of the sum of n independent random vectors supported on the set Bk={e1,...,ek} of standard basis vectors in Rk. We prove a structural characterization of these distributions, showing that, for all ε > 0, any (n, k)-Poisson multinomial random vector is ε-close, in total variation distance, to the sum of a discretized multidimensional Gaussian and an independent (poly(k/ε), k)-Poisson multinomial random vector. Our structural characterization extends the multi-dimensional CLT of Valiant and Valiant, by simultaneously applying to all approximation requirements ε. In particular, it overcomes factors depending on log n and, importantly, the minimum Eigen value of the PMD's covariance matrix. We use our structural characterization to obtain an ε-cover, in total variation distance, of the set of all (n, k)-PMDs, significantly improving the cover size of Daskalakis and Papadimitriou, and obtaining the same qualitative dependence of the cover size on n and ε as the k=2 cover of Daskalakis and Papadimitriou. We further exploit this structure to show that (n, k)-PMDs can be learned to within ε in total variation distance from Õk(1/ε) samples, which is near-optimal in terms of dependence on ε and independent of n. In particular, our result generalizes the single-dimensional result of Daskalakis, Diakonikolas and Servedio for Poisson binomials to arbitrary dimension. Finally, as a corollary of our results on PMDs, we give a Õk(1/ε2) sample algorithm for learning (n, k)-sums of independent integer random variables (SIIRVs), which is near-optimal for constant k.Alfred P. Sloan Foundation (Fellowship)Microsoft Research Faculty FellowshipNational Science Foundation (U.S.) (Award CCF-0953960 (CAREER))National Science Foundation (U.S.). Division of Computing and Communication Foundations (CCF-1101491)Simons Award for Graduate Students in Theoretical Computer Scienc
Programming language foundations / Aaron Stump, Department of Computer Science, University of Iowa.
No full textcomputer bookfair2015Includes bibliographical references (pages 321-323) and index.x, 326 pages :"Stump's Programming Language Foundations is a short concise text that covers semantics, equally weighting operational and denotational semantics for several different programming paradigms: imperative, concurrent, and functional. Programming Language Foundations provides: an even coverage of denotational, operational an axiomatic semantics; extensions to concurrent and non-deterministic versions; operational semantics for untyped lambda calculus; functional programming; type systems; and coverage of emerging topics and modern research directions. "-- Provided by publisher
Foundations of
No full textWe review the book Foundations of Artificial Intelligence (ed. David Kirsch, MIT Press, Cambridge, MA, 1993) and present a framework for the analysis of theories of artificial intelligence. Publishing Information To appear in Philosophical Psychology. Author Information Ashwin Ram is an Assistant Professor in the College of Computing of the Georgia Institute of Technology, and an Adjunct Professor in the School of Psychology. He received his B.Tech. in Electrical Engineering from the Indian Institute of Technology, New Delhi, in 1982, and his M.S. in Computer Science from the University of Illinois at Urbana-Champaign in 1984. He received his Ph.D. degree from Yale University for his dissertation on "Question-Driven Understanding: An Integrated Theory of Story Understanding, Memory, and Learning" in 1989. His research interests lie in the areas of machine learning, natural language understanding, explanation, and cognitive science, and he has several research publications in these ..
JSketch: Sketching for Java
No full textSketch-based synthesis, epitomized by the Sketch tool, lets developers synthesize software starting from a partial program, also called a sketch or template. This paper presents JSketch, a tool that brings sketch-based synthesis to Java. JSketch's input is a partial Java program that may include holes, which are unknown constants, expression generators, which range over sets of expressions, and class generators, which are partial classes. JSketch then translates the synthesis problem into a Sketch problem; this translation is complex because Sketch is not object-oriented. Finally, JSketch synthesizes an executable Java program by interpreting the output of Sketch.National Science Foundation (U.S.) (CCF-1139021)National Science Foundation (U.S.) (CCF- 1139056)National Science Foundation (U.S.) (CCF-1161775)University of Maryland (College Park, Md.). Institute for Advanced Computer StudiesLaboratory for Telecommunication Sciences
Intellectual structure and subject themes in information systems research : a journal cocitation study
No full textInformation Systems (IS) is a discipline in which research and practice are closely intertwined. IS is also closely related to and overlapping several other disciplines, including Information Science. Thus, IS provides an excellent case for examining the interplay of research and practice in a rapidly changing discipline. We explore the intellectual structure and subject themes in Information Systems (IS) research for 1990 to 1999 through the identification and analysis of the field's core journal literature. A core journal list of 100 titles was created and examined with journal cocitation analysis (JSA). JSA demonstrates that IS is a coherent discipline with research ranging from technology-oriented software and hardware to the application of IS in business and organizations. Journals are grouped into seven subject clusters: computer science, computer networking, computer engineering, information science, software engineering, human-computer
interaction, and management information systems. Information Science journals occupy a bridging position between technically oriented and application-focused clusters. ASIST publications, JASIST, ARIST, and PASIS, figure prominently in the Information Science cluster
Web Science
No full textOur understanding of the Web has not kept pace with its development. It is engineered using formally specified languages and protocols, but has large scale effects on society. Certain human activities – including education – have been altered irretrievably. This article argues for the development of the discipline of Web Science, to understand the reciprocal relationship between the Web and society at a number of scales, from technical protocols to emergent social behaviour, to ensure that the Web’s growth will continue, and will benefit society. The need for both analysis and engineering demands an inherently interdisciplinary approach. With this in mind, a new Web Science Research Initiative is briefly described
Distributed PCP Theorems for Hardness of Approximation in P
No full text© 2017 IEEE. We present a new distributed} model of probabilistically checkable proofs (PCP). A satisfying assignment x ∈{0,1}^n to a CNF formula φ is shared between two parties, where Alice knows x-1, \dots, x-{n/2, Bob knows x-{n/2+1},\dots,x-n, and both parties know φ. The goal is to have Alice and Bob jointly write a PCP that x satisfies φ, while exchanging little or no information. Unfortunately, this model as-is does not allow for nontrivial query complexity. Instead, we focus on a non-deterministic} variant, where the players are helped by Merlin, a third party who knows all of x.Using our framework, we obtain, for the first time, PCP-like reductions from the Strong Exponential Time Hypothesis (SETH) to approximation problems in \P. In particular, under SETH we show that %(assuming SETH) there are no truly-subquadratic approximation algorithms for %the following problems: Maximum Inner Product over \{0,1\}-vectors, LCS Closest Pair over permutations, Approximate Partial Match, Approximate Regular Expression Matching, and Diameter in Product Metric. All our inapproximability factors are nearly-tight. In particular, for the first three problems we obtain nearly-polynomial factors of 2^{(log n)^{1-o(1)}};only (1+o(1))-factor lower bounds (under SETH) were known before.As an additional feature of our reduction, we obtain new SETH lower bounds for the exact} monochromatic Closest Pair problem in the Euclidean, Manhattan, and Hamming metrics
Frontmatter, Table of Contents, Preface, Conference Organization, Author Index
No full textThis proceedings volume has the papers presented at the 30th annual conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010), held at the Institute of Mathematical Sciences (IMSc), Chennai, during 15–18 December 2010.
The conference attracted 128 submissions from 35 countries in 6 continents, most of them of very high quality. We thank the authors who submitted for making this such a competitive conference. The PC succeeded in obtaining the help of 216 external reviewers, in all producing 400 referee reports which were of immeasurable help in deciding the 38 contributed papers which have made it to this publication
Hardness Magnification for all Sparse NP Languages
No full text© 2019 IEEE. In the Minimum Circuit Size Problem (MCSP[s(m)]), we ask if there is a circuit of size s(m) computing a given truth-Table of length n = 2m. Recently, a surprising phenomenon termed as hardness magnification by [Oliveira and Santhanam, FOCS 2018] was discovered for MCSP[s(m)] and the related problem MKtP of computing time-bounded Kolmogorov complexity. In [Oliveira and Santhanam, FOCS 2018], [Oliveira, Pich, and Santhanam, CCC 2019], and [McKay, Murray, and Williams, STOC 2019], it was shown that minor (n{1+eps}-style) lower bounds for MCSP[2o(m)] or MKtP[2o(m)] would imply breakthrough circuit lower bounds such as NP is not in P/poly, NP is not in NC1, or EXP is not in P/poly. We consider the question: What is so special about MCSP and MKtP? Why do they admit this striking phenomenon? One simple property is that all variants of MCSP (and MKtP) considered in prior work are sparse languages. For example, MCSP[s(m)] has 2{O(s(m))} yes-instances of length n=2m, so MCSP[2o(m)] is 2{no(1)}-sparse. We show that there is a hardness magnification phenomenon for all equally-sparse NP languages. Formally, suppose there is an eps > 0 and a language L in NP which is 2{no(1)}-sparse, and L is not in Circuit[n{1+eps}]. Then NP does not have nk-size circuits for all k. We prove analogous theorems for De Morgan formulas, B-2-formulas, branching programs, AC0[6] and TC0 circuits, and more: improving the state of the art in NP lower bounds against any of these models by an eps factor in the exponent would already imply NP lower bounds for all fixed polynomials. In fact, in our proofs it is not necessary to prove a (say) n{1+eps} circuit size lower bound for L: one only has to prove a lower bound against n{1+eps}-Time neps-space deterministic algorithms with neps advice bits. Such lower bounds are well-known for non-sparse problems. Building on our techniques, we also show interesting new hardness magnifications for search-MCSP and search-MKtP (where one must output small circuits or short representations of strings), showing consequences such as Parity-P (or PP, PSPACE, and EXP) is not contained in P/poly (or NC1, AC0[6], or branching programs of polynomial size). For instance, if there is an eps > 0 such that search-MCSP[2{beta m}] does not have De Morgan formulas of size n{3+eps} for all constants beta > 0, then -P ⊄ NC1
- …
