All Questions

Filter by
Sorted by
Tagged with
5 votes
0 answers
210 views

Possible connection between complexity of Factorials and the density of solution of a set of Diophantine equations

Let $P(x) \in \mathbb Z[x]$ of degree $\ge 2$ and $S = \{(x,n) \in \mathbb Z^{2}:P(x)=n!\}$. It is known: $(a)$ $|S| < \infty$ under the $abc$ conjecture. $(b)$ Density of $S$ in $\mathbb Z$ is $...
Turbo's user avatar
  • 12.9k
9 votes
2 answers
987 views

Quantum PCP and hardness of simulating of Hamiltonians

I have a few questions about Quantum PCP conjecture: What is the statement of the quantum PCP conjecture? What implications would Quantum PCP theorem have for simulating of Hamiltonians? Is it ...
user avatar
22 votes
1 answer
871 views

How much computational power fits into a cubic centimeter?

This question is a followup on the question about DNA algorithms asked by Aadita Mehra. In comments there, Joe Fitzsimmons said, in part: [T]he radius of the system must scale proportionately to ...
Aaron Sterling's user avatar
3 votes
0 answers
103 views

A question on factorials

$P(x) = n!$ where $P(x) \in \mathbb Z[x]$ has finitely many $(x,n) \in \mathbb Z^{2}$ assuming $abc$ conjecture. Consider the following variant: Given $c,d,r,s,k \in \mathbb Z$ and $P(x) = n!$ where ...
Turbo's user avatar
  • 12.9k
6 votes
1 answer
441 views

Maximum ball transform

Consider a finite uniform grid $G$ in three dimensions with a function $f$ mapping integer grid positions $p$ to a boolean value $f(p)$ (i.e., a black/white volume image.) A ball in $f$ is a set of ...
Rumen's user avatar
  • 91
5 votes
3 answers
378 views

Calculating a fast matrix vector product between vector of reals and a 0-1 matrix

Given: some vector $R=(r_1...r_l)$ - real numbers, and a set of distinct vectors with $0$ or $1$ coordinates $$\begin{array}{c} V_1=(c_{1,1} ... c_{1,l}),\\ V_2=(c_{2,1} ... c_{2,l}),\\ .....\...
user avatar
10 votes
1 answer
502 views

Finite One-Way Permutation with Infinite Domain

Let $\pi \colon \{0,1\}^* \to \{0,1\}^*$ be a permutation. Note that while $\pi$ acts on an infinite domain, its description might be finite. By description, I mean a program that describes $\pi$'s ...
Sadeq Dousti's user avatar
  • 16.5k
5 votes
1 answer
2k views

Simulating Turing machines (output included) with circuits

A Turing machine with input alphabet {0,1} computes a partial or total function $f \colon \{0,1\}^* \to \{0,1\}^*$. Is it possible to construct a circuit family $\{C_n\}$ such that for an input $x$ of ...
echoone's user avatar
  • 223
3 votes
2 answers
1k views

An explanation of Whirlpool C implementation - or the general algorithm

Note: Question originally asked on StackOverflow - was directed here Anyone got a tutorial on the designers concept implementation of Whirlpool in C, or the Whirlpool algorithm in general? I find the ...
Oystein's user avatar
  • 133
1 vote
0 answers
291 views

Identifying sub graph in connected digraph [closed]

Hello I need some idea for a quick algorithm. Given a strongly connected undirected graph G with weighted edges, I would like to identify induced sub graph(it is required to be weakly connected) of ...
YAKOVM's user avatar
  • 189
14 votes
0 answers
325 views

Linear PRAM vs Arithmetic Linear PRAM

A linear PRAM model is a PRAM model without bit operations and at least one operand of the $\times$ instruction is a constant. If in addition we require that the running time does not depend on the ...
Shiva Kintali's user avatar
10 votes
2 answers
566 views

Complexity of hidden polygon puzzle on square grids?

Hiroimono is a popular $NP$-complete puzzle. I'm interested in the computational complexity of a related puzzle. The problem is: Input: Given a set of points on on a $n$x$n$ square grid and integer $k$...
Mohammad Al-Turkistany's user avatar
24 votes
2 answers
1k views

What is the best exact algorithm to compute the core of a graph?

A graph H is a core if any homomorphism from H to itself is a bijection. A subgraph H of G is a core of G if H is a core and there is a homomorphism from G to H. http://en.wikipedia.org/wiki/Core_%...
Regularity's user avatar
5 votes
1 answer
394 views

Solving "all-marginals" problem for independent sets on grid

Suppose I have a distribution over independent sets on an $n\times n$ grid where the probability of independent set occupying nodes $(i_1,j_1),\ldots,(i_k,j_k)$ is proportional to $\lambda_{i_1,j_1}\...
Yaroslav Bulatov's user avatar
22 votes
2 answers
899 views

Can the cost of GC be neglected when analyzing the running time of worst-case data structures specified in a garbage-collected programming language?

I just realized that I have been assuming the answer to my question is "yes" but I don't have a good reason. I imagine that maybe there is a garbage collector that provably introduces only $O(1)$ ...
Maverick Woo's user avatar
23 votes
4 answers
2k views

