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

learn more… | top users | synonyms

2
votes
0answers
96 views

research papers for undergraduate students

The papers presented at conferences like SODA, FOCS are hard to understand for undergraduates. Also a lot of background knowledge is assumed for understanding such papers. Are there any ...
2
votes
0answers
42 views

Dynamical systems analysis of deep learning

I am interested in finding out references that apply dynamical systems analysis to develop the "theory" of deep learning, specifically (say) feedforward deep neural nets. The only paper I seem to have ...
1
vote
1answer
38 views

Far point queries in high dimensions

Given a set of points $X\subset R^d$ and a number $r\in R$, create a data structure for queries of the form: "given a point $q\in R^d$ return a point $x\in X$ with $\text{dist}(q,x)\ge r$". This is ...
-2
votes
1answer
44 views

Examples of distributed systems [closed]

Would you please give me some examples of real distributed systems in the world that care about the performance of end-user besides the end-system. For example in Amazon Elastic Compute Cloud or Sun ...
-4
votes
0answers
47 views

generalized sequential machine (GSM) rearranging correspondence

consider a generalized sequential machine (similar to a FSM transducer but not the same). some GSMs have a notable property that they can be rewritten as new GSMs by recombining/ rearranging strings ...
10
votes
0answers
93 views

s-t connectivity on infinite planar graphs with finite description

I would like to know if the following problem is known and has been studied: Consider an infinite directed graph that can be built on the infinite lattice "tiling" a finite set of subgraphs, more ...
4
votes
1answer
197 views

Sample complexity of distinguishing two Gaussian distributions?

Below is a description of the problem: Suppose I have two $p$-dimensional Gaussian distributions with the same covariance matrix $\Sigma$ and means $\mu_1$, $\mu_0$. And I can get $n$ samples ...
2
votes
1answer
61 views

How to simulate sequential registers from causal ones?

Background: In distributed shared memory (DSM) model, the problem of register simulations/constructions is to simulate registers with certain characteristic out of registers with weaker features. For ...
0
votes
0answers
51 views

Recently Practical Problems for a Distributed system model

I've read the article of Grosu and Chronopoulos in 2005. For the load balancing problem and the model of distributed system in this article, I am seeking for recently practical problems and real ...
13
votes
2answers
574 views

Time complexity of counting triangles in planar graphs

Counting triangles in general graphs can be done trivially in $O(n^3)$ time and I think that doing much faster is hard (references welcome). What about planar graphs? The following straightforward ...
9
votes
2answers
154 views

Category theory and parsers — references wanted

Since I'm interested in parsers (mainly in parser expression grammars), I'm wondering if there's some work that gives a categorical treatment of parsing. Any reference on applications of category ...
3
votes
1answer
69 views

Results about computability power or limitations of shared read/write registers

I want to know more results about the computability power or limitations of shared $\texttt{read/write}$ registers/objects in distributed/concurrent computing theory. Two typical examples are: [1]. ...
3
votes
1answer
61 views

How well can an arbitrary (unknown) quantum state be imperfectly cloned?

How well can an arbitrary unknown (quantum) state $\rvert \psi \rangle = \alpha\rvert 0 \rangle + \beta \rvert 1 \rangle$, be imperfectly/approximately cloned? Given an unknown state ${\rvert \psi ...
11
votes
4answers
417 views

Additive combinatorics applications in algorithm design

I'm reading surveys by Trevisan and Lovett on applications of additive combinatoric in TCS. The majority of these applications fall under computational complexity, e.g., lower bounds. I wonder if ...
22
votes
3answers
533 views

Is the Cheeger constant $\mathsf{NP}$-hard?

I have read in uncountably many articles that determining the Cheeger constant of a graph is $\mathsf{NP}$-hard. It seems to be a folk theorem, but I have never found either a quote or a proof for ...
8
votes
2answers
265 views

The hardness of generating an instance of a problem that is harder than the complexity of the resulting problem

In the movie Inception Cobb asks a asks Ariadne to design a maze that takes twice as much time to design. This lends itself to a generalized problem where we have an situation where we are resource ...
2
votes
0answers
73 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
67 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
74 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 ...
5
votes
1answer
165 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
153 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
132 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
60 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
94 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
587 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
341 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 ...
6
votes
1answer
75 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
175 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 ...
2
votes
2answers
109 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 ...
10
votes
1answer
167 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
161 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
130 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
87 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
127 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
47 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
123 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
193 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
112 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
67 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
91 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
319 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
437 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
154 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
63 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
44 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
118 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
157 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 ...