# All Questions

12,154 questions
Filter by
Sorted by
Tagged with
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
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 ...
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
90 views

55 views

• 75
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
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
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$-...
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
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
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
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. ...
• 707
81 views

• 73
1 vote
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 ...
• 465
44 views

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. ...
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
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
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
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