Social choice, arrow's theorem and open problems ?

Last few months I started to lecture myself on social choice, arrow's theorem and related results. After reading about the seminal results, I asked myself about what happens with partial order ...
Sylvain Peyronnet's user avatar
35 votes
3 answers
3k views

complexity of greatest common divisor (gcd)

Consider the following counting problem (or the associated decision problem): Given two positive integers encoded in binary, compute their greatest common divisor (gcd). What is the smallest ...
Felix Breuer's user avatar
14 votes
2 answers
2k views

Justification for the Hungarian method (Kuhn-Munkres)

I wrote an implementation of the Kuhn-Munkres algorithm for the minimum-weight bipartite perfect matching problem based on lecture notes I found here and there on the web. It works really well, even ...
user avatar
21 votes
4 answers
2k views

DNA-algorithms and NP-completeness

What is the relationship between DNA-algorithms and the complexity classes defined using Turing machines? What do the complexity measures like time and space correspond to in DNA-algorithms? Can they ...
Aadita Mehra's user avatar
20 votes
3 answers
1k views

Survey on algorithms/complexity of linear algebra

I am looking for a good survey on algorithms and complexity of linear algebra (operations like rank, inverse, eigenvalues, ... for Boolean, $\mathbb{F}_p$, and integers/rationals matrices) with ...
Kaveh's user avatar
  • 21.6k
14 votes
1 answer
1k views

Computational Power of Neural Networks?

Let's say we have a single-layer feed forward neural network with k inputs and one output. It calculates a function from $\lbrace 0,1\rbrace ^{n}\rightarrow\lbrace 0,1\rbrace $, it's fairly easy to ...
gabgoh's user avatar
  • 1,548
2 votes
1 answer
122 views

Determinants and bilinear forms

If one calculates the product of diagonal elements of the $U$ matrix in a $LUP$ factorization of a given matrix $A$, one can calculate the determinant of $A$. Also it is known that $LUP$ factorization ...
Turbo's user avatar
  • 12.9k
2 votes
2 answers
325 views

Generate a sequence of numbers

I want to generate an infinite sequence of numbers between $0$ and $9$ such that the percentage of number $i$ appearing in the sequence is $p_i$. Let $p=\lbrace p_0,...,p_9\rbrace$. Another agent $B$ ...
user avatar
20 votes
0 answers
502 views

Model-checking for three-variable logics and restricted structures

Denote the $k$-variable fragment of logic $L$ by $L^{(k)}$. The model-checking problem for a logic $L$ with respect to a class of structures $C$, denoted $MC(L,C)$, is the decision problem $MC(L,C)...
András Salamon's user avatar
10 votes
1 answer
243 views

Relaxing $\ell_0$ constraints in an optimization

I have a feasibility question that can be framed as follows. I'm given a point $p$ in a $d$-dimensional vector space, and I want to find the closest point $q$ to $p$ that satisfies a set of "$\ell_0$ ...
Suresh Venkat's user avatar
4 votes
4 answers
2k views

Algorithm for finding similar images

If you go to FFFFOUND! and click on some image you will notice that on the new page, under the image, there is a section called "You may like these images." which suggests 10 images that look similar ...
please delete me's user avatar
21 votes
4 answers
977 views

Examples of hardness phase transitions

Suppose we have a problem parameterized by a real-valued parameter p which is "easy" to solve when $p=p_0$ and "hard" when $p=p_1$ for some values $p_0$, $p_1$. One example is counting spin ...
Yaroslav Bulatov's user avatar
61 votes
14 answers
4k views

Information Theory used to prove neat combinatorial statements?

What's your favorite examples where information theory is used to prove a neat combinatorial statement in a simple way ? Some examples I can think of are related to lower bounds for locally decodable ...
0 votes
1 answer
692 views

How to compute ROOK Polynomials for NxM Matrices [closed]

How to compute ROOK Polynomials for NxM Matrices for k objects ?
Tony's user avatar
  • 103
3 votes
1 answer
282 views

compressing rarely used space

So an idea I've had bouncing around for a while goes like this: suppose we have some TM that runs in possibly exponential time, and thus can use possibly exponential space. But let's say that it ...
ahh's user avatar
  • 223
39 votes
2 answers
1k views

How many distinct colors are needed to lower-bound the choosability of a graph?

A graph is $k$-choosable (also known as $k$-list-colorable) if, for every function $f$ that maps vertices to sets of $k$ colors, there is a color assignment $c$ such that, for all vertices $v$, $c(v)\...
David Eppstein's user avatar
41 votes
6 answers
3k views

Which model of computation is "the best"?

In 1937 Turing described a Turing machine. Since then many models of computation have been decribed in attempt to find a model which is like a real computer but still simple enough to design and ...
Tatiana Starikovskaya's user avatar
18 votes
4 answers
984 views

If P = BQP, does this imply that PSPACE (= IP) = AM?

Recently, Watrous et al proved that QIP(3) = PSPACE a remarkable result. This was a surprising result to myself to say the least and it set me off thinking... I wondered what if Quantum Computers ...
Zelah 02's user avatar
  • 1,578
