Reference-request is used when the author needs to know about work related to the question.

learn more… | top users | synonyms

-1
votes
0answers
23 views

citation for the vertex-splitting flow technique

I'm looking for a citation for the vertex-splitting variant of the Ford-Fulkerson algorithm (see the answer to Minimum-Cost Flow Problem with Constraint on the Total Incoming/Outgoing Flow for the ...
2
votes
0answers
64 views

Techniques introduced to log-rank conjecture

What have been some of techniques (like discrepancy, arithmetic combinatorics) that have been introduced to shed light on Log-rank conjecture which roughly states that deterministic communication ...
2
votes
1answer
62 views

Finite state transducer with infinitary outputs or without emphasis on acceptance?

1) Is there a notion of (deterministic) finite state transducer (FST) that allows the possibility of producing an infinite stream of output symbols? In other words, one where the transduction ...
1
vote
0answers
68 views

Complexity of Approximating Vandermonde Determinant

Given an $n\times n$ Vandermonde integer matrix with structured integers (such as arithmetic or geometric progression). Is complexity of approximately computing Vandermonde determinant upto ...
4
votes
1answer
154 views

possible bridge between group growth theory and complexity theory?

RJ Lipton conjectures a link between group growth theory and complexity theory. Group growth theory has undergone rapid advance in the last decade and has many surface similarities/ parallels with ...
4
votes
1answer
121 views

Introductions to steganography from an information-theoretic standpoint

Can I get some introductory references for steganography from an information-theoretic standpoint? I recently listened to a talk on it, and the speaker said that he knew of no good introductions to ...
3
votes
1answer
119 views

Finding a minimum directed cut that splits a weakly connected bipartite graph into two such non-edgeless graphs

Consider a directed, weakly connected bipartite graph $G = (U, V, E)$ where $U$ and $V$ are sets comprising the nodes of $G$, and $E \subseteq U \times V$ is the set of edges. The task is to find a ...
0
votes
0answers
56 views

Transcript of Feyman's Computer Heuristics Lecture

I am looking for an transcript of Feyman's Computer Heuristics Lecture. Does anyone know of one? Thanks in advance
4
votes
0answers
86 views

An oracle relative to which EXP(NP) = BPP

Whether or not $\mathbf{BPP} = \mathbf{EXP}^{\mathbf{NP}}$ is an open problem, although we believe the former is strictly contained in the other. I guess, from the absence of the proof of the ...
20
votes
5answers
561 views

Curious about computer-assisted NP-completeness proofs

In the paper "THE COMPLEXITY OF SATISFIABILITY PROBLEMS" by Thomas J. Schaefer, the author has mentioned that ...
3
votes
0answers
40 views

Reference for Nuclear Norm Relaxations

I have seen a bunch of results concerning Matrix Completion, PCA, Compressed Sensing where a common theme has been to relax the Rank constraint/objective by replacing it with Nuclear Norm. I was ...
4
votes
1answer
330 views

The complexity of a multi-objective shortest path problem

I have the following shortest path problem. Consider a directed graph with $n$ levels. Each level has $m$ nodes. Each node at level $i$ is connected to all nodes at level $i+1$. Let us also make a ...
5
votes
1answer
67 views

Quanitifier Free Presburger Arithmetic: Upper bound on solution size?

DISCLAIMER: I had originally posted this to CS.SE, but I've deleted it and moved it here, since it received little attention, and I think it is a research level question. According to this paper, if ...
4
votes
1answer
158 views

Array-like data structure with O(1) worst-case concatenate/join?

I am looking for a data structure $D$ which supports the following operations (preferably a (binary) tree-like structure): $D$ is indexed, i.e. there is a mapping from $\{1, \ldots, n\}$ to items ...
-1
votes
0answers
37 views

reported cases of pseudo random number generator biasing results

occasionally students ask about the theory of (pseudo) random number generators. it occurred to me it would be helpful to know significant reported cases where "not random enough" PRNGs were found to ...
2
votes
2answers
102 views

Reference on cryptography methods

I'm looking for a good reference, possibly a survey, on the different types of cryptography methods. As far as I understand, the security of a cryptographic method depends on some hardness ...
8
votes
1answer
155 views

