Most Popular
1500 questions
20
votes
1 answer
Techniques for showing non-derivability in logics and other formal proof systems
In proof systems for classical propositional logic if one want to show that a certain formula $\psi$ is not derivable one simply shows that $\neg\psi$ can be derived (although other techniques certainly are possible). Non-derivability follows…
Dave Clarke
- 16,666
- 3
- 60
- 106
20
votes
1 answer
Are there efficient general Bonferroni-style bounds known?
A classic problem in probability theory is to express the probability of an event in terms of more specific events. In the simplest case, one can say $P[A \cup B] = P[A] + P[B] - P[A \cap B]$. Let's write $AB$ for the event $A \cap B$.
There are…
András Salamon
- 19,000
- 3
- 64
- 150
20
votes
1 answer
What are the best possible time/error tradeoffs for approximate solution of linear programs?
For concreteness consider the LP for solving a two-player zero-sum game where each player has $n$ actions. Suppose each entry of the payoff matrix $A$ is at most 1 in absolute value. For simplicity let's make no sparsity assumptions.
Suppose runtime…
Warren Schudy
- 1,874
- 16
- 15
20
votes
2 answers
Why an infinite type hierarchy?
Coq, Agda, and Idris have an infinite type hierarchy (Type 1 : Type 2 : Type 3 : ...). But why not do it instead like λC, the system in the lambda cube that's closest to the calculus of constructions, which has only two sorts, $*$ and $◽$, and these…
Rui Baptista
- 303
- 1
- 5
20
votes
1 answer
Explain Gurvits's tensor-rank interpretation of Deolalikar's paper
[Note: I believe this question in no way hinges on the correctness or incorrectness of Deolalikar's paper.]
On Scott Aaronson's blog Shtetl Optimized, in the discussion about Deolalikar's recent attempt on P vs NP, Leonid Gurvits made the following…
Joshua Grochow
- 37,260
- 4
- 129
- 228
20
votes
6 answers
Network / Social network analysis visualization tools?
I was using Jung ( http://jung.sourceforge.net/ ) to visualize page rank and found it a little slow and difficult to scale it beyond 100 nodes. I was wondering what other tools people use for network / social network analysis and visualization.
steve
- 241
- 2
- 5
20
votes
2 answers
Arguments for/against Kolmogorov's conjecture about the circuit complexity of P
According to (unverified) historical account, Kolmogorov thought that every language in $\mathsf{P}$ has linear circuit complexity. (See the earlier question Kolmogorov's conjecture that $P$ has linear-size circuits.) Note that it implies…
Andras Farago
- 11,396
- 37
- 70
20
votes
2 answers
A good reference for complexity class operators?
I'm interested if there exist any good expository articles or surveys to which I can refer when I write about complexity class operators: operators which transform complexity classes by doing things such as adding quantifiers to them.
Examples of…
Niel de Beaudrap
- 8,821
- 31
- 70
20
votes
3 answers
Counting the Number of Simple Paths in Undirected Graph
How can I go about determining the number of unique simple paths within an undirected graph? Either for a certain length, or a range of acceptable lengths.
Recall that a simple path is a path with no cycles, so I'm talking about counting the number…
Ryan
- 301
- 1
- 2
- 6
20
votes
3 answers
Symbolic Execution is a case of Abstract Interpretation?
This is written in the wiki entry of Symbolic Execution, but I can't find any reference for it. Can anyone show me a pointer? Thank you.
sean
- 722
- 6
- 15
20
votes
4 answers
How can relational parametricity be motivated?
Is there some natural way to understand the essence of relational semantics for parametric polymorphism?
I have just started reading about the notion of relational parametricity, a la John Reynolds' "Types, Abstraction and Parametric Polymorphism",…
Tom Ellis
- 511
- 2
- 8
20
votes
5 answers
Unique $k$-SAT benchmarks
This question is probably on the border line between on-topic and off-topic, however I've seen similar questions here, therefore I'll ask it.
I'm implementing a Unique $k$-SAT solver, whose input is a $k$-CNF formula having at most $1$ satisfying…
Giorgio Camerani
- 6,842
- 1
- 34
- 64
20
votes
2 answers
Estimating Average in Polynomial Time
Let $f \colon \lbrace 0,1 \rbrace ^ n \to (2^{-n},1]$ be a function. We want to estimate the average of $f$; that is: $\mathbb{E}[f(n)]=2^{-n}\sum_{x\in \lbrace 0,1 \rbrace ^ n}f(x)$.
NOTE: In the OP, the range of f was [0,1]. I changed this a bit…
Sadeq Dousti
- 16,479
- 9
- 69
- 152
20
votes
4 answers
Positive topological ordering, take 3
Suppose we have an n by n matrix. Is it possible to reorder its rows and columns such that we get an upper-triangular matrix?
This question is motivated by this problem:
Positive topological ordering
The original decision problem is at least as hard…
domotorp
- 13,931
- 37
- 93
20
votes
0 answers
Identifying Reducible/Irreducible polynomials over $Z[x]$
It is well known LLL algorithm provides a fully polynomial algorithm to factor a reducible primitive polynomial over $\mathbb{Z}[x]$.
Say one only seeks to identify whether a given polynomial over $\mathbb{Z}[x]$ is reducible, then what are the best…
Turbo
- 12,812
- 1
- 19
- 68