All Questions

9,939 questions
15 views

$NP$ completeness of Hamiltonicity of cubic polyhedral graphs with bounded faced degree?

Let $\mathscr{C}_d$ be the class of cubic 3-connected simple plane graphs, with face degree bounded by $d$. Is there any $d$ such that Hamiltonian cycle is $NP$ complete on $\mathscr{C}_d$? If so, ...
16 views

Exponential blowup of state in Deterministic Finite Tree Automata

This is an example from Tree Automata: Techniques and Applications by Hubert Comon, Max Dauchet, Remi Gilleron, Florent Jacquemard, Denis Lugiez, Christof Loding, Sophie Tison and Marc Tommasi ...
16 views

Packing low-depth spanning trees in a bi-clique

A bi-clique of order $n$ (denoted by $B_n$) is a complete bipartite graph with each side having $n$ nodes. A packing of spanning trees of $B_n$ is a collection of edge-disjoint spanning trees of $B_n$....
7 views

27 views

141 views

What is the hardest instance for the group isomorphism problem?

Two groups $(G,\cdot)$ and $(H, \times)$ are said to be isomorphic iff there exists a homomorphism from $G$ to $H$ which is bijective. The group isomorphism problem is as follows: given two groups, ...
36 views

Enumerate over all halting Turing Machines? [on hold]

I understand that it is possible to enumerate over all Turing Machines. My understanding of how this works is by fixing an encoding of natural numbers to TM descriptions, and then enumerating the ...
31 views

Problems rephrased as quadratic unconstrained binary optimization

I was impressed when i came across Quadratic unconstrained binary optimization (QUBO) recently, and saw how one can rephrase many combinatorial problems into questions about optima of binary functions....
43 views

First-order multi arity functions in dependent type?

(cross posted from Reddit https://www.reddit.com/r/dependent_types/comments/b1ts8b/firstorder_multi_arity_functions_in_dependent_type/? Take Agda for example, functions of multi arity is "encoded" as ...
43 views

Inexpressibility of Second order

In finite model theory, Ehrenfeucht-Fraïssé games gives us tools to prove inexpressibility results for FOL. Pebble games do the same for infinitary logic with finitely many variables. Do we have such ...
92 views

An axiom for John Major's Equality

In the the standard library of Coq, there is the axiom: Axiom JMeq_eq : forall (A:Type) (x y:A), JMeq x y -> x = y. Why isn't it provable? Can it be reduced ...
99 views

How is SDP an extension of spectral algorithms?

In one of his lectures, Uri Feige described semidefinite programming (SDP) as ... an algorithmic technique that extends both linear programming and spectral algorithms. I know the basic ...
38 views

Why does Chaos Improve Evolutionary Algorithms?

I have presented an evolutionary algorithm using chaos theory (chaotic numbers) to solve an optimization problem. The results of the experiments show that this algorithm is much better than the same ...
8 views

Fastest way to read large wav files (or any large file) to python [migrated]

So i'm working on a school project where i have to work with large wav files ( > 250Mgb), and i wonder, why when i read such a file to audacity software, it take about 40 sec to be read and ploted, ...
37 views

Corruption bound in communication complexity

The corruption bound is referenced in this paper by Sherstov. Theorem 6 (Corruption bound): Let $f : X × Y \rightarrow \{0, 1\}$ be a given function and $\alpha, \beta \ge 0$ be given parameters. ...
20 views

How to calculate the number of variables and total number of clauses in a SAT problem for a specific domain size? [on hold]

I have a set of propositional clauses generated by clausification of a set of first-order logic axioms containing 2 binary predicates (p and c). Assume P is the number of distinct predicates in the ...
100 views

Intuitive explanation behind Goemans-Williamson randomized rounding

A very simple randomized cut algorithm achieves $1/2$ of the optimal value: just choose each vertex to be in the cut with probability $1/2$, independently. Goemans-Williamson does something more ...
73 views

Compressing grammars by introducing ambiguity and left-recursion

This is a reference request. What is known about the following questions? Problem: Given a grammar $G$ (for example context-free) with language $L$ we can introduce a new grammar $G'$ which also ...
73 views

Universality exists? [closed]

Do universal computers exist?
54 views

74 views

Enumerate all allocations of points in a simplex

Consider the standard 2-simplex $\{(x,y)~|~x+y=1~;~ x,y\geq 0\}$. Given a set $M$ of $m$ points in this simplex, we allocate each point either to X or to Y by the following process: Fix two positive ...
71 views

3 dimensional matching shortest solution NP-hard?

We have array of arbitrary number of elements - 3d vectors with positive integers components - for example ...
22 views

Learnability proof for lower dimensional joint vector space

For a multi-label learning problem, if I have a mapping function which takes in documents and labels and maps them to a lower dimensional joint vector space, how do I prove that this space is ...
55 views

Probability of detecting small bias of a die in the low confidence regime / balls and bins

We are given a biased $m$-sided die: one of the sides has probability $\frac{1}{m} + \gamma$ and all the rest have probability $\frac{1}{m} - \frac{\gamma}{m-1}$ each. The goal is to figure out which ...
33 views

Minimising the maximum distance to the centre of a cluster of points

I have a set of points $C_i$ on a two dimensional plane and I want to find a point $P$ such that the maximum distance from $P$ to any of the points is minimised, i.e. minimise(max($||P-C_i||$)). I've ...
27 views

Power of one step transition of a QTM

So in defining a quantum Turing machine, we have transition as below: $$\delta:Q\times \Gamma\rightarrow \mathbb{C'}^{Q\times \Gamma\times\{L,R,0\}}$$ Where $\mathbb{C}'\subseteq\mathbb{C}$ is a ...
94 views

When is a problem specified on a TM contained in non-uniform classes such as P/poly? [on hold]

In this paper by Gottesman and Irani: https://arxiv.org/abs/0905.2419 , they prove NEXP-hardness of tiling an $N\times N$ grid. They do so by encoding a TM in the tiles making up the grid. However, ...
Let's try to generalize the $VC$-dimension (of the class of hyperplanes) to include accuracy/error. Let $S$ be a set of points in $R^d$ and $t$ in $[0,1]$. We say that the class of hyperplanes $t$-...