All Questions

4 views

Lower Bound on Zero-order Regret

The upper bound on the zero-order regret is known as $O(\sqrt{T\ln n})$. I was wondering if there is also a positive lower bound on this? I guess this is true, since I could find it in Exercise 5 in ...
2 views

Which are the rewriting systems corresponding to the levels of the computatational hierarchy?

The lambda calculus is a rewriting system and Turing complete. Which are the rewriting systems corresponding to the other levels of the Chomsky hierarchy? E.g. what is the functionally computing ...
7 views

Expected number of Support Vector's in Vapnik's book

I would like to ask this community the question in http://mathoverflow.net/questions/150747/expected-number-of-support-vectors-in-vapniks-book: In Vapnik's book "Statistical Learning Theory", ...
13 views

From k-local Hamiltonian to CNF expression

Is there a general algorithm or convention for converting a given k-local Hamiltonian into a CNF form? What about if the CNF form needs to be with smallest number of variables? A sample k-local ...
18 views

I wanted to know if there is any investigation and development being carried to try and create frameworks for formal verification of programs, but outside functional programming ones (based on lambda ...
23 views

Geodesic loop related problem

I was reading a textbook, and ran into the question with the image below. Now I was very interested if someone here can explain and help me solve it. Thank you.
75 views

Subgraph containing all nodes and edges that are part of length-limited simple s-t paths in an undirected graph

Note: Quite similar to my previously posted question. This time however, the graph is undirected. Given An undirected graph $G$ with no multiple-edges or loops A source vertex $s$ A target vertex ...
17 views

how to intuitively think while Designing an NFA [on hold]

I don't know whether this question is right to be asked, But I definitely felt that it should be asked. I did see a lot of nice and informative questions, articles on inter-net and on StackOverflow ...
71 views

Deterministic dynamic dictionary on a small universe

We want to maintain a dictionary of $m$ elements with insert/delete and lookup in the word RAM model. Assume $m=O(n)$ at all times, so there can't be too many inserts without deletions. The universe ...
23 views

Reducing from a Turing machine that recognizes is regular to the halting problem

I'm trying to understand reduction, this is from my textbook and is not a homework problem or even any exercise, just trying to understand an example they present. This is the reduction they give: ...
67 views

Finding balanced disjoint cycles in bridgeless cubic graphs

Petersen's theorem states that A bridgeless cubic graph contains a perfect matching (1-factor). Motivated by this question, Complexity of finding 2 vertex-disjoint (|V|/2)-cycles in cubic graphs? I am ...
34 views

What is the fastest algorithm for Weighted Planar Max Cut

In 1990's, the paper Unifying Maximum Cut and Minimum Cut of a Planar Graph described an $O(n^{3/2}\log n)$-time algorithm for Weighted Planar Max Cut, a landmark in the field. Recently, this paper ...
63 views

How is the complexity of PCA $O(\min(p^3,n^3))$?

I've been reading a paper on Sparse PCA, which is: http://stats.stanford.edu/~imj/WEBLIST/AsYetUnpub/sparse.pdf And it states that, if you have $n$ data points, each represented with $p$ features, ...
154 views

what can be solved with semidefinite programming that can't be solved with linear programs?

I'm familiar with linear programs in that they can solve problems with linear objective functions and linear constraints. But what can semidefinite programming solve that linear programs can't? I ...
63 views

What are standard techniques for formal program verification?

What are considered the standard techniques for formal verification? A program verification course at my university presented the problem of verification as modeling a language's semantics as a ...
44 views

Topological sort with constraints on the relative difference between the vertex labels

A topological sort of a graph $G(V,E)$ consisting of $n$ vertices assigns a label $L(v_x)$ to a vertex $v_x$ where $L$ is defined as $L:V \rightarrow \{1,\dots,n\}$. Let additional constraints over ...
21 views

Is there a relation between $l_p$-norms of functions with same Fourier spectra but w.r.t different measures on the Hamming cube?

Informally, I want to ask if two functions $f$ and $g$ on the Hamming cube have the same Fourier spectra but w.r.t different measure and basis, then is $||f||_p$ related to $||g||_p$? (Where each ...
277 views

Max-Cut algorithm that shouldn't work, unclear why

OK, this might seem like a homework question and, in a sense, it is. As a homework assignment in an undergraduate algorithms class, I gave the following classic: Given an undirected graph $G=(V,E)$, ...
31 views

Redundancy During Removal of Null-Moves (Regular Exp to Finite Automata) [on hold]

I do not know whether this site is the right one for my automata questions, but I'm giving it a shot anyway. I'm no researcher, just a CS undergrad student who had theory of computation in his 4th ...
43 views

Theory of Computation Question

Theorem: If a language is Context Free Language , then its Transpose (also known as the reverse) will also be Context Free Language... I couldn't proof this theorem , please help if possible..
44 views

How to find the kth smallest element in a set [on hold]

We have an array A[1..N] and M is the maximum element of array A. We have a set S = { A[i] - A[j]: i<>j and A[i] > A[j] } We want to find the k-st smallest element in S. I am guessing that a heap ...
198 views

Graph classes where Hamiltonian Cycle and Hamiltonian Path problems have different complexity

While searching The information System on Graph Classes and their Inclusions, I found several graph classes for which the Hamiltonian Cycle problem is NP-complete while the complexity of Hamiltonian ...
91 views

Lovasz Theta as a short certificate

Lovasz Theta Function provides short proof for the question, "is the Shannon Capacity of a graph($\Theta(G)$) greater than $r\in\Bbb R$?" if the answer is NO when $r$ is above a certain value (this ...
71 views

What is the underlying physical principle behind quantum fault tolerance in quantum computation?

What is the underlying physical principle behind quantum fault tolerance in quantum computation? I am trying to follow the mathematical steps behind quantum fault tolerance, and while I can just ...
27 views

How to find the leaders in order to apply The Meggitt algorithm [on hold]

For example, a generator polynomial g(x) generates a cyclic code with length n=15, dimension k=7 and minimum distance d=5. (p=2) -> p = |(d-1)/2| degree 14 -> r=n-1=15-1 weight <= 2 -> weight ...
55 views

What are some efficient algorithms for finding the solutions to a quadratic multivariate polynomial?

Based on this question, there's an efficient algorithm to determine whether a quadratic multivariate polynomial solution exists. What are some algorithms to enumerate these solutions?
212 views

Subgraph containing all nodes and edges that are part of length-limited simple s-t paths in a digraph

Note: I posted a similar question regarding undirected graph. Given A digraph $G$ with no multiple-edges or loops A source node $s$ A target node $t$ Maximal path length $l$ I am looking for ...
64 views

Does CSG $\neq$ CFG imply PSPACE $\neq$ P? [on hold]

We already know that determining whether a CFG grammar generates a string is P-complete, and whether a CSG grammar generates a string is PSPACE-complete. We also know that some CSG languages are not ...
40 views

What is the maximum size of a queue that is implemented by an array of size n?

Introduction to Algorithms, 3rd Ed on page 234 gives an example of a queue that is at most $n-1$ elements implemented using an array $Q[1 ... n]$. I am wondering if this $n-1$ queue size is artificial ...
61 views

Turing machine to generate solved Turing machines that cannot in general be solved?

My question is as follows: For each Turing machine A, that generate pairs (M,H) given some seed N, where M is a description of another Turing machine and H is the statement of whether it will halt or ...
129 views

What is this notation style called?

I was reading a paper about implementing the statistical programming language R on the JVM, and encountered this notation I haven't seen before (I'm not formally CS-trained). What is the name of ...
164 views

Maximize the expected number of “losers” - Is it NP-hard?

I am trying to find a reduction for a problem that seems NP-hard: Let me start from a toy example. Consider 3 elements, $a$, $b$, and $c$. You want to choose two pairs out of the three pairs and ...
33 views

OCaml - how to set reference to special element in tree

Given type tree = Node of int * tree list * tree ref ;; our task is to set, for every node, the 3rd element of constructor Node (i.e. tree ref). We must set ...
294 views

Do we know whether P^#P = NP^#P?

I thought the relation between P using a #P-oracle and NP using a #P-oracle is still unknown (or equivalently the relation between P^PP and NP^PP). Recently, I have read in a journal article that ...
125 views

In what sense are Scala's Try[T] and Future[T] dual?

In a recent course based on Scala I found a hint that the Scala types Try[T] and Future[T] are dual. This was explained only ...
152 views

Graph Isomorphism is good candidate for NPI problem. NPI problems exist unless $P=NP$. I'm looking for a natural problem that is hard of GI under Karp reduction (A problem $X$ such that $GI <_p^m ... 0answers 17 views All versions of differential evolution algorithm explain all updates in the basic algorithm of differential evolution. i am not able to find all versions of this algorithm. explain all versions of this algorithm as a survey and i am not clearly ... 1answer 83 views Partitioning a matrix into equal-sized regions: finding the maximum I am facing the following research problem. We are given a matrix$M[1..p,1..p]$of elements such that: each element has value in the range$[0, \frac 1 j]$,$j <= p$,$j$is given, the sum of ... 2answers 90 views 2DFA that requires many states in equivalent DFA? Is there a 2DFA with$n$states (where$n$is nontrivial, say at least 4) that requires at least$2^n$states to simulate using any DFA? A two-way DFA (2DFA) is a deterministic finite-state ... 0answers 162 views Proof verification:$P \neq NP$[closed] I think that I can prove that$P \neq NP$, please verify my proof. Proof by contradiction: Any NP-Complete problem could be reduced to Circuit SAT. Any NP-Complete problem have a deterministically ... 0answers 73 views Testbed of perfect graphs Is there a publicly available testbed of perfect graphs? Ideally, the number of vertices should be 100 or more. 0answers 26 views Shifted geometric means Reading papers on the runtime comparison of two different algorithms on a given benchmark set, one often reads the term "shifted geometric means". Could anyone explain how it is defined and why it is ... 0answers 29 views Let A be the set of all strings of the form www(with binary alphabet). Show that A is decidable in linear time and that A is in L [on hold] I am learning the Computer theory, this question is related to the course. 0answers 47 views If a ∈ P and b is nontrivial , then b ∩ a ≤ b [closed] If a ∈ P and b is nontrivial , then b ∩ a ≤ b. Hello I was wonder if I am approaching this question correctly. My intuition is that since a is part of polynomial and we are taking the intersection ... 0answers 59 views Random 3-SAT: What is the consensus experimental range of the threshold? The critical ratio of clauses to variables for random 3-SAT is more than 3 and less than 6, and seems to be commonly described as "around 4.2" or "around 4.25". Mezard, Parisi, and Zecchina prove (in ... 0answers 50 views Depth First Search mark node as unvisited? [closed] I am reading Top Coder tutorial on Graphs, and the algorithm for DFS is given as follows: ... 0answers 43 views Examples of context-free languages with a non-context-free complements Context-free languages are not closed under complementation. In the lectures we have been given the same argument as here on Wikipedia. But this only shows that one of the three languages$A$,$B$, ... 1answer 164 views Reference for Turing to many-one reductions I am looking for a reference on `reducing' Turing reductions to many-one reductions. I have in mind a statement of the following form (similar enough statements would also satisfy me): Theorem. If ... 2answers 155 views Foundational textbook(s) for Complexity and Computability on Real Numbers It would be extremely helpful if someone can suggest foundational textbooks on Recursive Analysis (Computability over Reals) which explains connections between Computability and the Topological ... 3answers 1k views Cryptography without assumptions — seeking an overview Suppose$P = NP\$ and a fast linear-time algorithm for SAT appears tomorrow. Suddenly RSA is insecure, much of our modern communication system is broken, and we need to reconsider how to keep secrets ...

15 30 50 per page