# All Questions

9,986 questions
79 views

### Is there a universal gate set for classical probabilistic computing?

We know that NAND gates are universal for deterministic classical circuits, Toffoli gates are universal for reversible deterministic classical circuits, and Clifford+T is universal for quantum ...
103 views

### Optimal bounds for $k$-wise non-uniform random bits

Let $k\geq 2$ be a constant (in my case, $k=4$), and $n,t \geq 0$ be integers such that $2^t \leq n$. What is the smallest sample space (or, equivalent, how many true independent random bits are ...
137 views

### Take a NEXP-complete problem and then have the input in unary. Why is this not NP-complete?

It is known that if any unary language is NP-complete, then P=NP. Suppose we take a NEXP-complete language with input $x$ in binary and witness $y\in\{0,1\}^{2^{poly(|x|)}}$ such that the verifying ...
200 views

### Subset sum problem with at most one solution for any target

This question was originally asked on CS.se. A little bit of initial discussion can be found in the comments there. We first consider the search version of the subset sum problem: Given a set $S$ of ...
136 views

### Why is the Toffoli Gate named after Toffoli?

I was reading the following paper: Rolf Landauer, Irreversibility and Heat Generation in the Computing Process, IBM Journal of Research and Development, Volume 5, Issue 3, July 1961. On page 4, ...
174 views

69 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?
76 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 65 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 59 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 119 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 101 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 37 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 34 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 197 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 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 189 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 ...