# All Questions

9,939 questions
20 views

65 views

### Reference request: strong polynomial-time for LP

A follow-up of sorts on this question: Complexity of finding a consistent hyperplane What is a good survey of partial results on the strong poly-time status of the general LP problem?
29 views

### How to estimate the maximum and minimum eigenvalue of random walk Laplacian graph?

I'm wondering how to estimate the maximum and minimum eigenvalues of random walk Laplacian graph ! The normalized version of graph Laplacian allow to get eigenvalues in range [0,2]. Thank you
63 views

Problem I do not understand why larger $p$ will give a larger covering number. Since when $p\geq q$, the corresponding hypercube is also larger (by $\| x \| _ { q } \leq n ^ { ( 1 / q - 1 / p ) } \|... 1answer 64 views ### Question on deduction that a certain problem requires exponential space My question concern's a statement from the classic paper The equivalence problem for regular expressions with squaring requires exponential space. Regular expressions with squaring are like ordinary ... 0answers 54 views ### Rearranging angles of a convex polyline to make it closed Let {$\alpha_1, \alpha_2, ... ,\alpha_n$} be a string of n positive reals summing up to 2$\pi$. We inductively construct the following 2D polyline, denoting with$R[\alpha]$the clockwise rotation by ... 1answer 116 views ### Generalizations of linear programming Linear problems can be solved in polynomial time. So can semidefinite programs and, presumably, many other useful classes of optimization programs. Is there a survey/lecture notes describing ... 1answer 94 views ### Dependent C-style types with subtyping rule I'm looking for previous work regarding an extension of a C-style type system in which types may have constraints and have a defined subtyping rule. In particular, I'm interested in defining algebra-... 1answer 36 views ### Does fixed hyperparameters perform well regardless the number of training examples? I'm new in this community and I don't know whether my question is proper for this community. I will delete this post if it is not proper. I'm interested in deep learning network models and have a ... 0answers 33 views ### Time complexity of finding a point of infinite order on a rank 1 elliptic curve over Q As an outsider, it sounds like a lot of progress has been made on understanding rank 1 elliptic curves over Q. Much of the BSD conjecture is known for rank 1, and Heegner points provide a way in ... 1answer 189 views ### Depth reduction for Boolean circuits This result by Tavenas, Koiran and others show that any polynomial computed by a circuit of size$s$is computed by a depth-4 homogenous circuit of size$s^{\sqrt{d}}$. Are there any similar results ... 0answers 49 views ### Anagrams, Prime numbers and prime coding [closed] I am from math.stackexchange, here is my original post. https://math.stackexchange.com/questions/2354828/anagrams-prime-numbers-and-prime-number-coding The only comment I received was too technical ... 0answers 14 views ### Spidergon Networks-on-Chips What do you guys think about Spidergon NoC ? Why mod 4 ? And do you guys understand how the shortest path routing algorithm depends on the value of RelAd ? The original paper : Spidergon: a novel on-... 0answers 31 views ### total language lazy + eager term name I have been reading a lot of works related to total functional programming and I learned that eager and lazy evaluation can be combined in such a language. However I have yet to learn of a general ... 0answers 65 views ### A question on the Kolmogorov Complexity of Human I/O behaviour Note: From my Twitter poll I managed to get feedback from AI researchers and neuroscientists so far and I think it would be interesting to get input from theoretical computer scientists on this ... 1answer 180 views ### How to tell if an effect is algebraic? I've read Bauer's What is algebraic about algebraic effects and handlers? and he talks about IO being an algebraic effect, even though it doesn't have any equations. In other papers on algebraic ... 0answers 69 views ### LSH Probabilistic guarantees A family$H$is$(r,cr,p_1,p_2)$-sensitive if for all$x,y \in \mathbb{R}^d$we have:$\lVert x-y\rVert <r\quad \Rightarrow\quad \Pr[h(x)=h(y)] \geq p_1$, and$\lVert x-y\rVert > cr \quad \...
A (n, m, k)-bipartite graph is a bipartite graphs with: independent sets of size $\{n, m\}$ a total of $k \geq n+m-1$ edges We want an algorithm to generate a (n, m, k)-bipartite selected uniformly ...