The Lov\'asz theta function $\theta(G)$ of a graph $G$ has attracted a lot of attention for its connection with diverse issues, such as communicating without errors and computing large cliques in graphs. Indeed this function enjoys the remarkable property of being computable in polynomial time, despite being sandwitched between clique ... more >>>

In the framework of the Blum-Shub-Smale real number model \cite{BSS}, we study the {\em algebraic complexity} of the integer linear programming problem
(ILP$_{\bf R}$) : Given a matrix $A \in {\bf R}^{m \times n}$ and vectors
$b \in {\bf R}^m$, $d \in {\bf R}^n$, decide if there is $x ... more >>>

In this paper we study the Boolean Knapsack problem (KP$_{{\bf R}}$)
$a^Tx=1$, $x \in \{0,1\}^n$ with real coefficients, in the framework
of the Blum-Shub-Smale real number computational model \cite{BSS}.
We obtain a new lower bound
$\Omega \left( n\log n\right) \cdot f(1/a_{\min})$ for the time
complexity ... more >>>