Department of Computer Science
http://hdl.handle.net/2104/4770
2014-03-28T02:18:22ZMatrix Representations of GF(p[superscript n]) over GF(p)
http://hdl.handle.net/2104/8928
Matrix Representations of GF(p[superscript n]) over GF(p)
Maurer, Peter M.
We show that any non-singular nxn matrix of order p[superscript n]-1 over GF(p) is a generator of a matrix representation of GF(p[superscript n]). We also determine the number of matrix representations of GF(p[superscript n])GF(p) over GF(p), and then number of order p[superscript n]-1 matrices in the general linear group of degree n over GF(p). The theorems are easily generalizable to arbitrary field extensions.
2014-01-31T00:00:00ZFields and Cyclic Codes for Error Detection
http://hdl.handle.net/2104/8894
Fields and Cyclic Codes for Error Detection
Hess, Rachel N.
This technical report discusses some of the aspects of error detection using finite fields.
2014-01-14T00:00:00ZFaster k-means clustering.
http://hdl.handle.net/2104/8826
Faster k-means clustering.
Drake, Jonathan, 1989-
The popular k-means algorithm is used to discover clusters in vector data automatically. We present three accelerated algorithms that compute exactly the same clusters much faster than the standard method. First, we redesign Hamerly’s algorithm to use k heaps to avoid checking distance bounds for all n points, with little empirical gain. Second, we use an adaptive number of distance bounds to avoid redundant calculations (Drake and Hamerly 2012). Experiments show the superior performance of adaptive k-means in medium dimension (20 ≤ d ≤ 200) on uniform random data. Finally, we reformulate the triangle inequality to constrain the search space for a point’s nearest center to an annular region centered at the origin. For uniform random data, annulus k-means is competitive with or much faster than other algorithms in low dimension (d < 20), and it outperforms other algorithms on five of six naturally-clustered, real-world datasets tested (d ≤ 74).
2013-09-24T00:00:00ZDesigning incentives in P2P systems.
http://hdl.handle.net/2104/8811
Designing incentives in P2P systems.
Berciu, Radu Mihai.
The goal of this thesis is bringing closer together the game theoretic approach of creating incentives with the requirements and properties of P2P systems. Briefly, we detail the P2P system context that incentive mechanisms must address, focusing on the main properties (e.g., the existence of cheap identities), types of transacted goods, common goals (e.g., maximize utilization, robustness to rational manipulations) and common problems (e.g., easy-riding) of such systems; we define the design space for P2P incentive mechanisms through the first taxonomy for such mechanisms and examine the main classes; we analyze in-depth how known incentive mechanisms achieve their goals, from both a P2P systems and a game theory perspectives using BitTorrent and mechanism design models; we bundle our prescriptions into a framework for designing P2P incentive mechanisms, and we use it to create an incentive mechanism for a BitTorrent-like system.
2013-09-24T00:00:00Z