2 votes
1 answer
530 views

upper bound on the size of a DFA for A|B given the DFAs for A and B?

Given RegEx A and B where the size of the compiled DFAs are m and ...
BCS's user avatar
  • 151
9 votes
1 answer
478 views

Does There exist a particular PSPACE Complete Problem which has a FPTAS algorithm?

It is well known that the NP-Complete Problem called Subset Sum has a FPTAS. I was wondering if there existed an PSPACE Complete problem which also has a FPTAS? Thanks in advance.
Zelah 02's user avatar
  • 1,578
-1 votes
4 answers
3k views

Interesting variation to the subset sum problem

An interesting variation of the subset sum problem was presented to me by a friend from work: Given a set S of positive integers, of size n, and integers a and K, is there a subset R (of the set S) ...
ntsue's user avatar
  • 109
20 votes
0 answers
812 views

Weighted Hamming distance

Basically my question is, what kind of geometry do we get if we use a "weighted" Hamming distance. This is not necessarily Theoretical Computer Science but I think similar things come up ...
Bjørn Kjos-Hanssen's user avatar
2 votes
1 answer
6k views

How does one augment AdaBoost with cross-validation?

How does one augment AdaBoost with cross-validation?
Neil G's user avatar
  • 141
0 votes
1 answer
1k views

Question about Mapping Reductions (Clarify Example)

I cannot for the life of me wrap my head around these reductions. Specifically, the example I'm wrestling with: ...
prelic's user avatar
  • 103
6 votes
1 answer
683 views

Lower bound on independence number in terms of clique number and order of graph

In the paper "On Multi-dimensional Packing Problems" by Chekuri and Khanna there is the following lemma: Lemma 4.3.(p. 191 of the paper) Let $G$ be a graph on $n$ vertices with $\omega(G) ≤ k$. Then $...
Oleksandr Bondarenko's user avatar
46 votes
8 answers
21k views

Complexity of Finding the Eigendecomposition of a Matrix

My question is simple: What is the worst-case running time of the best known algorithm for computing an eigendecomposition of an $n \times n$ matrix? Does eigendecomposition reduce to matrix ...
Lev Reyzin's user avatar
  • 12k
33 votes
9 answers
2k views

Randomized algorithm that "looks" deterministic?

Is there an interesting example of a randomized algorithm for a search problem that always outputs the same (correct) answer, regardless of its internal randomness, but which exploits the randomness ...
arnab's user avatar
  • 7,000
10 votes
1 answer
5k views

LP formulation for if-conditions

I have the following LP: /* Objective function */ min: 1 w + 2 x + 0.5 y + z; /* Variable bounds */ w + x <= T1; w + y = U1; x + z = U2; T1 = 50; U1 = 70; U2 = 25; In this case U1 + U2 > T1 and ...
Bala's user avatar
  • 211
17 votes
1 answer
2k views

Meaning of P=NP? depends on space-time geometry ?

This question is about Page 125 of the book "Cellular automata in hyperbolic spaces: Volume 2" By Maurice Margenstern, Publisher Archives contemporaines, 2008. http://books.google.com/books?id=...
Roy Maclean's user avatar
-2 votes
1 answer
237 views

Approach to implementing an STM for a student [closed]

A student has implemented a scheme interpreter in scheme and then in C, and a scheme compiler in scheme. That student is now interested in implementing a STM (Software Transactional Memory) system ...
hawkeye's user avatar
  • 2,581
15 votes
3 answers
2k views

Complexity of edge coloring in planar graphs

3-edge coloring of cubic graphs is $NP$-complete. Four Color Theorem is equivalent to "Every cubic planar bridgeless graphs is 3-edge colorable". What is the complexity of 3-edge coloring of cubic ...
Mohammad Al-Turkistany's user avatar
11 votes
1 answer
266 views

What algorithms/reading matter would you recommend on resolving transactions / read-write locks?

A simplified classical database transaction can be viewed as: reading M items performing some calculation based on those reads writing some N results based on these calculations, which may include ...
Nick Fortescue's user avatar
10 votes
4 answers
769 views

How to know if X and Y have coauthored?

Is there any tool where one can figure out if two people have coauthored or not? Like the tool where one can figure out somebody's Erdos _number_ .
user avatar
93 votes
14 answers
21k views

What kind of mathematical background is needed for complexity theory?

I am currently an undergraduate student, bound to graduate this year. After graduation, I am considering to work towards a TCS master/PhD. I have begun wondering what fields of mathematics are ...
chazisop's user avatar
  • 3,796
15 votes
1 answer
463 views

Graph decompositions for combining "local" functions of vertex labelings

Suppose we want to find $$\sum_x \prod_{ij \in E} f(x_i,x_j)$$ or $$\max_x \prod_{ij \in E} f(x_i,x_j)$$ Where max or sum is taken over all labelings of $V$, product is taken over all edges $E$ for a ...
Yaroslav Bulatov's user avatar

15 30 50 per page
1
243 244
245
246 247
258