Questions tagged [norms]

Norms as in the l_p norms, normed vector spaces, matrix norms and so on.

Filter by
Sorted by
Tagged with
2 votes
0 answers

Obtaining a lower bound of a matrix norm

I was wondering (on a setting where $\vec X_i \sim \mathcal{N}(\vec\mu, \mathbb{I})$ are $n$ random $d$-dimensional multivariate normal vectors with unknown mean $\vec\mu$) how I could obtain a lower ...
  • 21
0 votes
0 answers

Convex mixed linear integer programming with real nuclear norm objective and linear integer objective

Khachiyan and Porkolab in 'Integer optimization on convex semialgebraic sets' gave an $O(ld^{ O(k^4)})$ algorithm to minimize a degree $d$ form with integer coefficients of binary length at most $l$ ...
  • 12.6k
1 vote
0 answers

Minimize L2 norm by circular permutation

Imagine two lists $L$, $M$ of the same length $n$. How to find $j$ such that $\sum_{i=1}^n(L[i]-M[i+j])^2$ is minimal, where the index $i+j$ is taken modulo $n$? Of course one can take all the ...
11 votes
1 answer

Any evidence that Linial, Shraibman lower bound on quantum communication complexity is not tight?

As far as I know, the factorization norm lower bound given by Linial and Shraibman is essentially the only lower bound known for quantum communication complexity (or at least it subsumes all others). ...
0 votes
1 answer

Confusion with the proof of constraints for a particular adiabatic quantum evolution

[This might be related to one of my previous unanswered questions.] This proof belongs to the paper, How to Make the Quantum Adiabatic Algorithm Fail by Edward Farhi, Jeffrey Goldstone, Sam Gutmann ...
7 votes
1 answer

The computational complexity of spectral norm of a matrix

How hard is computing the spectral norm of a matrix? This paper says, ... it suffices to say that, except for few particular cases, the Matrix Norm problem is NP-hard. I expected that the ...
3 votes
1 answer

Why spectral norms are used for computing the complexity of adiabatic Hamiltonian?

In the context of adiabatic quantum computation the spectral norm was first used in the first adiabatic paper by Farhi et. al. when he demonstrated the relation of it to the conventional quantum ...
11 votes
0 answers

expansion with respect to p-norms for p other than 2

Suppose I have an $d$-regular expander graph with $n$ vertices, where the stochastic version of its adjacency matrix $A$ (with entries $1/d$ and zero) has second eigenvalue $\lambda$. Let $x \in {\...
17 votes
0 answers

complexity of checking if a subspace is a Euclidean section of L1

If $X$ is a linear subspace of ${\mathbb R}^n$, $X$ is high-dimensional, and for every $x\in X$ we have $(1-\epsilon) \sqrt n ||x||_2 \leq ||x||_1 \leq \sqrt n ||x||_2$ for some small $\epsilon >...
7 votes
1 answer

Stronger Lower Bounds on Nondeterministic Multiparty Communication

This is a continuation of my previous question on Lower bounds for Nondeterministic Multiparty Communication. From the answer, the $\mu^\infty$ norm lower bounds nondeterministic multiparty ...
11 votes
1 answer

Lower bounds for Nondeterministic Multiparty Communication

This is a continuation of my previous question on communication lower bounds for partial boolean functions. Can someone suggest any reference on lower bounds for nondeterministic multiparty ...
20 votes
2 answers

$\ell_p$-norm preserving Turing machines

Reading some recent threads on quantum computing (here,here, and here), make me remember an interesting question about the power of some kind of $\ell_p$-norm preserving machine. For people working ...