Most Popular
1500 questions
16
votes
1 answer
Number of Hamiltonian cycles on random graphs
We assume that $G\in G(n,p),p=\frac{\ln n +\ln \ln n +c(n)}{n}$.
Then the following fact is well known:
\begin{eqnarray}
Pr [G\mbox{ has a Hamiltonian cycle}]=
\begin{cases}
1 & (c(n)\rightarrow \infty) \\
0 & (c(n)\rightarrow - \infty)…
Elely
- 309
- 1
- 4
16
votes
1 answer
LogDCFL-complete problems
LogCFL is the set of all languages that are logspace reducible to a context-free language. Similarly, LogDCFL is the set of all languages that are logspace reducible to a deterministic context-free language. See this wikipedia article for some…
Shiva Kintali
- 10,578
- 41
- 74
16
votes
1 answer
Strongly Regular Graph and GI-Completeness
It is not known if graph isomorphism (GI) for strongly regular graphs (SRGs) is in P. Are there any hints that it might or might not be GI-Complete? Are there any strong consequences in such cases? (Similar to the belief that GI may not be…
DurgaDatta
- 1,281
- 6
- 18
16
votes
3 answers
Subgraph isomorphism with a tree
If we have a large (directed) graph $G$ and a smaller rooted tree $H$, what is the best known complexity for finding subgraphs of $G$ isomorphic to $H$? I am aware of results for subtree isomorphism where both $G$ and $H$ are trees and also where…
Simd
- 3,902
- 20
- 49
16
votes
3 answers
Hardness Guarantees for AES
Many public-key cryptosystems have some kind of provable security. For example, the Rabin cryptosystem is provably as hard as factoring.
I wonder whether such kind of provable security exists for secret-key cryptosystems, such as AES. If not, what…
Sadeq Dousti
- 16,479
- 9
- 69
- 152
16
votes
4 answers
Unary parametricity vs. binary parametricity
I've recently become quite interested in parametricity after seeing Bernardy and Moulin's 2012 LICS paper ( https://dl.acm.org/citation.cfm?id=2359499). In this paper, they internalize unary parametricity in a pure type system with dependent types…
Christopher Monsanto
- 1,092
- 7
- 11
16
votes
1 answer
$(2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k} $?
While reading Dick Lipton's blog, I stumbled across the following fact near the end of his Bourne Factor post:
If, for every $n$, there exists a relation of the form
$$ (2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k} $$
where $m = poly(n)$, and each of…
user834
- 2,806
- 21
- 27
16
votes
1 answer
How to compute powers of square matrices?
Suppose we are given a matrix $A \in \mathbb R^{N\times N}$, and let $m \in \mathbb N_0$. How fast can we compute the power $A^m$ of that matrix?
The next best thing in comparison to computing $m$-products is to utilize fast exponentation, that…
shuhalo
- 1,165
- 5
- 13
16
votes
0 answers
Looking for an operator on polynomials
I have a small, self-contained, math question, whose motivation is from theoretical computer science (specifically, list decoding of algebraic codes, derivative/multiplicity codes, etc).
I wonder whether someone might have an idea.
I'm looking for…
Dana Moshkovitz
- 10,979
- 1
- 50
- 77
16
votes
1 answer
(How) can you model broadcasts in the pi-calculus?
Can you model reliable broadcasts in the pi-calculus?
If so: How?
If not: Are there any similar process algebras where you can?
What I have tried:
If sender $S$ wants to send a message $y$ to all $P_1$ to $P_n$, you could…
DaveBall aka user750378
- 499
- 5
- 17
16
votes
2 answers
Characterization of problems for which sublinear time algorithms exist
I was wondering if problems for which sublinear time (in the input size) algorithms exist can be characterized as possessing specific properties. This includes sublinear time (e.g. property testing, an alternative notion of approximation for…
Massimo Cafaro
- 2,216
- 20
- 19
16
votes
6 answers
When are two algorithms said to be "similar"?
I do not work in theory, but my work requires reading (and understanding) theory papers every once in a while. Once I understand a (set of) results, I discuss these results with people I work with, most of whom do not work in theory as well. During…
Rachit
- 838
- 6
- 17
16
votes
1 answer
NP-hardness of a graph partition problem?
I'm interested in this problem: Given an undirected graph $G(E, V)$, Is there a partition of $G$ into graphs $G_1(E_1, V_1)$ and $G_2(E_2, V_2)$ such that $G_1$ and $G_2$ are isomorphic?
Here $E$ is partitioned into two disjoint sets $E_1$ and…
Mohammad Al-Turkistany
- 20,928
- 5
- 63
- 149
16
votes
1 answer
Can boolean algebra be expressed in simply typed lambda caclulus?
Boolean algebra can be expressed in untyped lambda calculus in (for example) this way.
true = \t. \f. t;
false = \t. \f. t;
not = \x. x false true;
and = \x. \y. x y false;
or = \x. \y. x true y;
Also boolean algebra can be encoded in…
Ilya Klyuchnikov
- 261
- 1
- 6
16
votes
2 answers
Has the compactness theorem for FOL been formalized in Coq/Isabelle/etc?
I've been searching for a formalization of the compactness theorem for FOL, but haven't found any. Is anyone aware of such a development or related work?
Stefan Ciobaca
- 169
- 2