Top new questions this week:
|
|
Linear programs can be solved in polynomial time using the ellipsoid method, but in practice the Simplex method is much more efficient, and the smoothed analysis framework of Spielman and Teng ...
|
|
For a non-empty $3-SAT$ with $n\geq3$ variables and $T\geq1$ non-identical non-degenerate clauses $C_i$:
$$S=C_1 \wedge \ldots \wedge C_T$$
where a non-degenerate clause is one containing $3$ unique ...
|
|
I am wondering about the following property $\text{(P)}$ of an $NP$-complete language $L$
$\begin{align}\exists M\text{ a polytime machine}\lim_{n\to\infty}P(\text{M solves a random instance of size $...
|
|
It is well-known that various flavors of induction-recursion are consistent*. Typically, this is proven by showing that the standard model of type theory in sets can be extended to include induction-...
|
|
Let $p \geq q \in \mathbb{N}_+$, and let $L_\mathsf{max-entropy} := \{(f,k) \in \{0,1\}^{\lambda^p} \times \{0,1\}^{\log\lambda} | \lambda \in \mathbb{N} \wedge \mathrm{H}(\underbrace{C_f(\mathcal{U}_{...
|
|
Are there efficient algorithms to construct optimal evaluators of multivariable polynomials? Here, an 'evaluator' can be thought of as an algorithm or description of how to evaluate a specific ...
|
|
I came across the observation in russell & norvig's artificial intelligence book that the shortest path between two points while avoiding convex polygonal obstacles is a sequence of line segments ...
|
Greatest hits from previous weeks:
|
|
I'd like to write a survey on the applications of Topology in Computer
Science. I plan to cover the history of topological ideas in Computer
Science and also highlight a few current developments. It ...
|
|
After studying deterministic finite state automata (DFA) in undergrad, I felt they are extremely well understood. My question is whether there is something we still don't understand about them. I don'...
|
|
Which universities have a strong quantum computing curriculum, and offer some type of quantum computing/information courses/research?
The aim here is to collect a useful list for someone considering ...
|
|
In the spirit of some general discussions like this one, I'm opening this thread with the intention to gather opinions on what are the open challenges and hot topics in research on programming ...
|
|
I've come across the polynomial algorithm that solves 2SAT. I've found it boggling that 2SAT is in P where all (or many others) of the SAT instances are NP-Complete. What makes this problem different? ...
|
|
Alan Turing, one of the pioneers of (theoretical) computer science, made many seminal scientific contributions to our field, including defining Turing machines, the Church-Turing thesis, ...
|
|
I have been dabbling in HoTT and I am convinced that dependent type theory is much more suitable than set theory for proof assistants.
Now, this made me wonder - how fundamental is Type Theory ...
|
Can you answer this question?
|
|
Problem: Given a multiset S of irreducible polynomials in Z[x], say YES if S can be partitioned into two nonempty multisets A and B such that both the product of all the elements of A and the product ...
|
