# All Questions

10,209 questions
Filter by
Sorted by
Tagged with
2answers
2k views

### Graph encoding algorithms that you know of ?

Is there any compilation of graph encoding algorithms? I know about Prufer and Huffman encoding. But papers say, prufer is not good enough to represent Minimum Spanning Trees in the sense it may ...
1answer
677 views

### 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 ...
4answers
2k views

### Problems that can be used to show polynomial-time hardness results

When designing an algorithm for a new problem, if I can't find a polynomial time algorithm after a while, I might try to prove it is NP-hard instead. If I succeed, I've explained why I couldn't find ...
1answer
411 views

### Complexity of two perfect matchings with minimum shared edges?

Perfect Matching problem is polynomial time solvable in general graphs. Given undirected simple graph, Is the problem of finding two perfect matching with minimum shared edges between them ...
2answers
1k views

### polygonal triangulation and 3-colorability

Lets define polygonal triangulation a triangulation which has a hamiltonian cycle. It's easy to see that any polygonal triangulation is 3-colorable since any triangulation of a polygon is 3-colorable....
2answers
1k views

### Polynomial time approximation algorithms for machine scheduling: how many open problems are left?

In 1999, Petra Schuurman and Gerhard J. Woeginger published the paper "Polynomial time approximation algorithms for machine scheduling: Ten open problems". Since then, to the best of my knowledge, ...
7answers
4k views

### Truly random number generator: Turing computable?

I am seeking a definitive answer to whether or not generation of "truly random" numbers is Turing computable. I don't know how to phrase this precisely. This StackExchange question on "efficient ...
1answer
287 views

### On Defining Probabilistic/Nondeterministic Circuits

Assume that we are interested in deterministic circuits of size $f(n)$. Here, $n$ represents the number of inputs to the circuit. The standard way of defining probabilistic/nondeterministic circuits ...
3answers
1k views

### Properties of Random Directed Graphs with Fixed Out-Degree

I am interested in properties of random directed graphs with fixed out-degree $d$. I am imagining a random graph model where each vertex chooses d neighbors (say, with replacement) u.a.r. ...
1answer
399 views

### Do people look at loop nestness in boolean circuits?

While an EE undergrad I attended some lectures that presented a nice characterization of boolean circuits in terms of how many nested loops they have. In complexity, boolean circuits are often thought ...
1answer
1k views

### Reducing #SAT to #MONOTONE-2SAT

The problem #MONOTONE-2SAT is known to be #P-complete. This means that #SAT can be reduced to it. My question is: given a #SAT instance $F$, which is the transformation that converts $F$ to its ...
1answer
1k views

### Removing all but a few cycles in a graph

Let problem $S$ be defined as Given undirected graph $G$ and a set of cycles $C_1,C_2, \ldots, C_n$ in G, find minimum number of vertices that need to be deleted to remove all cycles in the ...
1answer
413 views

### Visualizing Unique Games

How would you design a picture to illustrate the unique games conjecture? This is for a "Current Events" presentation on unique games at the next AMS Joint Meeting and for the booklet that will be ...
1answer
583 views

### Using Kolmogorov complexity to establish proof complexity lower bounds?

The motivation for this question is the fact that most n-bit strings are incompressible. Intuitively, we can propose by analogy that most proofs for Tautologies are incompressible to polynomial size. ...
2answers
2k views

### Semantic vs. Syntactic Complexity Classes

In his "Computational Complexity" book, Papadimitriou writes: RP is in some sense a new and unusual kind of complexity class. Not any polynomially bounded nondeterministic Turing machine can be the ...
9answers
3k views

### Optimal greedy algorithms for NP-hard problems

Greed, for lack of a better word, is good. One of the first algorithmic paradigms taught in introductory algorithms course is the greedy approach. Greedy approach results in simple and intuitive ...
20answers
7k views

### NP-hard problems on trees

Several optimization problems that are known to be NP-hard on general graphs are trivially solvable in polynomial time (some even in linear time) when the input graph is a tree. Examples include ...
2answers
1k views

### NP-complete variants of undecidable problems?

Examples of bounded $NP$-complete variants of undecidable sets: Bounded Halting problem={ $(M, x, 1^t)$| NTM machine $M$ halts and accepts $x$ within $t$ steps} Bounded Tiling={ $(T, 1^t)$| there is ...
3answers
549 views

### 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 ...
36answers
39k views

### What videos should everybody watch?

Stanford University now has a Youtube channel, with free access to HD video of full courses on everything from dynamical systems to quantum entanglement. More conferences and workshops are ...
2answers
10k views

### What is the k-SAT problem? [closed]

First of all I am of course aware of the wikipedia article: http://en.wikipedia.org/wiki/Boolean_satisfiability_problem However I still do not understand exactly what the problem is. To demonstrate ...
1answer
940 views

### Graph Theory Fun Problem

Show that in any graph $G$ with min-degree $k$ ($k \geq 1$ duh!) you can find as its subgraph any tree on $k+1$ vertices. I have not been able to solve the question so far. However, I would like if ...
70answers
160k views

### What papers should everyone read?

This question is (inspired by)/(shamefully stolen from) a similar question at MathOverflow, but I expect the answers here will be quite different. We all have favorite papers in our own respective ...
2answers
794 views

### Universal Turing Machines in “Computational Complexity” by Papadimitriou

The first part of this question has been solved (see comments). In the book "computational complexity" by Papadimitriou, a Universal Turing Machine is given. But this machine is not concrete, in the ...
2answers
999 views

### Projective Plane of Order 12

Objective: Settle the conjecture that there is no projective plane of order 12. In 1989, using computer search on a Cray, Lam proved that no projective plane of order 10 exists. Now that God's ...
3answers
347 views

### How can I model this usage scenario mathematically?

I want to create a fairly simple mathematical model that describes usage patterns and performance trade-offs in a system. The system behaves as follows: clients periodically issue multi-cast packets ...
1answer
2k views

### How do I formally describe a rooted, directed, acyclic graph?

I need a formalism to describe the following requirements: I have a graph comprised of nodes and transitions between nodes Nodes maybe one of three types, all are sub-classes of a base abstract node ...
6answers
2k views

### Introduction to spectral graph theory

What are the basic references? Are there any good, high-level surveys of SGT and its applications to CS in general and machine learning more specifically?
1answer
423 views

### Is this problem mappable to 3SAT or is it weaker than 3SAT?

Consider a variant of a satisifiability problem. Given n dimensions (n >= 3, n < 10,000 think of n as large but finite) The range of each dimension is either an interval over the integers or an ...
2answers
505 views

1answer
882 views

### Integer relation detection for Subset Sum or NPP?

Is there a way to encode an instance of Subset Sum or the Number Partition Problem so that a (small) solution to an integer relation yields an answer? If not definitely, then in some probabilistic ...

15 30 50 per page