All Questions
12,683
questions
1
vote
0
answers
34
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
25
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
7
votes
1
answer
317
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 ...
- 599
5
votes
1
answer
130
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
75
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
65
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
47
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
113
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,086
0
votes
0
answers
39
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
402
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
53
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
-1
votes
0
answers
44
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
42
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
0
votes
0
answers
38
views
How the correctness of this construction can be proved? [closed]
We are using Myhill-Nerode Theorem algorithm and we want to prove that this algorithm gives us the minimized DFA.
So let $B$ be the minimized DFA obtained by applying the algorithm to the DFA $A$. We ...
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
122
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
63
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
58
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
97
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
23
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
427
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 ...
- 599
1
vote
1
answer
97
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
49
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
38
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
3
votes
1
answer
133
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 ...
- 599
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
15
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
2
votes
1
answer
168
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
56
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
77
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
62
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
100
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
116
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 ...
16
votes
0
answers
1k
views
Are theoretical computer science conferences losing touch with reality?
Anonymous account for obvious reasons. I am a researcher in TCS. I have several publications in SODA/STOC/FOCS. I've recently been so disgruntled with the way these conferences are run, and wanted to ...
0
votes
1
answer
30
views
Why is the estimation error smaller in Structural Risk Minimization
On p.87 in this online Understanding Machine Learning book, the authors wrote:
Unlike the ERM paradigm discussed in previous chapters, we no longer just care about the empirical risk, $L_S(h)$, but ...
- 131
1
vote
0
answers
47
views
Relation Between Different Definitions of Information Distance
I'm reading the fourth edition of An Introduction to Kolmogorov Complexity and Its Applications by Li and Vitanyi. In Section 8.3 of the book, it introduces the concept of "information distance.&...
0
votes
0
answers
97
views
Assume `P != NP`, does it imply that one-way functions exist?
I define a function f to be one-way iff for any sufficiently large x computing f(x) bounded ...
- 212
4
votes
1
answer
105
views
High-dimensional expanders through the lens of algebraic topology
High-dimensional expanders are used in a few areas of TCS (coding theory, sampling, probably some others). While I'm not too familiar with their usage, I know that in sampling they can be useful to ...
- 43
4
votes
2
answers
519
views
Do we currently know a polynomial-size Frege proof for Tseitin formulas?
There's a vast literature about super-polynomial lower bounds on proof lengths of Tseitin formulas in bounded-depth Frege systems, but what I'm curious about is: what if we don't restrict the depth of ...
- 145
1
vote
0
answers
39
views
Why the measure of information complexities for passive and active learning are increasing in research communities?
I am a PhD student working on the theory of active learning.
Over the years, accepted papers in COLT and ALT for active learning are focused on approaches that almost all of them define new ...
- 122
10
votes
0
answers
203
views
Is there a text that discusses both the “lambda cube” of pure type theories and Martin-Löf's intuitionistic type theories, and compares them?
I am lost in a maze of twisty little type theories, all different.
There are a number of works (textbooks and papers) that discuss pure type theories, and specifically the ones constituting the ...
- 599