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

learn more… | top users | synonyms

3
votes
0answers
25 views
+50

Sparser Bipartite graphs?

Maximal Planar Bipartite graphs are sparser than maximal planar graphs. For which other classes of graphs are maximal Bipartite members sparser than arbitrary maximal members. Let $\mathcal{C}$ be a ...
3
votes
2answers
96 views

Runtime of Tucker's algorithm for generating a Eulerian circuit

What is the time complexity of Tucker's algorithm for generating a Eulerian circuit? The Tucker's algorithm takes as input a connected graph whose vertices are all of even degree, constructs an ...
1
vote
0answers
90 views

Has there been work on formal Semantics for linear algebra?

Could I get some references on formal semantics for a calculus on linear algebra that helps you study matrix or tensor based programming languages? I am looking for anything that encompasses linear or ...
11
votes
0answers
78 views

Which monotone Boolean functions are representable as thresholds on sums?

I will introduce my problem with an example. Say you are designing an exam, which consists of a certain set of $n$ independent questions (that the candidates can get either right or wrong). You want ...
-1
votes
0answers
64 views

Similarity between two SAT formulas [closed]

Are there papers or results on similarity measures (metrics, etc.) between formulas in first order logic? That is, functions $f(\varphi_1, \varphi_2)$ that give some measure of similarity between ...
22
votes
2answers
984 views

Complexity zoo for unary languages

Of course, some complexity results may collapse for unary languages but I wonder if there is somewhere a survey summarizing the known results in this case: a kind of complexity zoo for unary ...
7
votes
1answer
107 views

Formalized priority argument

A priority argument, an important proof technique in recursion theory, was introduced by Friedberg and Muchnik, to solve Post's Problem, i.e., the existence of two r.e. sets that do not Turing reduce ...
1
vote
1answer
74 views

Reference for CTL* logic

I need a reference for CTL* logic (preferably easy to understand). I have gathered some disperse information regarding temporal and CTL logic but I need a more orderly coverage. A chapter of the ...
2
votes
1answer
52 views

List of papers on Runtime and Statistical Tradeoffs on Machine Learning

I was interested in the connection between (statistical) learning guarantees (or any statistical properties) and their relation to run time. For example, I was wondering, in what cases does having ...
10
votes
2answers
200 views

Name the graph class: Disjoint union of a clique and an independent set

Let $G$ be a graph which is the disjoint union of a clique and an independent set, i.e. $$G = K_{n_1} + \overline{K_{n_2}} = K_{n_1} + I_{n_2} .$$ The graph class of all such graphs is characterized ...
8
votes
6answers
566 views

Are there any topics in theoretical CS that are more about pure math?

I am a graduate student in theoretical computer science, and in particular, approximation algorithms. I find now that I am more interested in pure math (I can say this because I seem to have enjoyed ...
3
votes
1answer
187 views

Analogies between VNP and NP

Valiant introduced the class VNP with respect to "arithmetic circuits" over 35 years ago in a "rough" analogy to NP. Recently, there have been major advances in the area of arithmetic circuits eg as ...
7
votes
1answer
170 views

Information theory and convex optimization

I'm taking a graduate level course in information theory and I'm constantly struck by how much convex optimization there is in this subject. However, the proofs seem to shy away from using the full ...
3
votes
2answers
124 views

Question about an old result of Erdős and Simonovits

My question concerns the following result of Erdős and Simonovits. A graph $G$ is $d$-almost-regular if $d\delta(G)\geq \Delta(G)$. Theorem 1 of the above paper states that a large $n$-vertex ...
2
votes
1answer
59 views

Complexity for single-linkage clustering with max norm

Let $S\in\mathbb Z^d$ be a set of points, with some notion of distance $d(x,y)$ between two points $x,y\in S$. I am specifically interested in the max distance, that is $d(x,y)=\max_{1\le i\le d} ...
2
votes
1answer
139 views

Knapsack combining sum and product

I cannot find references concerning the complexity of the variant of the knapsack problem (decision version) where one of the two conditions must be a product instead of a sum (0 not allowed). A ...
1
vote
0answers
45 views

complexity of factoring multivariate polynomials over Fn

recently multivariate polynomial factoring has been related to Polynomial Identity Testing / PIT (by Kopparty, Saraf, Shpilka). where is the complexity of factoring multivariate polynomials over ...
4
votes
0answers
177 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
57 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
43 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 ...
11
votes
0answers
98 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
209 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
64 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
56 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
698 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
161 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
70 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
66 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 ...
12
votes
5answers
510 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
542 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
268 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
74 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
69 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
77 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
169 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
158 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
137 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
62 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
97 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
595 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
350 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
186 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
112 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
171 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
165 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
131 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
92 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
130 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 ...