Most Popular
1500 questions
27
votes
6 answers
How are real numbers specified in computation?
This may be a basic question, but I've been reading and trying to understand papers on such subjects as Nash equilibrium computation and linear degeneracy testing and have been unsure of how real numbers are specified as input. E.g., when it's…
user1338
27
votes
3 answers
Cryptography without assumptions -- seeking an overview
Suppose $P = NP$ and a fast linear-time algorithm for SAT appears tomorrow. Suddenly RSA is insecure, much of our modern communication system is broken, and we need to reconsider how to keep secrets from each other.
Question: Is there a good…
Andy Drucker
- 4,634
- 23
- 33
27
votes
0 answers
Counting Isomorphism Types of Graphs
Polya's counting theorem leads to an algorithm for counting (precisely) the number of isomorphism types of graphs with $n$ vertices in $\exp (\sqrt n )$ steps. From Polya theorem you get a formula where you need to run over all conjugacy classes of…
Gil Kalai
- 6,033
- 35
- 73
27
votes
2 answers
What is the logarithm or root operation in type-space?
I was recently reading The Two Dualities of Computation: Negative and Fractional Types. The paper expands on sum-types and product-types, giving semantics to the types a - b and a/b.
Unlike addition and multiplication, there are not one but two…
efrey
- 373
- 3
- 6
27
votes
3 answers
Does there exist an extension of regular expressions that captures the context free languages?
In many papers involving context-free grammars (CFGs), the examples of such grammars presented there often admit easy characterizations of the language they generate. For example:
$S \to a a S b$
$S \to $
generates $\{ a^{2i} b^i | i \geq…
Alex ten Brink
- 4,680
- 25
- 48
27
votes
2 answers
Complexity of factoring in number fields
What is known about the computational complexity of factoring integers in general number fields? More specifically:
Over the integers we represent integers via their binary expansions. What is the analogous representations of integers in general…
Gil Kalai
- 6,033
- 35
- 73
27
votes
3 answers
When is relaxed counting hard?
Suppose we relax the problem of counting proper colorings by counting weighted colorings as follows: every proper coloring gets weight 1 and every improper coloring gets weight $c^v$ where $c$ is some constant and $v$ is the number of edges with…
Yaroslav Bulatov
- 4,701
- 1
- 25
- 39
27
votes
1 answer
Is there a problem that is easy for cubic graphs but hard for graphs with maximum degree 3?
Cubic graphs are graphs where every vertex has degree 3. They have been extensively studied and I'm aware that several NP-hard problems remain NP-hard even restricted to subclasses of cubic graphs, but some others get easier. A superclass of cubic…
Vinicius dos Santos
- 1,868
- 12
- 21
27
votes
5 answers
Ecology and evolution through the algorithmic lens
The study of ecology and evolution is becoming increasingly more mathematical, but most of the theoretical tools seem to be coming from physics. However, in many cases the problems have a very discrete nature (see for example SLBS00) and could…
Artem Kaznatcheev
- 10,251
- 12
- 74
- 174
27
votes
2 answers
Deciding whether an NC${}^0_3$ circuit computes a permutation or not
I would like to ask about a special case of the question “Deciding if a given NC0 circuit computes a permutation” by QiCheng that has been left unanswered.
A Boolean circuit is called an NC0k circuit if each output gate syntactically depends on at…
Tsuyoshi Ito
- 16,466
- 2
- 55
- 106
27
votes
1 answer
Coloring complexity of graphs
Suppose $G$ is a graph with coloring number $d = \chi(G)$. Consider the following game between Alice and Bob. At each round, Alice picks a vertex, and Bob answers with a color in $\{1,\ldots,d-1\}$ for this vertex. The game ends when a monochromatic…
Yuval Filmus
- 14,445
- 1
- 48
- 92
27
votes
2 answers
What's the difference between ADTs, GADTs, and inductive types?
Might anyone be able to explain the difference between:
Algebraic Datatypes (which I am fairly familiar with)
Generalized Algebraic Datatypes (what makes them generalized?)
Inductive Types (e.g. Coq)
(Especially inductive types.) Thank you.
ninjagecko
- 373
- 3
- 5
27
votes
3 answers
Succinct Problems in $\mathsf{P}$
The study of Succinct representation of graphs was initiated by Galperin and Wigderson in a paper from 1983, where they prove that for many simple problems like finding a triangle in a graph, the corresponding succinct version in…
Nikhil
- 1,354
- 10
- 23
27
votes
4 answers
Major unsolved problems in distributed systems?
Inspired by this question, what are the major problems and existing solutions which needs improvement in (theoretical) distributed systems domain.
Something like membership protocols, data consistency?
zengr
- 457
- 1
- 4
- 7
26
votes
2 answers
What are the consequences of $L = \oplus L$?
Shiva Kintali has just announced a (cool!) result that graph isomorphism for bounded treewidth graphs of width $\geq 4$ is $\oplus L$-hard. Informally, my question is, "How hard is that?"
We know that nonuniformly $NL \subseteq \oplus L$, see the…
Aaron Sterling
- 6,994
- 6
- 42
- 74