 ## 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 ...

graph-theory ds.data-structures 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 ...

reference-request gt.game-theory 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 ...

quantum-computing 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, 110 William Street, 28th floor, New York, NY 10038

 <3