All Questions

Filter by
Sorted by
Tagged with
0 votes
0 answers
10 views

Exponential version of $CC^0$

(In this question, "uniform" will mean $DLOGTIME$-uniform.) In Allender's 1998 paper "The Permanent Requires Large Uniform Threshold Circuits", he talks about the "exponential ...
  • 885
-2 votes
0 answers
21 views

Is $O[2^n]$ equal (or close) to $O[2^n/n]$?

Is $O[2^n]$ equal (or close) to $O[{2^n \over n}]$? One is the number of integers when $n$ is the number of digits, the other is the number of prime numbers up to an integer with $n$ digits (assuming ...
2 votes
0 answers
38 views

Treewidth for hypergraphs that specify connectedness requirements

This question is about an alternative definition of treewidth, called weak treewidth. It is defined on hypergraphs where hyperedges intuitively require that the connected subtrees of occurrences of ...
  • 7,870
0 votes
0 answers
90 views

Savitch's theorem for time complexity

Is it known that an analog of Savitch's theorem for time complexity is impossible, or is this an open question? More formally, is $\exists d\ \forall c : \mathsf{NTIME}(n^c) \subseteq \mathsf{DTIME}(n^...
0 votes
1 answer
27 views

Differing definitions of a weak learner

I've been reading about boosting and have come across basically two definitions of a weak learner. Basically for hypothesis $h$ and target $c$, some definitions says that $h$ is a weak learner if $E[h(...
  • 1
0 votes
1 answer
55 views

reducing this problem to a decision problem

Before I can define my problem, let's make a simple definition. An expression $e$ is a conjunction of inequalities of the form $x~ op~ v$ where: $x$ is a variable, $op\in[<,>,\leq,\geq,=]$, and $...
1 vote
0 answers
56 views

Is this subsequence problem NP-hard?

Here is yet another "is X NP-hard?" question. The input of the problem is the following: A sequence of $n$ non-negative real numbers $\alpha_1, \ldots, \alpha_n$. Here $n$ is a positive ...
  • 11
0 votes
0 answers
36 views

Can information, eg. Shannon Entropy, be considered an absolute value?

This question is a distillation of my question here: How do I calculate the information content of a mass spectrum? Using a theoretical instrument that makes perfect measurements of fundamental ...
-1 votes
0 answers
21 views

Looking for paper on approximating TSP by cycle covers

I'm looking for a paper about approximating TSP by cycle covers mentioned here https://youtu.be/LPKHnPeF7aI?t=2001 I think he said a name but I couldn't make it out.
  • 225
1 vote
0 answers
32 views

computational complexity of sparse matrix powers

Given a sparse matrix $A$ with $nnz(A)$ denoting the number of non-zero entries in it. What is the computational complexity of computing $A^k$, for some positive integer $k$? As $k$ gets larger, I ...
  • 199
3 votes
1 answer
72 views

Does ${\bf CPO}$ have $\omega$-colimits?

Does the category ${\bf CPO}$ have $\omega$-colimits? By ${\bf CPO}$ I mean the category that has as objects the $\omega$-complete pointed partial orders and as arrows $\omega$-continuous functions.
  • 103
5 votes
0 answers
76 views

Reductions and projections in circuit complexity

I'm struggling to find a good reference that defines the difference between projection and monotone projection in the context of Boolean functions and circuit complexity. My understanding is that a ...
5 votes
1 answer
149 views

Is $PSPACE$ believed to be different than $PP$?

From Googling, I couldn't find any discussion about whether $PP=PSPACE$ is more or less likely than $PP\subsetneq PSPACE$. Is it currently believed that $PP\neq PSPACE$? What would be the ...
  • 195
0 votes
0 answers
52 views

Maintaining a $K_{3,3}$-minor-free graph

Suppose we are given that an undirected, connected graph $G$ is $K_{3,3}$-minor-free. Let $a,b\in V(G)$ be non-adjacent vertices. Under what conditions is the graph that results by adding the edge $(a,...
  • 75
0 votes
0 answers
53 views

Unclear explanation of basic parallel DAG computation

Consider computation represented as a DAG, without if-then-else conditions, where nodes represent tasks and edges represent data dependencies. For example, A->B->C means that there are 3 tasks ...
  • 1
0 votes
1 answer
41 views

Spectral sparsification of graphs with negative edge weights

I am reading the following well-known paper on spectral sparsification of weighted graphs: https://arxiv.org/pdf/0808.4134.pdf. Page 2 contains most of the definitions relevant to this question. It is ...
  • 1
6 votes
1 answer
260 views

Concrete family of propositional formulas

Let $k,n \in \mathbb{N}$, where $k$ can be thought of as being fixed constant. For each $1 \leq \ell \leq k$ and $1 \leq i \leq n$ we have a proposition symbol $p_{(\ell,i)}$ (so in total we have $nk$-...
0 votes
1 answer
60 views

Regarding UNSAT bechmark of SATLIB found as SAT instance

I found the Satisfiable assignment to one of the UNSAT [SATLIB benchmark][1] instance, specifically uuf50-01.cnf as below answer: [1, 2, 3, 4, -5, -6, -7, -8, 9, 10, -11, 12, 13, 14, -15, -16, 17, 18, ...
  • 11
-1 votes
0 answers
30 views

Do Euler paths have to start and end at different vertices? [closed]

I am wondering whether every Euler graph is also traversable. I.e. are Euler circuits Euler paths? Therefore I am asking the question above.
  • 99
-1 votes
0 answers
41 views

Decision Problem list of Integers Np complete?

I am currently studying the following decision problem: Given a list of integers of size n, for example: [2, 6, 7, 4, 2], n=5. Deleting one integer from the list either lets us go one step further to ...
  • 1
0 votes
0 answers
27 views

Computational complexity of CVaR calculation

I am currently looking for literature discussing the computational complexity of CVaR calculation. At this point the only work I have found is the following. Mavronicolas, Marios, and Burkhard Monien. ...
0 votes
0 answers
81 views

Non-uniformity assumptions in circuit complexity

I recently came accross the following standard inclusion of complexity classes: $$\textbf{NC}^0 \subseteq \textbf{AC}^0 \subseteq \textbf{NC}^1 \subseteq \textbf{L} \subseteq \textbf{NL} \subseteq \...
3 votes
0 answers
95 views

Context-free languages and free/bound variables

Fix a first-order language $L_0$, and let $$L=\{f(\varphi)\mid \varphi \text{ is a well-formed formula of $L_0$}\},$$ where $f(\varphi)$ is $\varphi$ with all occurrences of free variables underlined. ...
7 votes
1 answer
174 views

How do separations in of query complexities imply complexity class separations relative to oracles?

Simon's problem is the following: Given oracle access to a Boolean function $f: \{0,1\}^n\rightarrow \{0,1\}^n$, and promised that precisely one of the following two cases is true, decide which of ...
  • 250
-1 votes
0 answers
106 views

Computable functions with finite storage

Computable functions can be somewhat informally defined like this: Computable functions are exactly the functions that can be calculated using a mechanical calculation device given unlimited amounts ...
0 votes
0 answers
48 views

Non-uniform consequences of uniform derandomization

Adleman showed that $\mathsf{BPP/poly} \subseteq \mathsf{P/poly}$. Does $\mathsf{P} = \mathsf{BPP}$ have any implications for $\mathsf{BPP}/a(n) \subseteq \mathsf{P}/a(n)$ $\mathsf{BPTIME}(t(n))/a(n) ...
0 votes
0 answers
39 views

Maximum-weight matroid intersection with real weights

Given a matroid with weighted elements, a basis with maximum total weight can be found in polynomial time using the greedy algorithm. This is true even when the weights are real numbers, if we assume ...
1 vote
0 answers
56 views

One way analogues of Logspace

When we say a function is one-way we typically mean a function is encodable in $P$ but its decryption is not in $P$ but in $UP$. Likewise we say a function is logspace one-way if the function is ...
  • 12.6k
0 votes
0 answers
11 views

Queueing theory. How to figure out if steady state or grows without bound?

I have a real-life problem from work that we haven't been able to figure out. None of us have advanced CS background. Rate R of message arrival to the system from a client is 7/10s. 25 workers do ...
-4 votes
0 answers
32 views

Using hypercomputation for undecidable problems? [closed]

In mathematics and philosophy there are some unsolvable (or undecidable) problems like Russell's paradox or the liar's paradox that are usually said to be undecidable... There are also other "...
  • 93
3 votes
0 answers
65 views

Bounding the size of a power of a proper interval graph

Is there a citable proof of the following result (or perhaps a generalization of it)? Lemma 1. Let $G=(V, E)$ be a proper interval graph. Let $G^k=(V, E^k)$ be the $k$th power of $G$. Then $|E^k| = ...
  • 9,024
1 vote
0 answers
90 views

How to download .bib of all papers ever published in main venues in TCS (journals, conferences, repositories, etc.)

Is there now a system out there that does this? Or even venue by venue -- for example, is there a way to download all references for all papers published any time in JACM? I tried DBLP but I couldn'...
  • 7,529
0 votes
0 answers
41 views

Can an unrestricted grammar have a rule with only terminals on the left-hand side?

In the definition of unrestricted (type 0) grammars we only really have the rule that the lhs cannot be the empty string. Then, is it allowed to have a production rule with an lhs consisting only of ...
2 votes
0 answers
87 views

Problems in $P^{PP}$

I just discovered that a problem that I was studying could belong to $P^{PP}$, I would like to prove that this problem is $P^{PP}$-complete (if that is even a thing). The issue is that I'm unable to ...
0 votes
0 answers
39 views

Existence of a family of size 2^Ω(n) of subsets of {1,...,n} each of cardinality n/4 where two subsets have at most n/8 elements in common

Let $\mathcal{G}$ be a family of $t=2^{\Omega(n)}$ subsets of $N=\{1,2,...,n\}$, each of cardinality $n / 4$ so that any two distinct members of $\mathcal{G}$ have at most $n / 8$ elements in common. ...
  • 101
2 votes
1 answer
91 views

Hardness of Maximum Independent Set in 3-Colorable Graphs

Let $G = (V,E)$ be an undirected graph such that there is a proper coloring of the vertices of $G$ in three colors. Question: In such graphs, are there known results for the hardness of finding a ...
  • 63
1 vote
0 answers
48 views

Better approximation of the subset in the membership oracle

A standard tool for estimating the size of a subset via membership oracle queries is given below. Lemma 2.8: . Consider two (finite) sets $B ⊆ U$, where $n = |U|$. Let $ε ∈ (0, 1)$ and $γ ∈ (0, 1/2)$ ...
  • 41
10 votes
1 answer
1k views

Is the 3-coloring problem NP-hard on graphs of maximal degree 3?

Consider the 3-coloring problem: given an undirected graph $G = (V, E)$, decide if there is a 3-coloring of $G$, i.e., a function $f$ from $G$ to $\{1, 2, 3\}$ such that there is no edge $\{u, v\}$ in ...
  • 7,870
1 vote
1 answer
60 views

Graph partitioning to minimize sum of intra-partition edge weights

I've seen a lot of graph partitioning algorithms w/ the objective of minimizing the weight of inter-partition edges, (e.g. k-way partitioning) but haven't quite found anything on minimizing the total ...
  • 11
2 votes
2 answers
202 views

Resources for hoodie design related to theoretical CS [closed]

I have to design a hoodie for my computer science batch, and I want it to be related to Theoretical computer science. I don't want to slap on some text with HTML-like angle brackets, but actually want ...
1 vote
0 answers
39 views

Enumerating all parse trees from a parse forest

Say a generalized parsing algorithm whether a GLL parser or Early parser generates a parse forest. Would it be possible to enumerate all of the parse trees from the forest? If possible, in a lazy ...
2 votes
1 answer
41 views

Sampling strategies for Quicksort

I'm studying a variation of Quicksort in which the algorithm samples a subarray of size $f(n)< n$ ($n$ is the size of the input array) and then chooses the pivot from this subarray. The pivot is ...
3 votes
1 answer
162 views

Solving linear programs with special structure

We have an application and at some point we need to solve a linear programming problem that looks like this: $$ \min\ w_{1,2} + w_{3,4} + w_{5,6}\\ x_i - x_j \leq c_{ij},\ \forall\ (i,j) \in C\\ x_1 - ...
  • 73
1 vote
0 answers
101 views

Computing real numbers with Turing Machines

Consider the following decision problem: Given a two integers $n$ and $k$, decide whether $k=\lfloor n\pi\rfloor$ Question: Is this problem known to be in $P$? Although this may look like a stupid ...
-5 votes
0 answers
44 views

Simple questions about SAT problems and some more specifical tasks

I'm a pretty seasoned in practical machine learning and nearly every boolean SAT solvers. Now I'm pursuing MSc in Computer Science degree. So, several days ago I was contacted by one very strange guy. ...
0 votes
0 answers
62 views

On the Reductions of Functional complexity Classes

In Chapter 10 of Computational Complexity by Christos Papadimitriou, it is noted that reduction between problems of functional complexity classes are defined as follows: Function problem A reduces to ...
1 vote
2 answers
182 views

How much information does it take to specify, not each member of a group, but any one member?

It takes exactly $\log_2 n := \lg n$ bits of information to specify a number from $\{1,2,\ldots,n\}.$ Likewise, it takes $\lg{n\choose s}$ bits of information to specify a subset of $s$ out of the $n$ ...
  • 1,513
-1 votes
0 answers
42 views

Randomized Identity testing for circuits

$(1)$If a Arithmetic circuit $C$ has a size $x$, the degree $f_C$ should be $ \leq 2^{x-1} $? Is this bound sharp? why? $(2)$By fingerprinted polynomial Evaluation how to determine the degree of two ...
1 vote
0 answers
54 views

communication complexity lower bound for identifying coordinate in which two strings differ

This is a question from Rao and Yehudayoff's "Communication Complexity and Applications" textbook that I've been thinking about for a while. Suppose Alice has a string $x\in\{0,1\}^n$ that ...
  • 11
5 votes
1 answer
126 views

The precise definition of Normalization By Evaluation?

The Wikipedia article suggests that NbE is a technique for obtaining "the normal form of terms" by translating the object language into abstractions of the meta (host) language: The ...

15 30 50 per page
1
2 3 4 5
244