### A Linearithmic Time Algorithm for a Shortest Vector Problem in Compute-and-Forward Design

**2016-01-30**

1602.00169 | cs.IT

We propose an algorithm with expected complexity of $\bigO(n\log n)$
arithmetic operations to solve a special shortest vector problem arising in
computer-and-forward design, where $n$ is the dimension of the channel vector.
This algorithm is more efficient than the best known algorithms with proved
complexity.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2013-06-02**

1306.0160 | stat.ML

Phase retrieval problems involve solving linear equations, but with missing
sign (or phase, for comp… show more

**2019-05-28**

1905.11963 | cs.LG

A well-known problem in data science and machine learning is {\em linear
regression}, which is recen… show more

**2018-10-15**

1810.06740 | cs.DS

The Light Bulb Problem is one of the most basic problems in data analysis.
One is given as input $n$… show more

**2019-05-05**

1905.01748 | cs.DS

Distributed processing frameworks, such as MapReduce, Hadoop, and Spark are
popular systems for proc… show more

**2015-06-29**

1506.08536 | stat.ML

This papers introduces an algorithm for the solution of multiple kernel
learning (MKL) problems with… show more

**2018-02-25**

Given $n$ vectors $x_0, x_1, \ldots, x_{n-1}$ in $\{0,1\}^{m}$, how to find
two vectors whose pairwi… show more

**2018-09-25**

1809.09698 | cs.DS

Packing and covering semidefinite programs (SDPs) appear in natural
relaxations of many combinatoria… show more

**2019-01-24**

1901.08686 | math.OC

We study the complexity of approximating Wassertein barycenter of $m$
discrete measures, or histogra… show more

**2019-03-10**

1903.03944 | cs.DS

We present prior robust algorithms for a large class of resource allocation
problems where requests … show more

**2019-02-03**

1902.00919 | cs.DS

We study the $K$-item knapsack problem (\ie, $1.5$-dimensional KP), which is
a generalization of the… show more

**2019-01-07**

1901.01659 | cs.IT

In this paper, we present a general framework for applying dynamic
programming (DP) to discrete memo… show more

**2016-11-19**

1611.06427 | math.OC

We propose simple polynomial-time algorithms for two linear conic feasibility
problems. For a matrix… show more

**2019-04-07**

1904.03602 | cs.LG

We consider online algorithms under both the competitive ratio criteria and
the regret minimization … show more

**2019-02-05**

1902.01874 | cs.DS

The average-case complexity of a branch-and-bound algorithms for Minimum
Dominating Set problem in r… show more

**2017-02-24**

1702.07669 | cs.DS

In recent years, significant progress has been made in explaining the
apparent hardness of improving… show more

**2019-01-19**

1901.06482 | cs.DS

We provide theoretical analyses for two algorithms that solve the regularized
optimal transport (OT)… show more