All Questions
12,688
questions
0
votes
0
answers
4
views
Are there any problems in $\mathsf{BPP}$ that are known to be $\mathsf{RP}$-hard or $\mathsf{coRP}$-hard?
It's suspected that probabilistic complexity classes such as $\mathsf{RP}$ or $\mathsf{BPP}$ don't have complete problems. Of course, their promise counterparts have complete problems, but I am not ...
- 245
-3
votes
0
answers
28
views
would statistical randomness disprove P=NP
I saw a proof that claimed if the 3sat problem was statistically random which by definition means there are no patterns, then a deterministic turing machine could not possibly solve it more ...
-6
votes
0
answers
58
views
I found a fascinating solution to P=NP on academia.edu, where he creates an inherently undeterministic problem using statistical randomness
for background I just started researching computational complexity, so I have major gaps in understanding. I am not 100% sure if this guy is correct, but I can't seem to see why he would be wrong. ...
0
votes
1
answer
158
views
Does Turing-Church thesis have a secret life? [closed]
So the Turing-Church thesis says that computation formalisms such as Lambda Calculus and Turing Machine correspond to our informal notion of algorithm. It cannot be proven because it since it says ...
1
vote
0
answers
52
views
Is it possible to recover the set of derivation trees of a fact from its semiring provenance in Datalog?
Background: In the context of Datalog, Green et. al (2007) introduce the notion of the Datalog provenance semiring, a generalization of why-provenance as well as bag and probabilistic database ...
- 11
5
votes
0
answers
89
views
Variation of (derandomized) Valiant-Vazirani
I am interested in the following "improvement" of the Valiant-Vazirani reduction. As pointed out here, under the right derandomization assumptions one can obtain a deterministic polynomial-...
- 871
0
votes
0
answers
46
views
Hardness for find the clause for statisfiable 3-SAT problems
The 3-SAT problems are known to be NP-complete so the decision problems are believed to be non efficiently solvable unless P=NP. Yet, there are cases where the satisfiability can be answered such as ...
- 101
-1
votes
0
answers
50
views
Proof that DFS order is P-complete
Suppose we are given an oriented graph G with a selected number of nodes s, where for each node some particular ordering of edges leading from it is specified. If we run a depth-first search algorithm ...
1
vote
0
answers
57
views
How often can a clause cause a conflict?
This question is about DPLL+CDCL algorithms. How often can a clause cause a conflict?
I want to use a specific algorithm. Assume a DPLL+CDCL SAT solver using a fixed variable order. Variables and unit ...
- 559
1
vote
0
answers
38
views
Find the SVM kernel in detecting if a substring in a given string
Consider the task of learning to find a sequence of characters ("signature") in a file that indicates whether it contains a virus or not and let $\mathcal{X}$ be the set of all finite ...
- 131
-1
votes
0
answers
32
views
corresponding resoving and arbitary resolving
Notations:
$$C_x \otimes C_{\bar{x}} = V_1 \lor \ldots \lor V_a \lor W_1 \lor \ldots \lor W_b$$
$$ \text{ where } C_x = x \lor V_1 \lor \ldots \lor V_a \text{ and } C_{\bar{x}} = \bar{x} \lor W_1 \lor ...
- 315
8
votes
1
answer
389
views
What can we do with a generic oracle (as opposed to a random one)?
Let me first recall a few (lengthy but hopefully mostly standard) facts and definitions in order to motivate my question (feel free to skip down to the actual question):
Standard definitions: A ...
- 619
5
votes
1
answer
148
views
Can CDCL Algorithm Derived Conflict Clauses Always Be Obtained Through Resolution from an Unsatisfiable CNF Formula?
I have a question regarding the Conflict-Driven Clause Learning (CDCL) algorithm applied to an unsatisfiable CNF formula $F$.
Specifically, can all the conflict clauses learned by the CDCL algorithm ...
- 315
-1
votes
0
answers
81
views
Proof for Upper Bound on the Size of the Sum of Rational Numbers
In [1], Dominik Wojtczak determines that the 0-1 SUBSET-SUM problem with non-negative rational numbers is strongly NP-Complete.
Assume we are given a list of n items with
rational non-negative ...
2
votes
0
answers
71
views
Enforcing general position in $2d$ linear programming
Let $(x_1, y_1), ..., (x_k, y_k)$ be $n$ points in $\Re^2$. For my sake, $k=20$.
I am trying to set up a linear program to find a set of $k$ points in the plane $P$ that satisfy some linear ...
- 1,078
2
votes
0
answers
53
views
Is the Category of $(* \to)^n *$-kinded types freely generated from the discrete graph with $n$ nodes?
In Introduction to Higher Order Categorical Logic part 1, section 4, Lambek defines an adjunction between $\mathbf{Graph}$, the category of graphs and graph homomorphisms, and the category of ...
4
votes
0
answers
118
views
Convex optimization: is it possible to find solutions that are exactly feasible and approximately optimal in polynomial time?
In Nemirovxki's lecture notes on interior point methods, I found the following.
He defines an approximate solution as satisfying the following, for any given $\epsilon>0$:
that is: the ...
- 2,078
0
votes
0
answers
41
views
Approximation ratio of randomized rounding for integral multi-commodity flow
In [1], Raghavan and Thompson showed that we can use randomized rounding to approximate integral multi-commodity flow and routing with congestion. The result is that suppose the optimal solution is $W$...
6
votes
2
answers
428
views
Error in Robson's proof about separating strings?
One of my students discovered a possible mistake in Robson's classic paper Separating strings with small automata.
The issue is in the proof of Theorem 1, giving the simpler bound $O(\sqrt{n\log n})$.
...
- 13.9k
2
votes
0
answers
58
views
Many-one equivalence of sets that differ finitely
[This is a duplicate of my question from Mathematics Stack Exchange:
https://math.stackexchange.com/questions/4792354/many-one-equivalence-of-sets-that-differ-finitely
I am posting it here since it ...
- 33
-2
votes
0
answers
46
views
d-regular graphs and edge expanders
Show that there is no (n, d, ρ)-edge expander for ρ > 0.5
Is this statement even true?
My attempt: Let n = 2, then we can have 2 vertices, A and B. Let d = 1, therefore there is an edge between A ...
-2
votes
0
answers
43
views
Greedy rounding technique
I have an assignment problem-like structure with a bunch of additional constraints formulated as an integer linear program. By relaxing the integral constraint I ended up in a relaxed LP problem for ...
- 1
16
votes
2
answers
1k
views
Is there a SETH (Strong Exponential Time Hypothesis) for CSP (Constraint Satisfaction Problem)?
The Constraint Satisfaction Problem I mentioned is similar to CNF-SAT: A variable can take values from some finite domain $D$ where $|D| = d$. A literal of variable $x$ is an expression of the form $x\...
- 163
1
vote
1
answer
126
views
Are there any algorithms that the brain is better at solving than a regular computer? How would these be found/verified?
For example, one that brains appear to be able to solve in polynomial time but computers can't, or one optimized for the brain's innate capabilities - like language learning, or different ...
- 11
-1
votes
0
answers
64
views
What are you favorite techniques at finding lower bounds?
I know that for finding lower bounds there are information-theoretic techniques like Le Cam's Two point method, Fano inequality and Assouad, other approaches use packing number. Is there a "...
- 53
-2
votes
1
answer
60
views
What is really the difference between membership queries and "querying in i.i.d?
I'm struggling at finding the difference between algorithms that use i.i.d random queries then request their labels and algorithms that use membership queries.
Membership queries allow the learner to ...
- 122
0
votes
1
answer
102
views
Confusion about lower bounds and upper bounds in learning theory
In computer science, lower bounds and upper bounds are defined as follow:
$$m \geq g(n) \implies m = \Omega(g(n))$$
$$m \leq g(n) \implies m = \mathcal{O}(g(n))$$
However, in proving lower bounds and ...
- 53
0
votes
0
answers
92
views
Relationships between problem symmetry and its complexity
I read once that the more a problem has some symmetries the "easier" it is to solve and in particular its (time) complexity is polynomial.
Conversely, when starting from a polynomial problem,...
- 9
-1
votes
0
answers
26
views
Finding an algorithm EF[1,1] and PO division for more than two agents
From this research paper I want to write an algorithm for finding envy-freeness(EF) and Pareto optimality(PO) division for more than two agents.
We consider the problem of fairly and efficiently ...
- 99
2
votes
2
answers
433
views
Technical limitations of Turing machines due to the input and output encoding of values
Convention: Since I will be asking about some technicalities around Turing machines, it behooves to give a precise definition: say, here, “Turing machine” will stand for a $2$-symbol $1$-tape machine ...
- 619
1
vote
1
answer
100
views
Balanced set coloring
Let $\{S_1, S_2, ..., S_m\}$ be a collection of subsets of some universe $U$, where each $S_i$ has even size (so does $U$).
We want to color the elements of $U$, either red or blue, such that each $...
- 356
-1
votes
0
answers
50
views
Average case complexity of decision version of NP-hard problem
I am a bit confused regarding the average case complexity of certain graph problems that are NP-hard like graph coloring, clique, dominating set and whose decision version is NP-complete. It is ...
1
vote
0
answers
39
views
what are some Lower bound for finding large fourier coefficients of boolean function (above a threshold)?
Is there some known lower bounds for estimating large fourier coefficients of boolean functions? And were there any comparison of tightness with the upper bound of Goldreich Levin algorithm?
- 53
4
votes
1
answer
142
views
Connection between strong normalization of the simply typed λ-calculus, and cut elimination for propositional logic
What is the precise connection between:
strong normalization of the simply typed $\lambda$-calculus, and
cut elimination for (intuitionistic) propositional logic (limited to implication) in “sequent ...
- 619
1
vote
0
answers
63
views
Crafting ${NP}^{\#P}$-complete problems
Some related posts:
Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$?
$\mathsf{NP^{PP}}$ vs $\mathsf{P^{PP}}$
I needed a complete problem for the class ${NP}^{\#P}$ for a reduction to show the hardness of some other ...
- 11
2
votes
0
answers
42
views
Variable opening in locally-nameless representation
Although similar to a previously unanswered question, my query focuses on a different aspect of normalization. I'm trying to adjust the proof of strong normalization of STLC, given in Jeremy Avigad's ...
- 121
0
votes
0
answers
16
views
Any value in a formula that calculates (not look up) the 'order' of a 'Independent Edge Set' OR a 'I.E.S.' given an 'order' on complete graphs?
Any value or interest in a formula that calculates (not look up) the 'integer order' of a given 'Independent Edge Set' OR given an 'Independent Set' calculates the 'integer order' on Complete Graphs? ...
- 1
3
votes
1
answer
169
views
What’s the complexity of this decision problem with bit shifting?
I’ve been wondering about the computational complexity of a problem that involves bit shifting.
Let me define some notation before I present the problem.
If $\langle{b}\rangle$ is a bitstring ...
0
votes
1
answer
59
views
Learning positive half-lines (in $\mathbb{N}$)
The second section of these notes points explains how one might PAC learn the concept class of intervals of all positive half-lines in $\mathbb{R}$. If we restricted our attention to $\mathbb{N}$ ...
- 21
2
votes
2
answers
81
views
Learning with zero inductive bias
I want to understand the intuition behind the classic setting of learning theory, we always assume that the model belongs to some known class. Was there a formal proof that we can or can not learn a ...
- 53
2
votes
0
answers
21
views
Hardness of 3-Partition with Small Target Value
In the 3-partition problem, we are given a set of positive integers $a_1,\ldots,a_n$ and a target value $T$; the goal is to decide if there is a partition of the numbers to triplets such that the sum ...
- 173
6
votes
0
answers
64
views
Updating (minimal) DFA incrementally
Is there algorithm to incrementally update (minimal) DFA? Namely, having relatively large minimized DFA I want to update it incrementally using union and sudtraction with other (relatively small, ...
- 421
3
votes
1
answer
344
views
Intuition on Lupanov's Upper Bound on Circuit Size
The following result, by Lupanov, is a classic in the theory of Boolean function complexity:
Theorem: For every boolean function $f$ of $n$ variables:
$$C(f) \leq (1 + \alpha_n)\frac{2^n}{n}, \text{ ...
- 133
2
votes
0
answers
38
views
Does Goldreich-Levin algorithm for finding large Fourier coefficients have time complexity upper bound = sample complexity upper bound?
I'm currently working on finding better bounds for Goldreich-Levin algorithm for estimating large Fourier coefficients of a boolean function.
I was surprised seeing that the upper bounds for time ...
- 53
0
votes
0
answers
16
views
What is the condition under which the estimation error increases (logarithmically) with hypothesis class size for a finite hypothesis class
In section 5.2 error decomposition (p.404) from the online book "Shai et al., Understanding Machine Learning: From Theory to Applications", the authors wrote:
As we have shown, for a finite ...
- 131
0
votes
0
answers
40
views
Computability of Time Complexity of Recursive Sets
Is every recursive set's worst-case time complexity a total recursive function?
1
vote
1
answer
78
views
Learning arithmetic series
Let us say that an arithmetic series is a series of the form $s_t = \{0, t, 2t, \ldots\}$. For example, $s_3 = \{0, 3, 6, \ldots\}$. Now consider the concept class composed of all arithmetic series of ...
- 21
4
votes
1
answer
102
views
Lower bound for constant degree monotone arithmetic circuits
Do we know an explicit constant degree polynomial that requires monotone arithmetic circuits of size $n^{10}$?
- 891
-4
votes
2
answers
120
views
Why is it impossible to prove software to be correct?
I heard that computer programs can't be proved to be correct, only tested. Could anyone explain to a math student who knows logic and how to prove theorems in mathematics that why is this impossible? ...
- 3
-1
votes
0
answers
38
views
What are the prerequisites for reading the book "Understanding machine learning: from theory to algorithms"
The book mentions
"the reader is assumed to be comfortable with basic notions of probability, linear
algebra, analysis, and algorithms"
I am a graduate in electronics engineering. I have ...
