Theoretical Computer Science Stack Exchange Community Digest

Top new questions this week:

Fine-Grained Hardness for Undirected Hamiltonicity

The fastest known algorithm for detecting Hamiltonian cycles in directed graphs on $n$ nodes runs in essentially $2^n\text{poly}(n)$ time. However, for undirected graphs on $n$ nodes, there is an ...

cc.complexity-theory ds.algorithms graph-algorithms hamiltonian-paths fine-grained  
asked by Naysh 5 votes

Complexity of NFA to DFA minimization with binary threshold

What is the complexity of the following problem? Given an NFA $A$ and a number $k\in \mathbb{N}$ in binary encoding, does there exist a DFA $B$ with at most $k$ states such that $L(A)=L(B)$? ...

automata-theory minimization  
asked by Shaull 4 votes

Lower bound for the OR problem

Let us have booleans $x_1, \cdots, x_n$. Any algorithm that determines $\bigvee_1^n x_i$ with probability at least $2/3$ requires $\Omega(n)$ time. It is not too difficult to prove this, but the proof ...

reference-request time-complexity lower-bounds sample-complexity  
asked by user2316602 2 votes

Does a graph resulting from the union of triangles has a particular name?

I have different simple triangle graphs. As an instance, $G_1=(V_1,E_1)=(\{1,2,3\},\{\{1,2\},\{2,3\},\{3,1\}\})$ and $G_2=(V_2,E_2)=(\{1,4,5\},\{\{1,4\},\{4,5\},\{5,1\}\})$. The union of both graphs ...

asked by jesús garcía 2 votes

exact path cover for undirected graph

In a Python plotting application, I have an undirected connected graph, not necessarily simple, that I'd like to cover with paths such that each edge is contained in exactly one path. The number of ...

graph-theory graph-algorithms  
asked by Nico Schlömer 2 votes
answered by Chandra Chekuri 3 votes

Regular Expressions that converts into unambiguous automata

Brüggemann-Klein and Wood (1992) proved that a certain kind of regular expressions, that they call “Deterministic Regular expressions”, when converted into automata using the Glushkov's Construction, ...

reference-request automata-theory regular-language regular-expressions  
asked by ricardorr 2 votes
answered by MRC 4 votes

Fastest Known Algorithm for $k$-Dimensional Matching and $k$-Exact Cover

Given a $k$-uniform hypergraph $G$ (i.e., each edge of $G$ contains precisely $k$ vertices) on $n$ vertices, the $k$-Exact Cover problem is the task of deciding if there exists $n/k$ edges in $G$ ...

cc.complexity-theory ds.algorithms graph-algorithms parameterized-complexity exp-time-algorithms  
asked by Naysh 1 vote

Greatest hits from previous weeks:

Quantum computing project ideas

I'm undergraduate computer science student and I'm currently planning for my graduation project. I need some ideas in quantum computing field. any help?

quantum-computing soft-question  
asked by Deyaa 16 votes

Problems Between P and NPC

Factoring and graph isomorphism are problems in NP that are not known to be in P nor to be NP-Complete. What are some other (sufficiently different) natural problems that share this property? ...

cc.complexity-theory np-hardness big-list np-intermediate  
asked by Lev Reyzin 134 votes
answered by Lev Reyzin 110 votes

To what extent is "advanced mathematics" needed/useful in A.I. research?

I am currently studying mathematics. However, I don't think I want to become a professional mathematician in the future. I am thinking of applying my knowledge of mathematics to do research in ...

soft-question machine-learning ai.artificial-intel  
asked by Max Muller 27 votes
answered by Andrej Bauer 64 votes

What is the actual time complexity of Gaussian elimination?

In an answer to an earlier question, I mentioned the common but false belief that “Gaussian” elimination runs in $O(n^3)$ time. While it is obvious that the algorithm uses $O(n^3)$ arithmetic ...

cc.complexity-theory ds.algorithms reference-request linear-algebra  
asked by Jeffε 86 votes
answered by Elias 41 votes

Universal Approximation Theorem — Neural Networks

I posted this earlier on MSE, but it was suggested that here may be a better place to ask. Universal approximation theorem states that "the standard multilayer feed-forward network with a single ...

approximation-algorithms ne.neural-evol na.numerical-analysis  
asked by Matt Munson 24 votes
answered by matus 27 votes

Applications of Game theory in computer science?

As a computer science student, I have been introduced to game theory, but not seen much detail on the subject. I have searched on Google and looked at some books about game theory and they provided ...

asked by S. M. Shahinul Islam 16 votes
answered by Jeffε 23 votes

What would a very simple quantum program look like?

In light of the announcement of the world's first programmable quantum photonic chip, I was wondering just what software for a computer that uses quantum entanglement would be like. One of the first ...

asked by xpda 77 votes
answered by Beef 60 votes
You're receiving this message because you subscribed to the Theoretical Computer Science community digest.
Unsubscribe from this community digest       Edit email settings       Leave feedback       Privacy
Stack Overflow

Stack Overflow, 110 William Street, 28th floor, New York, NY 10038