All Questions
12,298
questions
6
votes
2
answers
645
views
Proof of a unique homomorphism from an initial object
What is the proof that there is only one homomorphism from an initial object to another object?
- 293
11
votes
3
answers
740
views
What evidence is there that $coRP \neq NP$?
What evidence is there that $coRP \neq NP$?
$coRP$ is the class of languages for which there exists a probabililistic Turing Machine that runs in polynomial time and always answers Yes on an input ...
- 5,026
12
votes
3
answers
679
views
$NP\cap coAM$ Languages
What other problems languages different than graph isomorphism are in $NP\cap coAM$? Can you give some references?
Update: I forgot to mention that I'm interested in languages not known to be in $...
- 3,280
19
votes
4
answers
1k
views
"All-different hypergraph coloring" - known problem?
I am interested in the following problem: Given a set X and subsets X_1, ..., X_n of X, find a coloring of the elements of X with k colors such that the elements in each X_i are all differently ...
- 1,023
29
votes
6
answers
1k
views
Well known classes of boolean formulas that require exponentially long resolution proofs
You might often find cutting plane methods, variable propagation, branch and bound, clause learning, intelligent backtracking or even handwoven human heuristics in SAT solvers. Yet for decades the ...
17
votes
4
answers
398
views
Alternate notion of complexity based on gap between brute-force and the best algorithm?
Typically, efficient algorithms have a polynomial runtime and an exponentially-large solution space. This means that the problem must be easy in two senses: first, the problem can be solved in a ...
- 2,707
6
votes
2
answers
397
views
Online learning: Perceptron updates
It seems that the perceptron updates come from some notion of primal-dual updates for convex programs. Can anyone explain how this is true or point to relevant literature?
- 69
28
votes
3
answers
1k
views
Natural problems in $NP \cap coNP$ not in $UP \cap coUP$?
Are there any natural problems in $NP \cap coNP$ that are not (known to be/thought to be) in $UP \cap coUP$?
Obviously the big one everyone knows about in $NP \cap coNP$ is the decision version of ...
- 36.3k
12
votes
3
answers
349
views
Complexity of Localization in Wireless Networks
Let distinct points $1 ... n$ sit in $\mathbb{R}^2$. We say points $i$ and $j$ are neighbors if $|i-j| < 3 \pmod{n-2}$, meaning each point is neighbors with points with indexes within $2$, ...
- 11.9k
11
votes
3
answers
613
views
Two Variants of NP
Here are two variations on the definition of NP. They (almost certainly) define distinct complexity classes, but my question is: are there natural examples of problems that fit into these classes?
(...
- 36.3k
19
votes
2
answers
585
views
Internal Regret in Online Convex Optimization
Zinkevich's "online convex optimization" ( http://www.cs.cmu.edu/~maz/publications/ICML03.pdf ) generalizes "regret minimization" learning algorithms from a linear settings to a convex setting and ...
- 9,329
34
votes
5
answers
2k
views
Evidence that PPAD is hard?
There is often-quoted philosophical justification for believing that P != NP even without proof. Other complexity classes have evidence that they are distinct, because if not, there would be "...
- 9,820
57
votes
13
answers
3k
views
For which algorithms is there a large gap between the theoretical analysis and reality?
Two ways of analyzing the efficiency of an algorithm are
to put an asymptotic upper bound on its runtime, and
to run it and collect experimental data.
I wonder if there are known cases where there ...
45
votes
10
answers
4k
views
Kolmogorov complexity applications in computational complexity
Informally speaking, Kolmogorov complexity of a string $x$ is a length of a shortest program that outputs $x$. We can define a notion of 'random string' using it ($x$ is random if $K(x) \geq 0.99 |x|$)...
16
votes
2
answers
2k
views
Is APX contained in NP?
A problem P is said to be in APX if there exists some constant c > 0 such that a polynomial-time approximation algorithm exists for P with approximation factor 1 + c.
APX contains PTAS (seen by ...
- 398
37
votes
9
answers
2k
views
Surprising Results in Complexity (Not on the Complexity Blog List)
What were the most surprising results in complexity?
I think it would be useful to have a list of unexpected/surprising results. This includes both results that were surprising and came out of ...
15
votes
5
answers
4k
views
History of recursion
Who introduced the idea of recursion?
Can someone explain where it came from and how it impacted computer science?
10
votes
2
answers
387
views
Is there a definitive reference for Turing machines with multiple oracle tapes?
Most of the literature seems to be concerned with machines with single oracles for specific problems, however there appear to be a few papers that consider machines with multiple oracles. Is there a ...
- 13.5k
30
votes
2
answers
4k
views
Are lambda calculus and combinatory logic the same?
I am currently reading "Lambda-Calculus and Combinators" by Hindley and Seldin. I'm not an expert, but have always taken an interest in lambda calculus because of involvement with functional ...
- 2,233
14
votes
3
answers
604
views
How hard is it to reduce termination to partial correctness?
If you are familiar with program verification you are likely to prefer reading the Question before the Background. If you are not familiar with program verification then you may still be able to ...
- 4,776
16
votes
2
answers
361
views
Finding small sets of integers in which every element is a sum of two others
This is a follow-up to this question on math.stackexchange.
Let us say that a non-empty set S ⊆ ℤ is self-supporting if for every a ∈ S, there exist distinct ...
- 8,871
20
votes
3
answers
424
views
Property testing in other metrics?
There is a large literature on "property testing" -- the problem of making a small number of black box queries to a function $f\colon\{0,1\}^n \to R$ to distinguish between two cases:
$f$ is a ...
- 9,820
10
votes
2
answers
245
views
Shuffling of tokens on a graph using local swaps
Let $G= (V, E)$ be a non-regular connected graph whose degree is bounded. Suppose that each node contain a unique token.
I want to uniformly shuffle the tokens amongst the graph using only local ...
- 3,043
16
votes
1
answer
448
views
Extensions of beta-theory of lambda calculus
The beta-eta-theory of the lambda-calculus is Post-complete. Can additional rules be added to extend the beta-theory of the lambda-calculus to get confluent theories other than the beta-eta theory?
...
- 4,306
41
votes
9
answers
5k
views
References for TCS proof techniques
Are there any references (online or in book form) that organize and discuss TCS theorems by proof technique? Garey and Johnson do this for the various kinds of widget constructions needed for NP-...
24
votes
2
answers
551
views
Parallel Dynamic Search
Is there a natural parallel analog to red-black trees with similar or even not-terribly-worse properties for updates while being reasonably work-efficient ?
More generally, what's the best we can do ...
- 31.9k
15
votes
1
answer
2k
views
Chernoff bound for weighted sums
Consider $X = \sum_i \lambda_i Y_i^2$, where $\lambda_i$ > 0 and $Y_i$ is distributed as a standard normal. What kind of concentration bounds can one prove on $X$, as a function of the (fixed) ...
- 445
20
votes
1
answer
433
views
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 ...
- 36.3k
8
votes
5
answers
761
views
Algorithm for inverting a bijective function.
Does there exist a generalized algorithm for finding the inverse function of an arbitrary bijective function?
In order for this algorithm to be
useful, it must eventually halt once
the correct answer ...
- 207
11
votes
1
answer
265
views
Can someone suggest a recent survey on product form Markov chains?
I'm especially interested in their use in model checking applications. I have Open, Closed and Mixed Networks of Queues with Different Classes of Customers by Baskett et al. Any other suggestions ...
- 6,974
18
votes
2
answers
831
views
Lower bounds on Gaussian complexity
Define the Gaussian complexity of an $n \times n$ matrix to be the minimal number of elementary row and column operations required to bring the matrix into upper-triangular form. This is a quantity ...
- 1,704
18
votes
1
answer
774
views
Best known joint containments for/by NP and Parity-P?
Parity-P is the set of languages recognized by a non-deterministic Turing machine which can only distinguish between an even number or odd number of "acceptance" paths (rather than a zero or non-zero ...
- 8,871
30
votes
3
answers
2k
views
Translating SAT to HornSAT
Is it possible to translate a boolean formula B into an equivalent conjunction of Horn clauses? The Wikipedia article about HornSAT seems to imply that it is, but I have not been able to chase down ...
- 1,079
16
votes
1
answer
378
views
Compared growth of the number of syntactic classes and Nerode classes.
For a language L ⊆ Σ^*, define the syntactic congruence ≡ of L as the least congruence on Σ^* that saturates L, i.e. :
u ≡ v ⇔ (∀ x, y)[xuy ∈ L ↔ xvy ∈ L].
Now define the Nerode equivalence as the ...
- 3,916
29
votes
4
answers
2k
views
Bounded-cardinality bounded-frequency set cover: hardness of approximation
Consider the minimum set cover problem with the following restrictions: each set contains at most $k$ elements and each element of the universe occurs in at most $f$ sets.
Example: the case $k = 4$ ...
- 11.4k
379
votes
92
answers
113k
views
Algorithms from the Book
Paul Erdős talked about the "Book" where God keeps the most elegant proof of each mathematical theorem. This even inspired a book (which I believe is now in its 4th edition): Proofs from the ...
32
votes
1
answer
6k
views
What's the difference between the Actor Model of Concurrency and Communicating Sequential Processes
I'm trying to wrap my head around what the real differences between the Actor Model of concurrency and Communicating Sequential Processes (CSP) model of concurrency.
So far the best that I have ...
- 423
37
votes
3
answers
2k
views
Parameterized complexity of Hitting Set in finite VC-dimension
I'm interested in the parameterized complexity of what I'll call the d-Dimensional Hitting Set problem: given a range space (i.e. a set system / hypergraph) S = (X,R) having VC-dimension at most d and ...
- 2,583
25
votes
2
answers
1k
views
Approximating the sign rank of a matrix
The sign rank of a matrix A with +1,-1 entries is the least rank (over the reals) of a matrix B which has the same sign pattern as A (i.e., $A_{ij}B_{ij}>0$ for all $i,j$). This notion is important in ...
- 1,704
29
votes
2
answers
2k
views
What are the consequences of Parity-L = P?
Parity-L is the set of languages recognized by a non-deterministic Turing machine which can only distinguish between an even number or odd number of "acceptance" paths (rather than a zero or ...
- 8,871
230
votes
60
answers
96k
views
Major unsolved problems in theoretical computer science?
Wikipedia only lists two problems under "unsolved problems in computer science":
P = NP?
The existence of one-way functions
What are other major problems that should be added to this list?
Rules:
...
22
votes
2
answers
1k
views
How does the Mulmuley-Sohoni geometric approach to producing lower bounds avoid producing natural proofs (in the Razborov-Rudich sense)?
The exact phrasing of the title is due to Anand Kulkarni (who proposed this site be created). This question was asked as an example question, but I’m insanely curious. I know very little about ...
- 2,025
30
votes
2
answers
6k
views
What would be the consequences of factoring being NP-complete?
Are there any references covering this?
- 793
15
votes
3
answers
913
views
Can it be determined if language L lies in NP?
Given a language L defined by a Turing Machine that decides it, is it possible to determine algorithmically whether L lies in NP?
- 793
14
votes
1
answer
38k
views
Is integer factorization an NP-complete problem? [duplicate]
Possible Duplicate:
What are the consequences of factoring being NP-complete?
What notable reference works have covered this?
- 793
13
votes
1
answer
346
views
Finding odd holes in circulant Paley graphs
The Paley graphs Pq are those whose vertex-set is given by the finite field GF(q), for prime powers q≡1 (mod 4), and where two vertices are adjacent if and only if they differ by a2 ...
- 8,871
12
votes
2
answers
385
views
Computational query complexity of SQ-learning
It is known that for PAC learning, there are natural concept classes (e.g. subsets of decision lists) for which there are polynomial gaps between the sample complexity needed for information theoretic ...
- 9,820
26
votes
4
answers
3k
views
DFA intersection in subquadratic space?
The intersection of two (minimal) DFAs with n states can be computed using O(n2) time and space. This is optimal in general, since the resulting (minimal) DFA may have n2 states. However, if the ...
- 962
68
votes
17
answers
4k
views
Applications of TCS to classical mathematics?
We in TCS often use powerful results and ideas from classical mathematics (algebra, topology, analysis, geometry, etc.).
What are some examples of when it has gone the other way around?
Here ...
-2
votes
2
answers
384
views
Can every non-deterministic finite automate be changed into one with only one acceptance state? [closed]
How can an arbitrary non-deterministic finite automate be converted into one with only one accept stage? If so, what is the proof that this can always be done?
- 793