All Questions

10
votes
2answers
615 views

What good notations for deterministic context-free and visibly pushdown languages exist?

Deterministic context-free languages (DCFL) and visibly pushdown languages (VPL) are both sets of formal languages between context-free languages (CFL) and regular languages (REG). Is there a readable ...
37
votes
6answers
3k views

Grid $k$-coloring without monochromatic rectangles

Update: The obstruction set (i.e. the NxM "barrier" between colorable and uncolorable grid sizes) for all monochromatic-rectangle-free 4-colorings is now known. Anyone feel up to trying 5-colorings? ;...
5
votes
2answers
912 views

Handbook of Logic in Computer Science - is it worth it?

I just found the first volume of Handbook of Logic in Computer Science in a library, but unfortunately I won't be able to use it here. It seems like a great resource, but it's insanely expensive to ...
38
votes
3answers
8k views

Is optimally solving the n×n×n Rubik's Cube NP-hard?

Consider the obvious $n\times n\times n$ generalization of the Rubik's Cube. Is it NP-hard to compute the shortest sequence of moves that solves a given scrambled cube, or is there a polynomial-time ...
1
vote
3answers
850 views

Complexity of a variant of the Mandelbrot set decision problem?

Mandelbrot set is defined using the complex equation $P_c (z)=z^2 +c$ where $c$ is a complex number Let Set $M=${$(c,k,m) |$ the sequence $P_c (0),P_c (P_c (0)), P_c (P_c (P_c (0)))...$ is unbounded ...
17
votes
1answer
602 views

Rapidly mixing Markov chains on 3-colorings of a cycle

The Glauber dynamics is a Markov chain on the colorings of a graph in which at each step one attempts to recolor a randomly chosen vertex with a random color. It does not mix for the 3-colorings of a ...
15
votes
1answer
511 views

Sensitivity of Graph Properties

In [1], Turan shows that the sensitivity (called "critical complexity" in the paper) of a graph property is strictly greater than $\lfloor {1\over 4} m \rfloor$ where $m$ is the number of vertices in ...
19
votes
1answer
775 views

Do all complexity classes have a leaf language characterization?

Leaf languages are a beautiful way to uniformly define many complexity classes. Most complexity classes are usually specified by a model of computation (e.g., deterministic/randomized TM), and a ...
8
votes
6answers
610 views

Have any generalizations of maximum weight matching been studied?

For example, one way to view maximum weight matching is that each vertex $v$ gets a utility $f_v= w(e_v)$ that equals the weight of the edge it's matched on, and zero otherwise. accordingly, a ...
19
votes
1answer
908 views

Construction of graphs where every pair of vertices have an unique common neighbor

Let $G$ be a simple graph on $n$ vertices $(n > 3)$ with no vertex of degree $n − 1$. Suppose that for any two vertices of $G$, there is a unique vertex adjacent to both of them. It is an exercise ...
-2
votes
1answer
233 views

Exception handling for flow control ? [closed]

Is it appropriate to use Exception handling for flow control of our programs ? There are some programming languages/circumstances where we can't avoid it Exception handling for flow control. Should ...
36
votes
9answers
10k views

Data for testing graph algorithms

I am looking for a source of huge data sets to test some graph algorithm implemention. Please also provide some information about the type/distribution (e.g. directed/undirected, simple/not simple, ...
8
votes
4answers
345 views

Heuristics for estimating the efficiency of Reduced Ordered Binary Decision Diagrams?

Reduced Ordered Binary Decision Diagrams (ROBDD) are an efficient data structure for representing boolean functions of multiple variables $f(x_1,x_2,...,x_n)$. I would like to get an intuition for how ...
33
votes
3answers
2k views

Given a weighted dag, is there an O(V+E) algorithm to replace each weight with the sum of its ancestor weights?

The problem, of course, is double counting. It's easy enough to do for certain classes of DAGs = a tree, or even a serial-parallel tree. The only algorithm I have found which works on general DAGs in ...
15
votes
1answer
349 views

Triangulating a Planar Polygon

Are there by now simpler algorithms/proofs for triangulating a planar polygon in linear time? What is a good resource on the state of the art of this famous problem?
5
votes
3answers
381 views

Definition for MSO2 for arbitrary structures

I am not able to find a rigorous definition of MSO_2 logic for arbitrary structures (which I can cite). MSO_2 for graphs is often used and defined, i.e. in On the Parameterised Intractability of ...
21
votes
1answer
2k views

Computational complexity of the 3-partition problem with distinct numbers

This question is related to an answer I posted in response to another question. The 3-partition problem is the following problem: Instance: Positive integers a1, …, an, where n=3m and the sum of the ...
12
votes
6answers
5k views

Quantum computing project ideas

I'm undergraduate computer science student and I'm currently planning for my graduation project. I need some ideas in quantum computing field. any help?
18
votes
1answer
1k views

Cutting-sticks puzzle

Problem: We are given a set of sticks all having integer lengths. The total sum of their lengths is n(n+1)/2. Can we break them up to get sticks of size ${1,2,\ldots,n}$ in polynomial time? ...
5
votes
1answer
275 views

Are there known “completion” operations over languages ?

Assume that $P \neq NP$ and let $NPI = NP \setminus (P \cup NPC)$. Let $L \in NPI$ be a language over an alphabet $\mathcal{A}$. Does there always exist $S \subset \mathcal{A}^*$ such as $(L \cup S) ...
5
votes
2answers
596 views

Given the following set of LISP primitives, is it possible to extend the eval function to evaluate defmacro?

In this paper McCarthy sets out the following primitives: QUOTE, CAR, CDR, ...
17
votes
2answers
597 views

MIP with efficient provers

It is well-known that the set of languages having two-prover interactive proof systems, in which the verifier runs in polynomial-time (MIP), is NEXP. But are there bounds known on the power of such ...
1
vote
2answers
420 views

Shouldn't relativisation contain consistency proof ?

My question may be stupid, but let's take the Baker-Gill-Soloway theorem as an example : There exists an oracle A such as $P^A = NP^A$ and an oracle B such as $P^B \neq NP^B$. If we take both ...
8
votes
0answers
393 views

Type inference with subtype constraints and polymorphism using Trifonov and Smith's constraint maps

Trifonov and Smith's Subtyping Constrained Types (1996) introduces constraint maps to represent consistent closed constraint sets (such maps providing sets of lower and upper bounds to each variable ...
10
votes
6answers
2k views

Do many-one reductions and Turing reductions define the same class NPC

I wonder if NPC classes defined by many-one reductions and Turing reductions are equal. Edit: Another question, are Turing reductions only collapsing C and co-C classes for some C or is there a class ...
19
votes
3answers
834 views

What algorithms are known for computing Craig interpolants?

Is there any survey of algorithms for computing interpolants? What about papers on only one algorithm? The case I'm most interested in is $A=\lnot p\land q$ and $C=q$, plus the constraint that the ...
21
votes
2answers
2k views

Bounds on $E[f(x)]$ in terms of $f(E[x])$ other than Jensen's inequality?

If $f$ is a convex function then Jensen's inequality states that $f(\textbf{E}[x]) \le \textbf{E}[f(x)]$, and mutatis mutandis when $f$ is concave. Clearly in the worst case you cannot upper bound $\...
35
votes
1answer
2k views

Multiplying n polynomials of degree 1

The problem is to compute the polynomial $(a_1 x + b_1) \times \cdots \times (a_n x + b_n)$. Assume that all coefficients fit in a machine word, i.e. can be manipulated in unit time. You can do $O(n \...
10
votes
2answers
403 views

Lower bounds for linear satisfiability problem

In SODA 1995, Jeff Erickson showed lower bounds for linear satisfiability (checking if a some $r$-subset of $n$ real numbers satisfies a linear equation on $r$ variables). The proof method uses ...
2
votes
3answers
923 views

Best bounds for the longest path optimization problem in cubic Hamiltonian graph?

optimization problem Input: cubic Hamiltonian graph feasible solution: A simple path measure to optimize: length of the simple path Design a polynomial-time algorithm that outputs the longest path ...
14
votes
3answers
1k views

Is there a complexity theory analogue of Rice's theorem in computability theory?

Rice's theorem states that every nontrivial property of the set recognized by some Turing machine is undecidable. I am looking for complexity-theoretic Rice-type theorem that tells us which ...
19
votes
4answers
2k views

How are side effects handled in semantics?

In Anthony Aaby's "Introduction to Programming Languages" section on Semantics, he makes the following observation: Much of the work in the semantics of programming languages is motivated by ...
1
vote
3answers
577 views

Major conjectures used to prove complexity lower bounds?

Complexity theory uses a large number of unproven conjectures. There are several hardness conjectures in David Johnson's NP-Completeness Column 25. What are the other major conjectures not mentioned ...
3
votes
2answers
320 views

What is the complexity of computing a compatible 3-coloring of a complete graph?

Given a complete graph whose edges are colored by 3 colors, a compatible 3-coloring is a coloring of nodes such that no edge of the graph has the same color as its end-points. The best algorithm I ...
3
votes
1answer
203 views

Sparsity of Horn satisfiability?

Is the set of satisfiable Horn formulas sparse? A sparse language contains a polynomially bounded number of srings at every length.
2
votes
1answer
337 views

What is the most efficient algorithm to sample graphs with trivial automorphism groups ?

Let us call a graph "asymmetric" if it has no nontrivial automorphism group. http://en.wikipedia.org/wiki/Asymmetric_graph I'm looking for an efficient way to compute a random asymmetric graph on a ...
9
votes
2answers
196 views

Bounding the rate of increase of the price of anarchy across equilibrium concepts

We know and love a bunch of nested classes of solution concepts: PN: Pure Nash Equilibrium MN: Mixed Nash Equilibrium CE: Correlated equilibrium CCE: Course correlated equilibrium. The relationship ...
11
votes
4answers
456 views

Dimensionality reduction with slack?

The Johnson-Lindenstrauss lemma says roughly that for any collection $S$ of $n$ points in $\mathbb{R}^d$, there exists a map $f:\mathbb{R}^d \rightarrow \mathbb{R}^k$ where $k = O(\log n/\epsilon^2)$ ...
37
votes
9answers
18k views

What is the difference between non-determinism and randomness?

I recently heard this - "A non-deterministic machine is not the same as a probabilistic machine. In crude terms, a non-deterministic machine is a probabilistic machine in which probabilities for ...
11
votes
2answers
950 views

Does Pattern Calculus represent a step forward in languages or are we just going back to LISP?

Barry Jay in his book makes some bold claims - basically by saying that, at the core of a program, everything is either atomic or composed. Then things can be easily iterated, filtered, updated, just ...
45
votes
5answers
18k views

Relationship between Turing Machine and Lambda calculus?

Is there a relationship between the Turing Machine and the Lambda calculus - or did they just happen to arise about the same time?
18
votes
3answers
2k views

Why can Lambda Calculus not represent some combinators?

This paper suggests that there are combinators (representing symbolic computations) that can not be represented by the Lambda calculus (if I understand things correctly):
4
votes
1answer
892 views

Is there any natural Karp reduction from Independent Set problem to SAT?

Is there a natural Karp reduction from Independent Set to SAT ? That is, a reduction that does not rely on the Turing machine (as the case in proof of Cook's theorem) but the combinatorial structure.
6
votes
4answers
742 views

What are the best known upper bounds and lower bounds for computing O(log n)-Clique?

Input: a graph with n nodes, Output: A clique of size $O(\log n)$, Providing links to references would be great
110
votes
17answers
7k views

Examples of the price of abstraction?

Theoretical computer science has provided some examples of "the price of abstraction." The two most prominent are for Gaussian elimination and sorting. Namely: It is known that Gaussian elimination ...
6
votes
1answer
469 views

Efficiently Samplable Distributions

What does it mean for a distribution to be efficiently samplable? This came up in the discussions about the distributions used in the recent attempted P!=NP proof. The context was that a ...
13
votes
1answer
278 views

Reference to lower bound on separator in a grid?

It is easy to verify that given the d dimensional grid of the integer points $\{1,\ldots,n\}^d$, with the regular adjacency, one can find a separator of size $n^{d-1}$ (just pick any middle hyperplane,...
32
votes
6answers
7k views

Is there a stable heap?

Is there a priority queue data structure that supports the following operations? Insert(x, p): Add a new record x with priority p StableExtractMin(): Return and delete the record with minimum ...
24
votes
2answers
822 views

Space efficient “industrial” unbalanced expanders

I am looking for unbalanced expanders that are "good" and "space-efficient". Specifically, a bipartite left-regular graph $G=(A,B,E)$, $|A|=n$, $|B|=m$, with left degree $d$ is a $(k,\epsilon)$-...
12
votes
3answers
417 views

Streaming derandomization

Stream algorithms require randomization for the most part to do anything nontrivial, and because of the small-space constraint, need PRGs that use little space. I know of two methods that have been ...

15 30 50 per page