Reference for the fact that (0=1) implies false requires a universe in MLTT

It's a fairly well-known fact that deriving a contradiction from a disequality (for example, $(0=1) \to \bot$) in Martin-Loef type theory requires a universe. The proof is also fairly ...
4
votes
1answer
158 views

Graph theoretic restriction to Proofs in Proof Complexity Theory

Proof complexity is a most basic area of computational complexity theory. An ultimate purpose of this area is to prove $NP\neq coNP$, that is, any prover cannot give a proof of unsatisfiability of ...
8
votes
1answer
128 views

Complexity results about locally bipartite graphs

A graph is locally bipartite if the open neighborhood of every vertex induces a bipartite graph. (According to searches the same name might be used for something else related to surfaces). Which ...
3
votes
0answers
80 views

Reconstruction of sparse vectors from random matrices

In the paper [A], the following linear algebra result (Lemma 5 in [A]) is stated as being well known. Note that a vector is $s$-sparse if it contains at most $s$ non-zero entries. Lemma: Let $1 ...
3
votes
0answers
123 views

Equivalence of deterministic finite transducers over finite/infinite words

Equivalence of deterministic finite transducers - a special case of single-valued finite transducers - is decidable because it is decidable whether a transducer is single-valued. Note that two ...
2
votes
1answer
46 views

Promise Variant of Set-Packing

An instance of the SET-PACKING problem is given by a list of sets $\mathcal{S} = \{S_1,\dots,S_m\} \subseteq 2^U$. It is a ``yes'' instance iff there exists some subset $\mathcal S'$ of $\mathcal S$ ...
3
votes
2answers
235 views

computing maximal bit density over a FSM

let $L$ be a regular language defined by a FSM over binary symbols $\{0,1\}$. consider a function $f(x)$ on words/ strings that computes "bit density", defined as the number of $1$'s in a word ...
1
vote
0answers
122 views

Looking for reference on NP-Completeness of proofs of length n

Given a deductive system $\Lambda$, and some well-formed-formula S, one can ask the question "Is there a proof S in $\Lambda$ of length n?" If n is presented in base-1 and if all the axioms of ...
10
votes
1answer
187 views

Hartmanis-Stearns conjecture and the computable transcendental numbers

In the 1965 article "On the computational complexity of algorithms" by Hartmanis and Stearns, the authors conjecture that if a real-time Turing Machine computes the real number $r$ in, for example, ...
2
votes
1answer
94 views

minimal finite automata given in-words and out-words

this seems an interesting FSM optimization problem; have not seen it studied, wondering if it has been and/ or looking for other insight. given: two finite sets of words $S_{in}$ and $S_{out}$. ...
2
votes
1answer
64 views

Lower bounds and impossibility results for distributed transactions

I am studying on distributed transactions, mainly on the correctness criteria (e.g., serializability (SR) and snapshot isolation (SI) in replicated settings) and their implementations. To avoid ...
7
votes
1answer
87 views

Extensional characterization of non-deterministic finite state transductions

I recently became aware of the rather appealing characterization of deterministic word-to-word transductions as word functions with bounded variation (see e.g. [1]). This coincides with the set of ...
13
votes
1answer
307 views

“Snake” reconfiguration problem

While writing a small post on the complexity of the videogames Nibbler and Snake; I found that they both can be modeled as reconfiguration problems on planar graphs; and it seems unlikely that such ...
10
votes
2answers
436 views

Lower bound on estimating $\sum_{k=1}^n a_k$ for non-increasing $(a_k)_k$

I'd like to know (related to this other question) if lower bounds were known for the following testing problem: one is given query access to a sequence of non-negative numbers $a_n \geq \dots\geq a_1$ ...
8
votes
1answer
143 views

What are the major research issues in distributed transactions?

Background: Transaction processing has been a traditional research topic in database theory. Nowadays distributed transactions are popularized by the large-scale distributed storage systems which ...
0
votes
2answers
105 views

Where can I find the proof of the theorem and what is the computational complexity of the computably isomorphic map?

"any two representations of reals which are acceptable are actually computably isomorphic",please see here for reference where may proof of this theorem be found, and what is the the computational ...
-2
votes
1answer
62 views

