| |
1-10 of 180 reviews |
Date Reviewed | |
| |
On the hardness of finding subsets with equal average
Elkind E., Orlin J. Information Processing Letters 113(13): 477-480, 2013. Type: Article
This paper proves that, given a set of positive integers, it is nondeterministic polynomial time (NP)-complete to determine whether there are two nonidentical (although possibly overlapping) subsets of that set such that the average of...
|
Dec 5 2014 |
|
| |
On a compact encoding of the swap automaton
Fredriksson K., Giaquinta E. Information Processing Letters 114(7): 392-396, 2014. Type: Article
A swapped version of a string P is a string obtained from P by a combination of swaps of adjacent symbols, with each symbol involved in at most one swap. This paper deals with the problem of findin...
|
Aug 19 2014 |
|
| |
Comorphisms of structured institutions
Ţuţu I. Information Processing Letters 113(22-24): 894-900, 2013. Type: Article
Once upon a time, programmers talked to their clients. Later, they were given a written specification instead. These specifications became standardized with special forms and formats. Academics explored special logics to use in them. G...
|
Dec 11 2013 |
|
| |
On the distinctness of modular reductions of primitive sequences modulo square-free odd integers
Zheng Q., Qi W., Tian T. Information Processing Letters 112(22): 872-875, 2012. Type: Article
The study of maximal period linear recurring sequences, or primitive sequences, over ring ℤ/(M) (for some special positive integer M) is of cryptographic importance. In deriving a good ps...
|
May 10 2013 |
|
| |
A correspondence between type checking via reduction and type checking via evaluation
Sergey I., Clarke D. Information Processing Letters 112(1-2): 13-20, 2012. Type: Article
This paper deals with the implementation of a type checker for the simply typed lambda calculus in the Standard ML language. A type system is generally defined via a set of predicates that are defined inductively following the structur...
|
Mar 25 2013 |
|
| |
Scheduling on parallel identical machines with job-rejection and position-dependent processing times
Gerstl E., Mosheiov G. Information Processing Letters 112(19): 743-747, 2012. Type: Article
Three new theorems, solving upper bounds for scheduling n jobs on m parallel identical machines, are derived in this paper. The scheduling problem is reduced to a restricted linear assignment probl...
|
Nov 27 2012 |
|
| |
A simple division-free algorithm for computing determinants
Bird R. Information Processing Letters 111(21-22): 1072-1074, 2011. Type: Article
The determinant of a matrix has a long history in mathematics. It is usually discussed along with Cramer’s rule for the solution of systems of linear equations. As late as the 1950s, the evaluation of 2×2 and 3&#...
|
Sep 28 2012 |
|
| |
Fast brief practical DFA minimization
Valmari A. Information Processing Letters 112(6): 213-217, 2012. Type: Article
It is very unusual to see a paper on computational complexity that focuses on actual code, rather than using a higher-level pseudocode description of algorithms. Valmari’s paper presents a complete C++ program for finding a m...
|
Jul 2 2012 |
|
| |
Taking the final step to a full dichotomy of the possible winner problem in pure scoring rules
Baumeister D., Rothe J. Information Processing Letters 112(5): 186-190, 2012. Type: Article
There has quite naturally been much interest in studying the computational difficulties in trying to manipulate elections. This paper looks at a case that had not been classified in any of the earlier work: the difficulty of manipulati...
|
Jun 25 2012 |
|
| |
 Speeding up CRC32C computations with Intel CRC32 instruction
Gueron S. Information Processing Letters 112(5): 179-185, 2012. Type: Article
Gueron introduces an algorithm to speed up the CRC32C implementation using the corresponding central processing unit (CPU) CRC32 instruction from Intel to compute cyclic redundancy checks of an arbitrary length buffer with inputs rangi...
|
Jun 11 2012 |
|
| |
|
|
| |
|
|
|
|
