All Questions

0
votes
0answers
6 views

Name of special class of k-partite graphs

Consider directed graphs $G=(V,E)$ such that $V$ can be partitioned into sets $V_1, V_2, \ldots, V_k$. For the edges we have that if $v \in V_i$ and $(v,w) \in E$ then $w \in V_{i+1}$ for all $1 \le ...
0
votes
0answers
10 views

Does the Y Combinator Contradict the Haskell-Howard Correspondence?

The Y combinator has the type $(a \rightarrow a) \rightarrow a$. By the Haskell-Howard Correspondence, because the type $(a \rightarrow a) \rightarrow a$ is inhabited, it must correspond to a true ...
2
votes
0answers
16 views

Relating univalence for a theory of cateogries to the skeleon concept

Say I work in homotopy type theory and my sole objects of study are conventional categories. Equivalences here are given by functors $F:{\bf D}\longrightarrow{\bf C}$ and $G:{\bf ...
0
votes
0answers
30 views

When is a binary relation confluent? [on hold]

My computer science task states that a binary relation R is confluent if where R is a subset of ℕ (including 0). It is my first task using quantifiers and binary relations, so I have some basic ...
-7
votes
0answers
62 views

A naive proof strategy about the P versus NP [on hold]

Proving that $$P=NP$$ in in $NP$ and, proving that $$P\neq{NP}$$ would be in $P$. Does the formulation is acceptable? Side-precision The proof of $P=NP$ will be so tough to elaborate than it should ...
2
votes
0answers
69 views

Pseudorandom generators indistinguishable by uniform deterministic adversaries

I've seen pseudorandom generators defined for nonuniform efficient adversaries, or uniform probabilistic efficient adversaries. (For example, a monograph Pseudorandomness by Vadhan (here's its draft ...
1
vote
0answers
33 views

Bounding the cost of an approximation algorithm when subtraction involve

Given an algorithm with approximation ratio $\alpha$, and another algorithm with approximation ratio $\beta=n^\epsilon$, and a solution to a problem with cost $c$. What is the standard way to bound ...
2
votes
0answers
34 views

Is there value in a faster soultion for the Halting Problem in a Linear Bounded Automata?

Sorry for being so informal, but I was thinking a bit about how the Halting Problem is solvable on a LBA but very very slow, in that if you have gone though more states in execution then the total ...
-4
votes
0answers
41 views

The Arrow of Time in a Network

Writing a sci-fi script. Need some legit theory to back up a central story element (so there's no limit re: real world application): Could there be a logically consistent theory supporting the ...
-1
votes
0answers
13 views

DW multi-dimensional modeling; dimensions orthogonality

In Multi-Dimensional design for a data warehouse; the dimensional model is used which is composed of a fact and a set of dimensions, where fact contains measures an each dimension is composed by a set ...
-2
votes
1answer
49 views

The Arrow of Time in a Non-Physical Realm

Could there be a logically consistent theory supporting the transmission of non-physical information to a point in time previous to the time it was sent using a computer network (quantum theory, etc)? ...
3
votes
1answer
78 views

Locally sorted sequences

Let $S=s_1,\ldots,s_n$ be a sequence and $p$ be a permutation on the indices of $S$ such that $p$ sorts $S$. Define a sequence to be locally sorted with degree $k$ if $\forall s_i \in S |p(i) - i | ...
4
votes
1answer
57 views

Busy beaver candidate elimination: Minimum space requirements

I'm currently enrolled in a course that introduces Turing machines. As I wanted to play around a bit, I wrote a little TM engine and had it search for busy beavers (it successfully found the 4-state ...
-3
votes
1answer
69 views

What are some natural problems that we can quickly find a solution to using massive parallelism but not a canonical solution?

For many problems, more than one output is acceptable. For instance, the problem of finding an assignment that satisfies a boolean formula. If randomness buys us something then it could be that it ...
0
votes
0answers
46 views

Complexity of scheduling jobs on arcs in a network

Consider a path consisting of 3 arcs. For each arc we are given a set of jobs $j$, specified by a release date $r_j$ and a deadline $d_j$. All jobs have unit processing time. A solution of the problem ...
4
votes
1answer
64 views

Categorical semantics for non-monotonic logics?

Are there any categorical semantics for non-monotonic logics? It appears that the simple answer to this is "No" since the obvious notion of composition fails for any model of a non-monotonic logic. ...
7
votes
1answer
103 views

Theoretical results for random forests?

Random forests have a reputation among practitioners of being among the most effective classification techniques. Yet we don't encounter them much in the learning-theoretic literature, from which I ...
-1
votes
0answers
18 views

SVM and Neural Networks

Both Support Vector Machines and neural networks learn a separator for classification. How do they differ in choosing the separator? How do they differ in their mechanism to go from a linear to a ...
6
votes
1answer
88 views

Are there presentations of set theory in terms of lambda-calculus?

I am planning to implement in software a set theory language, based on a binary function, which in set theory is the so called adjunction operation: $f(x, y) = x \cup$ {y}. Therefore, a presentation ...
18
votes
3answers
371 views

Natural NP-complete problems with “large” witnesses

The question on cstheory "What is NP restricted to linear size witnesses?" asks about the class NP restricted to linear size $O(n)$ witnesses, but Are there natural NP-complete problems in which ...
5
votes
1answer
41 views

Where is relational parametricity in hyperdoctrine or topos models explored?

Reynolds originally proposed a relational semantics for the second order polymorphic lambda calculus[1]. However he later showed[2] that this approach was inconsistent with classical set theory. ...
0
votes
1answer
35 views

Why are sub-normalized states studied in quantum computation?

By basic postulates of QM, any state of a system is described by a normalised density operator. Now i fail to see why people study sub-normalized states ( e.g.: In generalised fidelity etc). I'd be ...
-2
votes
0answers
9 views

Is current hardware adequate for neural networks ? Are there more adequate hardware?

If you have a large neural network and you use more than 10 cores, it will be limited by the fact each core will need to read/write data that it can't access fast enough. I've read about some samsung ...
7
votes
3answers
145 views

How high are the higher types that appear in practice?

This is admittedly a rather naively put and vague question, and I'm not sure how much more specific I want or can make it, but I'll try. By "practice" I mean surely in actual programming practice (of ...
0
votes
0answers
29 views

Algorithm to go from a picture (or pictures) of a string in space, to a piecewise-linear representation of the curve

Say you have a knotted-up string or, as in this case, USB cable: I am wondering to what extent there are algorithms that could turn a picture like this (or a succession of pictures of the same ...
2
votes
2answers
96 views

Can Curry-Howard prove a theorem from the types in your program, that has nothing to do with your program?

The following link states: Curry-Howard means that any type can be interpreted as a theorem in some logical system, and any term can be interpreted as a proof of its type. This does not mean ...
0
votes
1answer
104 views

Where is the proof of universality of Rule110 in Stephen Wolfram's book?

I have Stephen Wolfram's book A New Kind Of Science. And I want to find the proof of the universality of Rule 110. I couldn't find the clue in the contents page since it only shows 12 chapters and no ...
2
votes
0answers
87 views

What makes for a good paper abstract?

I am writing a paper for a TCS conference and wondering what the community's opinion is on how abstracts in TCS should be written, good practices, or rules of thumb. I thought that I had read enough ...
-4
votes
0answers
56 views

Doubts about dichotomy theorem [on hold]

Good afternoon. I have a little doubt about the schaeffer dichotomy theorem: http://www.ccs.neu.edu/home/lieber/courses/csg260/f06/materials/papers/max-sat/p216-schaefer.pdf I ve seen in that paper ...
-1
votes
0answers
71 views

When is counting coins NP-complete? [closed]

having a bit of an issue with this question and deciding which of these situations requires dynamic programming and which are NP-complete: All three (except the last one) ask how much goes to person ...
15
votes
1answer
367 views

Any polynomial which is hard to count but easy to decide?

Every monotone arithmetic circuit, i.e. a $\{+,\times\}$-circuit, computes some multivariate polynomial $F(x_1,\ldots,x_n)$ with nonnegative integer coefficients. Given a polynomial ...
1
vote
0answers
168 views

Reconstructing a string from random samples

What is known about the following problem? Reconstruct a string $\sigma$ of known length $n$ over a known alphabet $\Sigma$ from a collection of uniformly and independently chosen $k$-long ...
3
votes
1answer
99 views

Why is shifting bits different from shifting qubits?

In classical circuit complexity, shifting bits is considered gratis; all you have to do is reorganizing wires between corresponding gates. By contrast, shifting qubits is typically done by using a ...
-1
votes
1answer
74 views

Connecting partial paths to form a hamiltonian cycle

For an undirected graph that consists of partial paths such that each vertex is a part of one of those paths and that there are edges between all the paths, is there an efficient algorithm to connect ...
6
votes
0answers
83 views

Bias of a random boolean low degree polynomial

What is the bias of a random Boolean function that can be represented as a low degree polynomial over the reals, i.e. has low Fourier degree? More specifically, is it true that if we take a uniformly ...
9
votes
4answers
126 views

Applications of $p$-adic numbers in CS

Are there any concrete (or a rich source of) examples of application of $p$-adic numbers in computer science?
10
votes
1answer
166 views

What is this variant of set cover problem known as?

Input is a universe $U$ and a family of subsets of $U$, say, ${\cal F} \subseteq 2^U$. We assume that the subsets in ${\cal F}$ can cover $U$, i.e., $\bigcup_{E\in {\cal F}}E=U$. An incremental ...
-2
votes
0answers
78 views

Is the SAT variant where exactly k variables must be set to true known? [on hold]

Consider the following satisfiability variant: Given a CNF formula $F$ and an integer $k$, decide if there is an assignment $\phi$ such that $F$ is satisfied under $\phi$, and $\phi$ sets exactly ...
3
votes
2answers
77 views

Lower bound proof for compressive sensing (Gel'fand widths)?

Let $x \in \mathbb{R}^n$ have $k$ non-zero entries. The main insight of compressive sensing is that there exist $m\times n$ matrices $A$ with $m = O(k \log n/k)$ such that any $x$ can be recovered ...
-1
votes
0answers
41 views

Support tortoise svn application [closed]

Am currently working on developing an desktop application we could use at our startup to function along side the current repository tortoise svn and also monitor and track developer activity ( ...
8
votes
3answers
287 views

EXPSPACE-complete problems

I am currently trying to find EXPSPACE-complete problems (mainly to find inspiration for a reduction), and I am surprised by the small number of results coming up. So far, I found these, and I have ...
3
votes
1answer
31 views

Definition of Projection Measure in the characterization of strong approximation Resistance in a paper by Khot et al

I'm reading a paper about Constraint Satisfaction Problems, specifically "A Characterization of Strong Approximation Resistance", Subhash Khot, Madhur Tulsiani, Pratik Worah (ECCC TR13-075). The ...
1
vote
0answers
47 views

Testing - Correcting Pairs in PCPs

The BLR linearity test and the low degree test are two common tools in PCPs. By my understanding these tests ensure bounds such that (self-) correctors can be applied. I have two questions regarding ...
1
vote
0answers
29 views

Minimizing a general submodular pseudo boolean function

Are there algorithms that minimize a general submodular pseudo boolean function (PBF) without first transforming it to a quadratic pseudo boolean function (QPBF)?
33
votes
16answers
8k views

Most memorable CS paper titles

Following a fruitful question in MO, I thought it would be worthwhile to discuss some notable paper names in CS. It is quite clear that most of us might be attracted to read (or at least glance at) a ...
-4
votes
0answers
35 views

Difference between parallel and concurrent buffering? [on hold]

In double buffering there are two terms Concurrent buffering. Parallel buffering. What is the difference between them, answer with example will be appreciated. Are they both in use now a days ? ...
-2
votes
0answers
94 views

Necessity of a Turing machine for a given problem in order to reduce it to another [closed]

I found it surprising that a certain type of reduction hasn't been flagged anywhere (except in Cook's original 1971 proof). Yes, there are Cook reductions (also known as Turing reduction), and the ...
8
votes
1answer
110 views

Randomized identity-testing for high degree polynomials?

Let $f$ be an $n$-variate polynomial given as an arithmetic circuit of size poly$(n)$, and let $p = 2^{\Omega(n)}$ be a prime. Can you test if $f$ is identically zero over $\mathbb{Z}_p$, with time ...
-3
votes
0answers
37 views

Aggregated Analysis [closed]

The answer is .................................. I am trying to study the answer but I have couple of confusions. how did they come with (n-1/2) / (1-1/2) in the 3rd line of the answer. What ...
-2
votes
0answers
36 views

How prevalent are traffic control algorithms?

Can anyone point me to some algorithms that specialize in traffic control and prevention? I am always wondering if traffic lights optimize for specific conditions.

15 30 50 per page