For two representations of finite length of one computable number are there $P$-time algorithms that compute one from another

Any computable number may have different representations of finite length . For example,$\sqrt{2}$ may be represented as root of equation, or as a (shortest for a universal Turing Machine)program of ...
0
votes
0answers
38 views

What are the differences between data partition and data replication regarding distributed transaction?

For a large-scale distributed database (or storage) system, data is often partitioned (wiki) (a.k.a sharding) and/or replicated (wiki) across different nodes. Roughly speaking, data partition splits ...
1
vote
1answer
117 views

Reference for unpublished but quoted manuscript

Is there a place to locate the reference "[Smi88] D. V. Smirnov, ``Shannon's Information Methods for Lower Bounds for Probabilistic Communication Complexity,'' Master's thesis, Moscow University, ...
8
votes
2answers
154 views

Understanding graph minor theorem

This question is two-fold, and is mainly reference-oriented: Is there somewhere where the main intuitions for proving graph minor theorem are given, without going too much into the details? I know ...
1
vote
0answers
73 views

What is the name of this data structure? (hash table with a limit on the number of entries)

Denote $[n] \triangleq \{1,2,\ldots,n\}$. Assume we would like to have a data structure $S$ which kinda works as a dictionary from $[k]$ to $[v]$, and supports add/remove/update/query functionality, ...
7
votes
2answers
220 views

Enumerating Planar Graphs of Bounded Treewidth

I am looking for references for the following problem: given integers $n$ and $k$, enumerate all non-isomorphic planar graphs on $n$ vertices and treewidth $\leq k$. I'm interested both in theoretical ...
4
votes
2answers
165 views

Flat vs non-flat domains

My understanding is that, more often than not, when people use domain theory for higher-type computability or the denotational semantics of functional programming languages, they tend to prefer flat ...
4
votes
1answer
154 views

Is it decidable that a computable analytic function over $\mathbb{R,C} ,$ equals $0$

Is it decidable whether a computable analytic function $f(x_1,x_2,\dots,x_n)$ over $\mathbb{R}$, $\mathbb{C}$ in a semi-algebraic or semi-analytic domain is identically zero? Is there any algorithm? ...
10
votes
2answers
220 views

How to judge the definition of computational complexity of reals is natural or suitable?

As we know, definition of computational complexity of algorithm is almost without controversy, but the definition of computational complexity of reals or the computation models over reals is not in ...
5
votes
2answers
97 views

Can real-time deterministic multicounter automata recognize the marked palindrome language?

Consider the marked palindrome language which is defined as MPAL=$\{ w\#w^r | w \in \{a,b\}^* \}$. It is easy to recognize MPAL using only a single stack. My question is whether MPAL can be ...
3
votes
0answers
79 views

Presburger Arithmetic Decision Procedures

What are good textbook references for Presburger Arithmetic decision procedures?
10
votes
1answer
442 views

Decide the existence of a string homomorphism

Consider the following problem: Given two strings x,y, decide whether there exists a string homomorphism f such that f(x)=y. It is easy to show that this problem is in $NP$. Are there other ...
1
vote
0answers
144 views

intuition that VP=?VNP is (not?) connected to P=?NP

recently there has been major progress into the VP=?VNP problem for algebraic circuits originated by Valiant, inspiring some optimistic outlook on its eventual or imminent resolution.[1] what is ...
8
votes
2answers
347 views

Looking for Literature Source for Following idea

I am quite certain that I am not the first to entertain the idea that I am going to present. However, it would be helpful if I can find any literature related to the idea. The idea is to construct a ...
6
votes
4answers
229 views

Explaining computer science algorithms/concepts/ideas using metaphors

Recently I found an interesting algorithm book entitled 'Explaining Algorithms Using Metaphors' (Google books) by Michal Forišek and Monika Steinová. "Good" metaphors help people understand and even ...
13
votes
2answers
483 views

Long-Standing Conjectures later trivially proved by an implication

I'd like to know if there have been conjectures that have long been unproven in TCS, that were later proven by an implication from another theorem, that may have been easier to prove.
6
votes
1answer
162 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 ...
6
votes
1answer
137 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 ...