# Tagged Questions

The tag has no usage guidance.

2k views

### Super-linear time complexity lower bounds for any natural problem in NP?

Do we know any problem in NP which has a super-linear time complexity lower bound? Ideally, we would like to show that 3SAT has super-polynomial lower bounds, but I guess we're far away from that. I'd ...
1k views

154 views

139 views

57 views

122 views

### Bounding the Schur's complement of similiar matrices

Assume the following: • $L\leq K$ . • $\Gamma\in M_{K,L}$ is a $L$ rank ${ 0,1}$ matrix, without identical rows or the zeros row. • $N\in M_{K,K}$ is a diagonal matrix, whose diagonal is a ...
94 views

### Bounding a q-expansion on a bounded open subset of the complex upper-half plane

Let $f:\mathbf{H}\to \mathbf{C}$ be a holomorphic function on the complex upper-half plane and let $q:\tau\mapsto \exp(\pi i \tau)$ be the nome on $\mathbf{H}$. Suppose that there are integers $a_j$ ...
229 views

### Geometric/Analytic techniques for constructive and asymptotic bounds in the Lee metric

Slight extension of cross posting from http://cstheory.stackexchange.com/questions/7408/lee-metric-gilbert-varshamov-and-hamming-bounds-for-larger-relative-distance-rang (closed there) The following ...
265 views

### Good lower bound on matching in bipartite graph

Suppose a bipartite graph $G=(V_1 \cup V_2, E)$ is given, and one is interested in matching vertices $V_1$ to vertices $V_2$. Assume Hall's condition does not hold, so a perfect matching does not ...
125 views

### Bounds on the smallest real positive root of a polynomial

I'm trying to find upper and lower bounds of the smallest positive root of a polynomial, stated in terms of its coefficients. As I appreciate it might be a very general problem, My specific interest ...
40 views

### When does the equality hold in Dias da Silva - Hamidoune Theorem?

Let $p$ be prime number and let $A$ be a $k$-elements subset of $\mathbb{Z}/p\mathbb{Z}$. Dias da Silva - Hamidoune Theorem states that $|h^{\hat{}}A| \geq \min(p, hk -h^2 + 1)$, where $h$ is an ...
Is it possible to lower bound the minimal eigenvalue of a symmetric PSD matrix $M= \begin{pmatrix}A & C\\ C^*&B\end{pmatrix}$ from the knowledge of the eigenvalues of $M$'s Schur complement ...