The Experts below are selected from a list of 18720 Experts worldwide ranked by ideXlab platform
Alo Rose - One of the best experts on this subject based on the ideXlab platform.
-
efficient collision resistant hashing from worst case assumptions on cyclic lattices
Theory of Cryptography Conference, 2006Co-Authors: Chris Peike, Alo RoseAbstract:The generalized Knapsack function is defined as fa(x)=∑iai ·xi, where a=(a1,...,am) consists of m elements from some ring R, and x=(x1,...,xm) consists of m coefficients from a specified subset S⊆R. Micciancio (FOCS 2002) proposed a specific choice of the ring R and subset S for which inverting this function (for random a,x) is at least as hard as solving certain worst-case problems on cyclic lattices. We show that for a different choice of S ⊂ R, the generalized Knapsack function is in fact collision-resistant, assuming it is infeasible to approximate the shortest vector in n-dimensional cyclic lattices up to factors $\tilde{O}(n)$. For slightly larger factors, we even get collision-resistance for anym≥ 2. This yields very efficient collision-resistant hash functions having key size and time complexity almost linear in the security parameter n. We also show that altering S is necessary, in the sense that Micciancio's original function is not collision-resistant (nor even universal one-way). Our results exploit an intimate connection between the linear algebra of n-dimensional cyclic lattices and the ring ℤ[α]/(αn−1), and crucially depend on the factorization of αn-1 into irreducible cyclotomic polynomials. We also establish a new bound on the discrete Gaussian distribution over general lattices, employing techniques introduced by Micciancio and Regev (FOCS 2004) and also used by Micciancio in his study of compact Knapsacks.
-
efficient collision resistant hashing from worst case assumptions on cyclic lattices
Lecture Notes in Computer Science, 2006Co-Authors: Chris Peike, Alo RoseAbstract:The generalized Knapsack function is defined as f a (x)= Σ i a i x i , where a = (a 1 ,...,a m ) consists of m elements from some ring R, and x = (x i ,...,x m ) consists of m coefficients from a specified subset S C R. Micciancio (FOCS 2002) proposed a specific choice of the ring R and subset S for which inverting this function (for random a, x) is at least as hard as solving certain worst-case problems on cyclic lattices. We show that for a different choice of S ⊂ R, the generalized Knapsack function is in fact collision-resistant, assuming it is infeasible to approximate the shortest vector in n-dimensional cyclic lattices up to factors 0(n). For slightly larger factors, we even get collision-resistance for any m > 2. This yields very efficient collision-resistant hash functions having key size and time complexity almost linear in the security parameter n. We also show that altering S is necessary, in the sense that Micciancio's original function is not collision-resistant (nor even universal one-way). Our results exploit an intimate connection between the linear algebra of n-dimensional cyclic lattices and the ring Z[α]/(α n -1), and crucially depend on the factorization of a n - 1 into irreducible cyclotomic polynomials. We also establish a new bound on the discrete Gaussian distribution over general lattices, employing techniques introduced by Micciancio and Regev (FOCS 2004) and also used by Micciancio in his study of compact Knapsacks.
Chris Peike - One of the best experts on this subject based on the ideXlab platform.
-
efficient collision resistant hashing from worst case assumptions on cyclic lattices
Theory of Cryptography Conference, 2006Co-Authors: Chris Peike, Alo RoseAbstract:The generalized Knapsack function is defined as fa(x)=∑iai ·xi, where a=(a1,...,am) consists of m elements from some ring R, and x=(x1,...,xm) consists of m coefficients from a specified subset S⊆R. Micciancio (FOCS 2002) proposed a specific choice of the ring R and subset S for which inverting this function (for random a,x) is at least as hard as solving certain worst-case problems on cyclic lattices. We show that for a different choice of S ⊂ R, the generalized Knapsack function is in fact collision-resistant, assuming it is infeasible to approximate the shortest vector in n-dimensional cyclic lattices up to factors $\tilde{O}(n)$. For slightly larger factors, we even get collision-resistance for anym≥ 2. This yields very efficient collision-resistant hash functions having key size and time complexity almost linear in the security parameter n. We also show that altering S is necessary, in the sense that Micciancio's original function is not collision-resistant (nor even universal one-way). Our results exploit an intimate connection between the linear algebra of n-dimensional cyclic lattices and the ring ℤ[α]/(αn−1), and crucially depend on the factorization of αn-1 into irreducible cyclotomic polynomials. We also establish a new bound on the discrete Gaussian distribution over general lattices, employing techniques introduced by Micciancio and Regev (FOCS 2004) and also used by Micciancio in his study of compact Knapsacks.
-
efficient collision resistant hashing from worst case assumptions on cyclic lattices
Lecture Notes in Computer Science, 2006Co-Authors: Chris Peike, Alo RoseAbstract:The generalized Knapsack function is defined as f a (x)= Σ i a i x i , where a = (a 1 ,...,a m ) consists of m elements from some ring R, and x = (x i ,...,x m ) consists of m coefficients from a specified subset S C R. Micciancio (FOCS 2002) proposed a specific choice of the ring R and subset S for which inverting this function (for random a, x) is at least as hard as solving certain worst-case problems on cyclic lattices. We show that for a different choice of S ⊂ R, the generalized Knapsack function is in fact collision-resistant, assuming it is infeasible to approximate the shortest vector in n-dimensional cyclic lattices up to factors 0(n). For slightly larger factors, we even get collision-resistance for any m > 2. This yields very efficient collision-resistant hash functions having key size and time complexity almost linear in the security parameter n. We also show that altering S is necessary, in the sense that Micciancio's original function is not collision-resistant (nor even universal one-way). Our results exploit an intimate connection between the linear algebra of n-dimensional cyclic lattices and the ring Z[α]/(α n -1), and crucially depend on the factorization of a n - 1 into irreducible cyclotomic polynomials. We also establish a new bound on the discrete Gaussian distribution over general lattices, employing techniques introduced by Micciancio and Regev (FOCS 2004) and also used by Micciancio in his study of compact Knapsacks.
Bryant A Julstrom - One of the best experts on this subject based on the ideXlab platform.
-
the quadratic multiple Knapsack problem and three heuristic approaches to it
Genetic and Evolutionary Computation Conference, 2006Co-Authors: Amanda Hiley, Bryant A JulstromAbstract:The quadratic multiple Knapsack problem extends the quadratic Knapsack problem with K Knapsacks, each with its own capacity Ck. A greedy heuristic fills the Knapsacks one at a time with objects whose contributions are likely to be large relative to their weights. A hill-climber and a genetic algorithm encode candidate solutions as strings over {0,1,...,K} with length equal to the number of objects. The hill-climber's neighbor operator is also the GA's mutation. In tests on 60 problem instances, the GA performed better than the greedy heuristic on the smaller instances, but it fell behind as the numbers of objects and Knapsacks grew. The hill-climber always outperformed the greedy heuristic, and on the larger instances, also the GA.
-
greedy genetic and greedy genetic algorithms for the quadratic Knapsack problem
Genetic and Evolutionary Computation Conference, 2005Co-Authors: Bryant A JulstromAbstract:Augmenting an evolutionary algorithm with knowledge of its target problem can yield a more effective algorithm, as this presentation illustrates. The Quadratic Knapsack Problem extends the familiar Knapsack Problem by assigning values not only to individual objects but also to pairs of objects. In these problems, an object's value density is the sum of the values associated with it divided by its weight. Two greedy heuristics for the quadratic problem examine objects for inclusion in the Knapsack in descending order of their value densities. Two genetic algorithms encode candidate selections of objects as binary strings and generate only strings whose selections of objects have total weight no more than the Knapsack's capacity. One GA is naive; its operators apply no information about the values associated with objects. The second extends the naive GA with greedy techniques from the non-evolutionary heuristics. Its operators examine objects for inclusion in the Knapsack in orders determined by tournaments based on objects' value densities. All four algorithms are tested on twenty problem instances whose optimum Knapsack values are known. The greedy heuristics do well, as does the naive GA, but the greedy GA exhibits the best performance. In repeated trials on the test instances, it identifies optimum solutions more than nine times out of every ten.
Frank Neumann - One of the best experts on this subject based on the ideXlab platform.
-
evolutionary algorithms for the chance constrained Knapsack problem
Genetic and Evolutionary Computation Conference, 2019Co-Authors: Yue Xie, Oscar Harper, Hirad Assimi, Aneta Neumann, Frank NeumannAbstract:Evolutionary algorithms have been widely used for a range of stochastic optimization problems. In most studies, the goal is to optimize the expected quality of the solution. Motivated by real-world problems where constraint violations have extremely disruptive effects, we consider a variant of the Knapsack problem where the profit is maximized under the constraint that the Knapsack capacity bound is violated with a small probability of at most α. This problem is known as chance-constrained Knapsack problem and chance-constrained optimization problems have so far gained little attention in the evolutionary computation literature. We show how to use popular deviation inequalities such as Chebyshev's inequality and Chernoff bounds as part of the solution evaluation when tackling these problems by evolutionary algorithms and compare the effectiveness of our algorithms on a wide range of chance-constrained Knapsack instances.
Guochuan Zhang - One of the best experts on this subject based on the ideXlab platform.
-
approximation algorithms for a bi level Knapsack problem
Theoretical Computer Science, 2013Co-Authors: Lin Chen, Guochuan ZhangAbstract:In this paper, we consider a variant of the Knapsack problem. There are two Knapsacks with probably different capacities, owned by two agents respectively. Given a set of items, each with a fixed size and a profit. The two agents select items and pack them into their own Knapsacks under the capacity constraint. Same items can be packed simultaneously to different Knapsacks. However, in this case the profit of such items may vary. One agent packs items into his Knapsack to maximize the total profit, while another agent can only pack items into his Knapsack as well but he cares about the total profits of items packed into two Knapsacks. The latter agent is a leader while the former is a follower. We aim at designing an approximation algorithm for the leader assuming that the follower is selfish. For different settings we provide approximation results.
-
approximation algorithms for a bi level Knapsack problem
Conference on Combinatorial Optimization and Applications, 2011Co-Authors: Lin Chen, Guochuan ZhangAbstract:In this paper, we consider a variant of Knapsack problem. There are two Knapsacks with probably different capacities, owned by two agents respectively. Given a set of items, each with a fixed size and a profit, the two agents select items and pack them into their own Knapsacks under the capacity constraint. Same items can be packed simultaneously to different Knapsacks. However, in this case the profit of such items can vary. One agent packs items into his Knapsack to maximize the total profit, while another agent can only pack items into his Knapsack as well but he cares the total profits of items packed into two Knapsacks. The latter agent is a leader while the former is a follower. We aim at designing an approximation algorithm for the leader assuming that the follower is selfish. For different settings we provide approximation results.
