ML p(r)ior | A Linearithmic Time Algorithm for a Shortest Vector Problem in Compute-and-Forward Design

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.
PDF

Highlights - Most important sentences from the article

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

Related Articles

2013-06-02

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2019-05-05

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

Highlights - Most important sentences from the article

2015-06-29
1506.08536 | stat.ML

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

Highlights - Most important sentences from the article

2018-02-25
1802.09104 | cs.DS

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

Highlights - Most important sentences from the article

2018-09-25
1809.09698 | cs.DS

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

Highlights - Most important sentences from the article

2019-01-24

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

Highlights - Most important sentences from the article

2019-03-10

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2016-11-19

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

Highlights - Most important sentences from the article

2019-04-07
1904.03602 | cs.LG

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

Highlights - Most important sentences from the article

2019-02-05

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

Highlights - Most important sentences from the article

2017-02-24

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

Highlights - Most important sentences from the article

2019-01-19
1901.06482 | cs.DS

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

Highlights - Most important sentences from the article