146 research outputs found
Review of <em>Advancing Global Education: Patterns of Potential Human Progress</em>
No full textDennis Soltys reviews the second volume of a five-part series that will further comprise health, infrastructure, and governance. The first volume, on poverty, was reviewed by this author in the No. 2, 2010, issue of the journal of Poverty & Public Policy.Education, education, global, poverty, development
Review of <em>Reducing Global Poverty: Patterns of Potential Human Progress, Vol. 1</em>
No full textDennis Soltys, author of <em>Education for Decline: Soviet Vocational and Technical Schooling from Khrushchev to Gorbachev</em> (Toronto: University of Toronto Press, 1997), reviews this book that discusses poverty and the human condition in many of the poorest regions around the globe.Poverty, global poverty, policymaking, human potential
sj-pdf-1-dst-10.1177_19322968211059537 – Supplemental material for Diabetes Device Downloading: Benefits and Barriers Among Youth With Type 1 Diabetes
No full textSupplemental material, sj-pdf-1-dst-10.1177_19322968211059537 for Diabetes Device Downloading: Benefits and Barriers Among Youth With Type 1 Diabetes by Benjamin A. Palmer, Karissa Soltys, M. Bridget Zimmerman, Andrew W. Norris, Eva Tsalikian, Michael J. Tansey and Catherina T. Pinnaro in Journal of Diabetes Science and Technology</p
A Proof of Concept for Homomorphically Evaluating an Encrypted Assembly Language
No full textFully homomorphic encryption allows computations to be made on encrypted data without decryption, while preserving data integrity. This feature is desirable in a variety of applications such as banking, search engine and database querying, and some cloud computing services. Despite not knowing the plaintext content of the data, a remote server performing the computation would still be aware of the functions being applied to the data. To address the issue, this thesis proposes a method of encrypting circuits and executing encrypted instructions, by combining fully homomorphic encryption and digital logic theory. We use the classic RISC Archtecture as a foundation of our work, and the result of our algorithm is essentially an encrypted programming language, where a remote server is capable of executing program code that was written and encrypted by a local client.Master of Science (MS
A Generalization of Square-free Strings
No full textOur research is in the general area of String Algorithms and Combinatorics on Words. Specifically, we study a generalization of square-free strings, shuffle properties of strings, and formalizing the reasoning about finite strings.
The existence of infinitely long square-free strings (strings with no adjacent repeating word blocks) over a three (or more) letter finite set (referred to as Alphabet) is a well-established result. A natural generalization of this problem is that only subsets of the alphabet with predefined cardinality are available, while selecting symbols of the square-free string. This problem has been studied by several authors, and the lowest possible bound on the cardinality of the subset given is four. The problem remains open for subset size three and we investigate this question. We show that square-free strings exist in several specialized cases of the problem and propose approaches to solve the problem, ranging from patterns in strings to Proof Complexity. We also study the shuffle property (analogous to shuffling a deck of cards labeled with symbols) of strings, and explore the relationship between string shuffle and graphs, and show that large classes of graphs can be represented with special type of strings.
Finally, we propose a theory of strings, that formalizes the reasoning about finite strings. By engaging in this line of research, we hope to bring the richness of the advanced field of Proof Complexity to Stringology.ThesisDoctor of Philosophy (PhD
LA, permutations, and the Hajós Calculus
No full textAbstractLA is a simple and natural logical system for reasoning about matrices. We show that LA, over finite fields, proves a host of matrix identities (so-called “hard matrix identities”) from the matrix form of the pigeonhole principle. LAP is LA with matrix powering; we show that LAP extended with quantification over permutations is strong enough to prove fundamental theorems of linear algebra (such as the Cayley–Hamilton Theorem). Furthermore, we show that LA with quantification over permutations expresses NP graph-theoretic properties, and proves the soundness of the Hajós Calculus. Several open problems are stated
Unambiguous Functions in Logarithmic Space
No full text The notion of nondeterminism is one of the most fundamental concepts in many areas of computer science. Unambiguity, requiring that there be at most one correct sequence of nondeterministic choices, has proved to be one of the most meaningful restrictions of nondeterminism. In the context of space-bounded Turing Machines, several variants of unambiguity have been proposed and studied, and some interesting results have been established, narrowing slightly the gap between deterministic and nondeterministic logarithmic-space computation. We study the different variants of unambiguity in the context of computing multi-valued functions (as opposed to the usual yes/no decision problems). We propose a modification to the standard computation models of Turing Machines and configuration graphs, which allows for unambiguity-preserving composition. We introduce a unified notation, capturing the different flavors of ambiguity. Furthermore, we define a notion of reductions (based on function composition), which allows non-determinism but controls its level of ambiguity. In the light of this framework we establish some reductions between different variants of path counting problems. We also investigate more carefully the technique of inductive counting, and obtain improvement of some existing results.ThesisDoctor of Philosophy (PhD
Fair Ranking in Competitive Bidding Procurement: A Case Analysis
No full textAbstractFair and transparent procurement procedures are a cornerstone of a well functioning free-market economy. In particular, bidding is a mechanism whereby companies compete for contracts; when functioning well, the process rewards both the quality of the proposal, and the “reasonableness” of the quote. This way, both the company and the public win. The bidding process requires a fair and transparent ranking procedure. Once the parameters of the competition are established, the company issuing the bid is required by law to abide by those parameters. Not surprisingly, opposing interests may try to “game the system.” The more complex the service, the harder it is to rank competing bids. Complex services require complex ranking, which in turn makes undue influence more difficult to uncover. In this paper we analyze the case of two companies, Reilly Security and Contemporary Security, bidding for the contract of providing security during the Pan American games ([1]) in Toronto 2015: The Pan Am Games are the world's third largest international multi-sport Games; they are only surpassed in size and scope by the Olympic Summer Games and the Asian Games. We argue that the ranking procedures did not reflect the quality of the bids, resulting in one of the companies submitting a substantially more expensive bid, and still winning the competition. The reader may gain information on this contentious matter by reading a number of newspaper articles: [2–5]. Article [5] mentions the results presented in this paper. The author consulted for Executek International on this matter
Formalizing Combinatorial Matrix Theory
No full textIn this thesis we are concerned with the complexity of formalizing reasoning in Combinatorial Matrix Theory (CMT). We are interested in the strength of the bounded arithmetic theories necessary in order to prove the fundamental results of this field. Bounded Arithmetic can be seen as the uniform counterpart of Propositional Proof Complexity. Perhaps the most famous and fundamental theorem in CMT is the K{\"o}nig's Min-Max Theorem (\KMM) which arises naturally in all areas of combinatorial algorithms. As far as we know, in this thesis we give the first feasible proof of \KMM. Our results show that Min-Max reasoning can be formalized with uniform Extended Frege. We show, by introducing new proof techniques, that the first order theory \LA with induction restricted to formulas---i.e., restricted to bounded existential matrix quantification---is sufficient to formalize a large portion of CMT, in particular \KMM. -\LA corresponds to polynomial time reasoning, also known as \ELA. While we consider matrices over , the underlying ring is , since we require that compute the number of 1s in the matrix (which for a 0-1 matrix is simply the sum of all entries---meaning ). Thus, over , \LA translates to \TC^0-Frege, while, as mentioned before, \ELA translates into Extended Frege. In order to prove \KMM in \ELA, we need to restrict induction to formulas. The main technical contribution is presented in Claim~4.3.4, ~Section~4.3.3. Basically, we introduce a polynomial time procedure, whose proof of correctness can be shown with \ELA, that works as follow: given a matrix of size such that , where the minimum cover is of size , our procedure computes a maximum selection of size , row by row. Furthermore, we show that Menger's Theorem, Hall's Theorem, and Dilworth's Theorem---theorems related to \KMM---can also be proven feasibly; in fact, all these theorems are equivalent to KMM, and the equivalence can be shown in \LA. We believe that this captures the proof complexity of Min-Max reasoning rather completely. We also present a new Permutation-Based algorithm for computing a Minimum Vertex Cover from a Maximum Matching in a bipartite graph. Our algorithm is linear-time and computationally very simple: it permutes the rows and columns of the matrix representation of the bipartite graph in order to extract the vertex cover from a maximum matching in a recursive fashion. Our Permutation-Based algorithm uses properties of \KMM Theorem and it is interesting for providing a new permutation---and CMT---perspective on a well-known problem.Doctor of Philosophy (PhD
A Propositional Proof System with Permutation Quantifiers
No full text Propositional proof complexity is a field of theoretical computer science which concerns
itself with the lengths of formal proofs in various propositional proof systems. Frege systems are an important class of propositional proof systems. Extended Frege augments them by allowing the introduction of new variables to abbreviate formulas. Perhaps the largest open question in propositional proof complexity is whether or not Extended Frege is significantly more powerful that Frege. Several proof systems, each introducing new rules or syntax to Frege, have been developed in an attempt to shed some light on this problem. We introduce one such system, which we call H, which allows for the quantification of transpositions of propositional variables. We show that H is sound and complete, and that H's transposition quantifiers efficiently represent any permutation. The most important contribution is showing that a fragment of this proof system, H*1, is equivalent in power to Extended Frege. This is a complicated and rather technical result, and is achieved by showing that H*1 can efficiently prove translations of the first-order logical theory ∀PLA, a logical theory well suited for reasoning about linear algebra and properties of graphs.ThesisMaster of Science (MSc
- …
