texts: Bringing rigor into discussions. Do we have a crowd-sourced sytematic reasoning system?

texts:
I am looking for ways to crowd-source systematic reasoning behind common and uncommon convictions, beliefs, science principles, software or product design, political views, etc. Today, discussions on such topics happen in both formal & informal media, like newspapers, blogs, emails, scientific literature, e-groups, etc. Such discussions use the tools, style and expressions of natural language and are also hugely diverse in presentation.

The disadvantage of this type of discourse is that the rigor behind a certain claim cannot always be evaluated easily. It's fairly complex to figure all the missing pieces, unstated assumptions, specious logic, etc.

The best case would be a system that can auto-derive conclusions, figure out contradictions, incompleteness, unsoundness, etc. but that's probably too far at this point. For a start am looking for a simple system that would allow me to represent Boolean statements like: "z is true iff (x OR y) is true", etc., along with axioms that one declares true. The statement themselves could just be in a natural language form.

Such a system would help in rigorously representing scientific answers like for "Why is the sky blue?", convictions like "Why should I homeschool my child?", "Why is the US dollar not a good bet in the long run?", "Why is climate change caused by human activity?", "Why does C++ have to do this?", etc.

As you'd see many of the above questions come with too many points & counter points to be rigorously represented in regular forums. In most cases it's just different axioms that drive disagreeing parties away from each other. Calling out axioms explicitly simplifies the evaluation of an argument.

The system am looking for would be able to present a claim with finality like: "Given the following axioms/assumptions, the statement .... is true.".  It would also be able to represent the chain of reasoning as appropriate.

A simple vision for such a system is to represent short statements (restricting perhaps to a tweet-like length of 144 chars), their truth-value condition (as a Boolean expression) and the axioms to start out with.

Do we have such systems/websites available? Thoughts?


texts:
I'm interested in the basic amplification procedure for QMA: the prover sends $O(r)$ copies of his witness to the verifier, which decreases the error probability to $2^{-O(r)}$ (Chernoff bound). The only difficulty is to show when $x \notin \mathcal{L}$ that the prover will not gain anything if he entangles the copies. There are complicated proofs of this result (see [KW00],[KSV02]), but I have also seen one-line proofs that use convexity. See these lectures notes from Aaronson from instance:

  Now what if Merlin sends witness states that are entangled with each
  other? By convexity, some pure state $|\psi\rangle$ maximizes the probability that
  Arthur accepts. Even after Arthur has performed an experiment on a
  register, Merlin can hope for nothing better than for the next
  register Arthur acts on to contain $|\psi\rangle$. But then, why not just put the
  unentangled state $|\psi\rangle$ there? So, entangling registers doesn't win Merlin anything.

I don't understand the convexity argument here. Assume that the acceptance probability is given by $||\Pi |\psi\rangle ||^2$ for some projector $\Pi$. I know that $||\cdot||^2$ is convex but I don't see how to use it here. For instance, if $|\psi\rangle = \sum_i \alpha_i |\psi^i_1\rangle \otimes \cdots \otimes |\psi^i_r\rangle$ for orthogonal unit vectors $|\psi^i_1\rangle \otimes \cdots \otimes |\psi^i_r\rangle$ (thus $\sum_i |\alpha_i|^2 = 1$) we would like to have $||\Pi |\psi\rangle ||^2 \leq \sum_{i,j} |\alpha_i|^2 \cdot ||\Pi |\psi^i_j\rangle ||^2$ but this is not what convexity means...


texts: What is complexity of this max-edge subgraph problem?

texts:
While discussing the question I had asked here, @NealYoung and I encounter another problem, which is to judge complexity of the problem below:

  Given a connected undirected graph, finding a maximum-size subset of
  the edges such that every vertex has degree at most two.

I have found some paper on complexity of relative problems. Most of them added more constraint on the original one. FOS03 added "with no odd cycles" and proved that it is NP-hard. CTW07 implied that the variant added "with no 3-cycle" is P referring to another paper (which I failed to find). But I have been unable to judge complexity of the original problem. So how to judge it? Thanks.


texts:
It is well known that we can compute:
$$
a^e \mod m
$$
in $O(\log e \log ^2 m)$ bit operations (assuming multiplication $nm$ in $O(\log n \log m)$ time) via exponentiation by squaring. I am wondering if there is a way to compute:
$$
a^e \mod p^n
$$
for some prime $p$, in time better than $O(\log e\ n^2 \log ^2 p)$, given by the above method. Such a technique could be combined with the chinese remainder theorem to obtain an efficient algorithm to compute $a^e \mod m$ when the prime factorization of $m$ is known.


texts: Help needed on method to use for anomaly detection

texts:
I think people here could guide me in solving a problem related to anomaly detection. The term anomaly here refers to some malware attack.

I could get information about the malware infection from more than one source. For example extracting value from two different data strututres and if the value is different it is certain that virus infection is there.

In order to remove the false positive cases, information is gathered from different data strutres or mechanisms. In that certain information are less trusted and certain information are more trusted.

I am looking for a mathematical method, that could easily handle this type of situations?

Update 1:

Its applied in Linux Kernel for detecting some kind of anomalies. But the problem is that if the kernel is affected you cant trust anyone. But "some" behavior can tell you that anomaly is there. But some others not

Update 2:

Current models mainly depends on archived copy of the system before infection and then compare it with the new state. I am looking for some other method like

(1) Certain variables cant be accessed by a normal module
(2) Information given by command should match
(3) Module code didn't have any jmp instructions often

In these (3) is allowed to some extent. But (1) is disallowed. The (2) should certainly match.

Hope now things are clear.


texts: Reasons for which a graph may be not $k$ colorable?

texts:
While reasoning a bit on this question, I've tried to identify all the different reasons for which a graph $G = (V_G,E_G)$ may fail to be $k$ colorable. These are the only 2 reasons that I was able to identify so far:

$G$ contains a clique of size $k+1$. This is the obvious reason.
There exists a subgraph $H = (V_H, E_H)$ of $G$ such that both the following statements are true:

$H$ is not $k-1$ colorable.
$\exists x \in V_G - V_H\ \forall y \in V_H\ \{x,y\} \in E_G$. In other words there exists a node $x$ in $G$ but not in $H$, such that $x$ is connected to each node in $H$.

We can see the 2 reasons above as rules. By recursively applying them, the only 2 ways to build a non $k$ colorable graph which does not contain a $k+1$ clique are:

Start from a cycle of even length (which is $2$ colorable), then apply rule 2 for $k-1$ times. Note that an edge is not considered to be a cycle of length $2$ (otherwise this process would have the effect of building a $k+1$ clique).
Start from a cycle of odd length (which is $3$ colorable), then apply rule 2 for $k-2$ times. The length of the starting cycle must be greater than $3$ (otherwise this process would have the effect of building a $k+1$ clique).

  Question

  Is there any further reason, other than those 2 above, that makes a graph non $k$ colorable?

$\ $
Update 30/11/2012

More precisely, what I need is some theorem of the form:

  A graph $G$ has chromatic number $\chi(G) = k + 1$ if and only if...

Hajós calculus, pointed out by Yuval Filmus in his answer, is a perfect example of what I am looking for, as a graph $G$ has chromatic number $\chi(G) = k + 1$ if and only if it can be derived from axiom $K_{k+1}$ by repeatedly applying the 2 rules of inference of the calculus. The Hajós number $h(G)$ is then the minimum number of steps necessary to derive $G$ (i.e. it is the length of the shortest proof).

It is very interesting that:

The question of whether there exists a graph $G$ whose $h(G)$ is exponential in the size of $G$ is still open.
If such $G$ does not exist, then $NP = coNP$.


texts: Has anyone studied "polynomially compact" metric spaces?

texts:
A subspace $S$ of a metric space $A$ is compact if it is complete and totally bounded. Here, complete means that every Cauchy sequence in $S$ has a limit also in $S$. For $S$ to be totally bounded,  we must have for every radius $r$, that there is a finite set $U$ of open balls of radius $r$ whose union covers $S$.

I would like to know if anyone has studied spaces where the size of $U$ is bounded by a function of $r$ -- for example, where $U(r)$ is $O(\frac{1}{r}^k)$ for some $k$.

The reason I am curious is that I am investigating models of reactive programming (ie, stream functions), where boolean streams are given the Cantor metric (two streams have a distance of $2^{-n}$ when the first position at which they differ at time $n$), and programs between streams are interpreted by functions continuous with respect to this metric. While the continuity requirement functions nicely capture causality requirements very well, it unfortunately also permits stream functions to require their whole history to compute a value (that is, functions $f(x)$ may require their whole history $x_0, \ldots, x_n$ to compute $f(x)$ at time $n$).

One idea I have for understanding this phenomenon is that the Cantor space is compact, and that at radius $2^{-n}$ you need $2^n$ balls to cover the space -- that is, there are $2^n$ length-$n$ binary sequences. So I have a vague idea that if somehow there were a way of equipping the Cantor space with an even coarser metric, I could model computations which are permitted to remember less of their input. (Eg, a polynomial bound would permit you to use space logarithmic in the elapsed time.)


texts: Is every recursive language recognized by a mortal Turing machine?

texts: We say that a Turing Machine $M$ is mortal if $M$ halts for every starting configuration (in particular, the tape content and initial state can be arbitrary). Is every recursive language recognized by a mortal Turing Machine? (i.e. if there is a TM that accepts $L$, there is also mortal TM that accepts $L$)


texts: What's the “smallest” complexity class for which an $\omega \hspace{.02 in}(n)$ circuit lower bound is known?

texts:
I believe the answers to this question give classes such that for all polynomials $p$,

there is a problem in the class which does not have circuits of size $p(n)$.

However, I'm asking about circuit size $\omega \hspace{.02 in}(n)$.

$\big(\hspace{-0.07 in}\left\langle \hspace{-0.04 in}0^{\hspace{.02 in}0}\hspace{-0.03 in},\hspace{-0.04 in}1^{\hspace{-0.03 in}1}\hspace{-0.03 in},2^{\hspace{.02 in}2}\hspace{-0.04 in},\hspace{-0.03 in}3^1\hspace{-0.04 in},\hspace{-0.03 in}4^4\hspace{-0.03 in},\hspace{-0.03 in}5^1\hspace{-0.04 in},\hspace{-0.03 in}6^{\hspace{.03 in}6}\hspace{-0.03 in},\hspace{-0.03 in}7^1\hspace{-0.03 in},\hspace{-0.03 in}8^8\hspace{-0.03 in},\hspace{-0.03 in}9^1\hspace{-0.03 in},...\hspace{-0.05 in}\right\rangle \:$ is super-linear but not $\omega \hspace{.02 in}(n)$.

Although such even-odd behavior could be handled by padding, one might instead

have extremely long streaks of super-polynomial values between low values.)


texts:
I've been reading a bit of the literature lately, and have found some rather interesting data-structures.

I have researched various different methods of getting update times down to $\mathcal{O}(1)$ worst-case update time [1-7].

Recently I begun looking into lock-free data-structures, to support efficient concurrent access.

Have any of these worst-case $\mathcal{O}(1)$ update-time techniques been used in the implementation of lock-free data structures?

I ask because; to me, they seem like the obvious practical extension of this "theoretical enhancement".

Tarjan, Robert Endre. “Updating a Balanced Search Tree in O(1) Rotations.” Information Processing Letters 16, no. 5 (1983): 253 – 257.
Driscoll, J R, N Sarnak, D D Sleator, and R E Tarjan. “Making Data Structures Persistent.” In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, 109–121. STOC  ’86. New York, NY, USA: ACM, 1986.
Levcopoulos, C., and Mark H. Overmars. “A Balanced Search Tree with O(1) Worst Case Update Time.” Acta Inf. 26, no. 3 (November 1988): 269–277.
Fleischer, Rudolf. A Simple Balanced Search Tree With O(1) Worst-Case Update Time
Dietz, Paul F, and Rajeev Raman. “A Constant Update Time Finger Search Tree.” Information Processing Letters 52, no. 3 (1994): 147 – 154.
Lagogiannis, George, Christos Makris, Yannis Panagis, Spyros Sioutas, and Kostas Tsichlas. “New Dynamic Balanced Search Trees with Worst-case Constant Update Time.” J. Autom. Lang. Comb. 8, no. 4 (July 2003): 607–632.
Brodal, Gerth Stølting, George Lagogiannis, Christos Makris, Athanasios Tsakalidis, and Kostas Tsichlas. “Optimal Finger Search Trees in the Pointer Machine.” J. Comput. Syst. Sci. 67, no. 2 (September 2003): 381–418.

FYI: This is a reposting of Lock-free, constant update-time concurrent tree data-structures?


texts:
If you go to FFFFOUND! and click on some image you will notice that on the new page, under the image, there is a section called "You may like these images." which suggests 10 images that look similar to the original.

What would be a good algorithm to achieve this functionality for a collection of images?

Any documentation, books, etc. related to such algorithms is very appreciated. Also algorithms for finding similar images that yield better results than those seen on FFFFOUND! website are also welcome.


texts: Importance of ACM/IEEE in TCS conference

texts:
Recently I was in an ACM supported conference.
During the banquet, the conference organizers told us about the future and past of the conference. They told us that during the 2010 edition of the conference there was a loss of 5000$.

They showed us the budget of the previous conference where we could see that there were 8000$ (10% of the budget if I remember correctly) given to ACM. Maybe because I am not yet fully in the field (I am starting my PhD in september 2011), I was the only one to ask what was this money given for. The answer I got was really disappointing, apparently the main contributions of the ACM was to print the proceedings and to give advice so the next year there would not be such a loss (apparently the advice given was to raise the entry fees).

I was really surprised, since in order to read the proceedings your university has to pay a subscription to ACM (correct me if I am wrong), I thought ACM (is it the same for IEEE?) had to pay to support the conference.

So my questions are:

What does ACM really bring to a conference?
Have you heard of other conferences where this is the case?

Related Blog posts:
Freedom to Thinker and Matt Blaze's post, apparently the question was already asked.


texts: Data structures for embedded simplicial complexes

texts:
I am looking for a data structure to encode an $n$-dimensional simplicial complex with an embedding in $\mathbb{R}^{n+1}$. I am aware of combinatorial maps, which generalize rotation systems of planar graphs, and generalized maps which further generalize combinatorial maps to allow for non-orientability.

From Wikipedia, a combinatorial map is defined as an $(n+1)$-tuple $(D, \beta_1,\dots,\beta_n)$ such that:

1) $D$ is a finite set of darts,

2) $\beta_1$ is a permutation on $D$,

3) $\beta_2, \dots, \beta_n$ are involutions on $D$,

4) $\beta_i \circ \beta_j$ is an involution if $i + 2 \leq j$.

Here's my understanding of the definition. The set $D$ should contain $n+1$ darts for each $n$-simplex as this is the natural generalization of a half-edge in a planar rotation system. The permutation $\beta_1$ describes the cyclic order in which the $n$-simplices are incident to a common $(n-1)$-simplex. The involutions $\beta_2,\dots,\beta_n$ allow you to move from one $(n-1)$-simplex to another along a common $n$-simplex, which generalizes the one involution needed to define the half-edges in a planar rotation system.

I don't understand what condition 4 is used for, however Wikipedia states that it is included to "fix constraints which guarantee the topological validity of the represented object: a combinatorial map represents a quasi-manifold subdivision."

Here are my questions about this data structure:

1) Are my interpretations of conditions 1-3 correct?

2) What is the geometric interpretation of condition 4?

3) Can a combinatorial map be used to encode any orientable embedded simplicial complex, or just quasi-manifold subdivisions?

4) What is a quasi-manifold subdivision?

5) Why does the definition of a combinatorial map fail for non-orientable complexes?


texts: What if an $\mathsf L$-complete problem has $\mathsf{NC}^1$ circuits? More generally, what evidence is there against $\mathsf{NC}^1=\mathsf{L}$?

texts:
Edit: let me reformulate the question in a more specific way (and change the title accordingly). A slightly edited version of the original question follows.

Is there a result comparable to the Karp-Lipton theorem starting from the assumption $L\in\mathsf{NC}^1/\mathsf{poly}$ with $L$ an $\mathsf L$-complete language (under, say, $\mathsf{AC}^0$ reductions)?  By "comparable" I mean that it derives non-trivial consequences (perhaps considered unlikely) from the assumption.

I am having trouble finding in the literature (or online) a discussion of the relationship between $\mathsf{NC}^1$ and logarithmic space going beyond "the former is included in the latter and it is open whether the inclusion is strict".  More specifically, I could find only two three pieces of evidence against equality of the two classes:

Barrington's theorem and the characterization of non-uniform deterministic logspace in terms of branching programs gives us $\mathsf{NC}^1/\mathsf{poly}=\mathsf{L}/\mathsf{poly}$ iff bounded-width polysize branching programs are as expressive as arbitrary polysize branching programs, which I guess would be highly surprising (especially considering how surprising Barrington's theorem itself is).
Markus Holzer [Hol02] proved that $\mathsf{NC}^1/\mathsf{poly}=\mathsf{L}/\mathsf{poly}$ iff one-head two-way non-uniform deterministic finite automata have the same expressive power whether they are oblivious or not ("oblivious" means that the movement of the head during the computation depends only on the length of the input, not on the input itself). Oblivious polytime Turing machines do have the same power as non-oblivious ones, but I guess it is hard to see how that simulation may be done in the much more restricted framework of finite automata.
Edit: there is a paper by Allender et al. [ABCDR09] in which a number of reachability problems for certain classes of graphs are shown to be hard for $\mathsf{NC}^1$ under $\mathsf{AC}^0$ reductions, whereas the same problems are not known to be hard for $\mathsf{L}$. As stated by the authors, "this gives a cluster of natural problems that are candidates for having complexity intermediate between $\mathsf{NC}^1$ and $\mathsf{L}$".

Besides the above points and the usual empirical evidence ($\mathsf{L}$-complete problems do not seem to have logarithmic-depth bounded fan-in circuits), is there any other evidence against $\mathsf{NC}^1=\mathsf{L}$?

[Hol02] Markus Holzer. Multi-head finite automata: data-independent versus data-dependent computations. Theor. Comput. Sci. 286(1):97-116 (2002).

[ABCDR09] Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta and Sambuddha Roy. Planar and Grid Graph Reachability Problems. Theory Comput. Syst. 45(4):675--723 (2009).


texts: Geometric picture behind quantum expanders

texts:
(also asked here, no replies)

A $(d,\lambda)$-quantum expander is a distribution $\nu$ over the unitary group $\mathcal{U}(d)$ with the property that: a) $|\mathrm{supp} \ \nu| =d$, b) $\Vert \mathbb{E}_{U \sim \nu} U \otimes U^{\dagger} - \mathbb{E}_{U \sim \mu_H} U \otimes U^{\dagger}\Vert_{\infty} \leq \lambda$, where $\mu_H$ is the Haar measure. If instead of distributions over unitaries we consider distributions over permutation matrices, it's not difficult to see that we recover the usual definition of a $d$-regular expander graph. For more background, see e.g.: Efficient Quantum Tensor Product Expanders and k-designs by Harrow and Low.

My question is - do quantum expanders admit any kind of geometric interpretation similar to classical expanders (where spectral gap $\sim$ isoperimetry/expansion of the underlying graph)? I don't define "geometric realization" formally, but conceptually, one could hope that purely spectral criterion can be translated to some geometric picture (which, in the classical case, is the source of mathematical richness enjoyed by expanders; mathematical structure of quantum expanders seem to be much more limited).


texts: Is nonuniform $\mathsf{TC^0}$ equal to the composition closure of $\mathsf{AC^0}$ and Majority?

texts:
D.A.M. Barrington, N. Immerman and H. Straubing show in their 1990 paper
"On Uniformity Within $\mathsf{NC^1}$" that
the uniform $\mathsf{TC^0}$ is equal to $\mathsf{FOM}$
($\mathsf{FO}$ plus Majority quantifiers).

Is a similar result known for the nonuniform case?
I.e. is it known that any $\mathsf{TC^0}$ function can be obtained by composing Majority and (nonuniform) $\mathsf{AC^0}$ functions?

It seems this should be true since $\mathsf{AC^0}$ is closed under restrictions of inputs (replacing an input with $0$ or $1$) and the evaluation problem for $\mathsf{TC^0_d}$ circuits is in (uniform) $\mathsf{TC^0}$.

Clarification and Motivation:
By composing I mean the usual composition of functions,
i.e. the composition of $g(\vec{y})$ and $\vec{f}(\vec{x})$ is
$h(\vec{x})=g(\vec{f}(\vec{x}))$.
Consider the smallest set of functions containing the Majority function and $\mathsf{AC^0}$ which is closed under composition.
In the uniform case this gives uniform $\mathsf{TC^0}$.
If I am not making a mistake,
the evaluation problem for $\mathsf{TC^0_d}$ circuits ($\mathsf{TC^0_d}$-Eval) is in uniform $\mathsf{TC^0}$ and
therefore in this set by [BIS88].
I think this is enough since
we can get any function in $C\in\mathsf{TC^0_d}$
by composing a simple $\mathsf{AC^0}$ function with $\mathsf{TC^0_d}$-Eval:
given input $\vec{x}$ the $\mathsf{AC^0}$ function computes
$(\vec{x}, \langle C \rangle)$,
where $\langle C \rangle$ is a fixed string encoding the circuit $C$.
This $\mathsf{AC^0}$ function composed with $\mathsf{TC^0}$-Eval
computes the same function that $C$ does.
But this argument uses [BIS88] and
I feel that the nonuniform case should have an easier well-known direct proof.
The reason this is interesting is that $\mathsf{TC^0}$ is not known
to have any complete problem w.r.t. many-one $\mathsf{AC^0}$ reductions.
But for many purposes this characterization of $\mathsf{TC^0}$
as the composition closure of Majority+$\mathsf{AC^0}$ (if correct)
seems to be as good as
having a complete problem w.r.t. many-one $\mathsf{AC^0}$ reductions.


texts: a geometric variant of k-medians. NP-hard or in P?

texts:
The following problem is a special case of k-medians.  Is it NP-hard?  Is it in P?
Input: $n$ points $(x_1,y_1), (x_2,y_2), \ldots, (x_n, y_n)$ with each $y_i \ge 0$, and an integer $k$.
Output: a set $S$ containing $k$ of the given points, of minimum cost, defined as $\sum_i d((x_i,y_i), S)$, where
$$ d((x_i, y_i), S) = \min\big(y_i, ~\min\{ y_i - y_j : j \in S \,\wedge\, y_j \le y_i \,\wedge\,|x_i - x_j| \le 1 \}\big).$$
I think of this as each point "falling" vertically just until it either (a) reaches the x-axis, or (b) is aligned horizontally with, and at distance at most 1 from, one of the $k$ chosen points.  The goal is to choose the $k$ points to minimize the total distance fallen by the remaining points, as shown below.  (The input is on the left, a solution with $k=3$ is on the right.  The cost of the solution is the total length of the dashed vertical lines.)

$~~~~~~~~~$
$~~~~~~~~~~~~~~~~~~~~~~$ input  $~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$ solution with $k=3$


texts: Surveys on pseudo-random number generator design?

texts: I am interested in generation of pseudo-random numbers for cryptography. Besides Chapter 5 of Menezes/Oorschot/Vanstone; Chapter 8 of Stinson; and Chapter 3 of Goldreich, where else could I find more? I'm interested in general principles for designing PRNGs (desirable properties, tests, etc).


texts: I need a book on Mu-Calculus with lots of examples that can be used for self-study and preparation for exams.


texts: What is the current "state-of-the-art" solver for quadratic knapsack problems?

texts:
New to this forum, so please let me know if my question format is incorrect.

For linear KP with $n$ items and $c$ capacity, dynamic programming can find exact solutions in $\mathcal{O}(nc)$. I have seen some results extending dynamic programming to approximate solutions to the QKP link giving a lower bound within 0.05% of true solutions in $\mathcal{O}(n^2c)$.

Does there exist an algorithm giving at least as accurate results in at least as good time?


texts: Boltzmann sampling for containers/dependent polynomials?

texts:
I’d like to randomly sample from dependently-typed data structures.
Has anyone looked at extending Boltzmann sampling to containers or dependent polynomials?


texts: Does this bin packing problem have a name?

texts:
My problem is related to the standard bin packing problem (where you have bins of capacity $1$, items of capacity $(0,1]$, and want to pack the items into as few bins as possible), but there are a couple of twists. First, you have a fixed number of bins, and want to fit as many items as possible into them. As far as I can see, this is not obviously equivalent (except for the decision versions of the problems). Or perhaps I’m missing something obvious?

Second, some items are not permitted in some bins. That is, for each item, there is a list of forbidden bins.

Does this problem have a name? Even a name for the version without the forbidden bins would be useful. (I’m sure the “as many items as possible” part must be a totally standard packing problem?)

What I’m ultimately looking for is a way of attacking the problem (an exponential, exact DP algorithm; an approximation algorithm; a good heuristic/B&B solution…), or some starting-point that could be adapted.


texts: Why do equalities between complexity classes translate upwards and not downwards?

texts:
Hey Guys, I understand that the padding trick allows us to translate complexity classes upwards - for example $P=NP \rightarrow EXP=NEXP$. Padding works by "inflating" the input, running the conversion (say from say $NP$ to $P$), which yields a "magic" algorithm which you can run on the padded input. While this makes technical sense, I can't get a good intuition of how this works. What exactly is going on here? Is there a simple analogy for what padding is?

Can provide a common sense reason why this is the case?


texts: Can modern SAT-Solvers utilise the symmetry of First Order Logic?

texts:
Apologies if the question is trivial or is wrongly stated, I am a Physicist!
Assuming that we have a universally quantified first-order logic sentence, all variables are universally quantified, defined over a finite domain $\mathcal{D}$. Then what are the most efficient ALL-SAT (algorithms that enumerate all models of a formula) algorithms in literature? In my understanding, DPLL and CDCL  based algorithms have no way of discerning symmetries which would be inherent to a grounded FOL formula.
Trivial Example:
Let the domain $\mathcal{D} = \{a,b\}$
$$\forall x F(x)$$
Then the grounding of this sentence is,
$$F(a)\land F(b)$$
So the brute force idea would be to just check all $2^{\#ground atoms}$ assignments and in this case, only {F(a): True , F(b): True} is the model. But obviously this is a trivial example, if we ground the formula for more complex sentence then, do SAT-solvers solve this as just another propositional case or are there methods to use the "symmetry" from the First Order sentence?


texts: Number of distinct differences of $\omega(\sqrt{n})$ integers chosen from $[n]$

texts:
I encountered the following result during my research.

  $$\lim\limits_{n\to \infty} \mathbb{E}\left[
\frac{\#\{|a_i-a_j|,1\le i,j\le m \}}{n}
\right] = 1$$
  where $m=\omega(\sqrt n)$ and $a_1,\cdots,a_m$ are chosen at random from $[n]$.

I am looking for a reference/a direct proof.

Crossposted on MO


texts: Obtaining the Axiom of Choice through a modality in HTT

texts:
In (constructive) homotopy type theory, the law of excluded middle is not derivable. Moreover, assuming parametricity it is refutable.

But, one can work inside the double negation modality to obtain (a form of) the law of excluded middle.

The question now is, can the same be done to obtain the axiom of choice? To be exact, is there a modality M such that the type $\Pi x : A. \|\Sigma y : B. R(x, y)\| \to M \|\Sigma f : A \to B. \Pi x : A. R (x, f(x))\|$ is inhabited?


texts:
It is known thanks to Immerman and Szelepcsényi that ${\rm NSPACE}(f)={\rm coNSPACE}(f)$ if $f=\Omega(\log)$ (even for non-space constructible functions).

In the same paper, Immerman state that the logspace alternating hierarchy collapses, this means that $\Sigma_j{\rm SPACE}(\log)={\rm NSPACE}(\log)$ (the definition of the bounded alternating turing machine and of what is a hierarchy can be found on wikipedia).

Is there any paper about the alternating space hierarchy  for  $f=\Omega(\log)$ ? I asked last week to Immerman who did not remember reading anything like that. In english I would want to know if there is any written proof that using any language that can be decided by a Turing Machine with $j$ alternations can also be decided by a non deterministic turing maachine with the same space bound.

My question is really about finding a reference, because I think I figured out the proof; but I guess that it may already be known.

Maybe I should state what I think are the two main problems. First if $f=O(n)$, let's say $f=\log^2$, then it is impossible to compose to $SPACE(f)$ TM to obtains a $SPACE(f)$ TM, which we could do with $\rm{LOGSPACE}$ TM. Secondly, there is one argument for the case $f=O(n)$ and one for $f=\Omega(n)$ but there is still some problem for fonction which are neither $O(n)$ nor $\Omega(n)$.


texts:
Suppose $f:\{0,1\}^n \to \{0,1\}$ is a function such that it can be computed by a circuit of size $n^c$ for some constant $c>0$.

  Q. Is there any nontrivial upper bound on the depth of a circuit of size quasi-polynomial or subexponential computing $f$?


texts: Impredicativity + large eliminations (with no excluded middle) in Coq

texts:
It is known that impredicativity + large eliminations + excluded middle is inconsistent. Prop is impredicative and consistent with excluded middle, but does not allow large eliminations (except when constructing witnesses whose type lives in Prop). Set and Type(i) allow large eliminations and are consistent with excluded middle, but are predicative. If we use the -impredicative-set flag, then Set is impredicative, but does not allow large eliminations for large inductive types.
Is there a universe in Coq which is impredicative, allows large eliminations on any inductive type that lives in it, but is consistent in the absence of the axiom of excluded middle?


texts: Correctness proof of recursive-descent recognizer

texts:
Let G be a grammar that contains no left-recursive rules, and we use a recursive-descent recognizer that uses full backtracking, using list of results for example, to recognize strings of G.

How can someone show formally that if s is a sentence in G, then R(G), which is the
recognizer I just described for G, can recognize s, and it also explores all the paths, i.e., if there are two paths to recognition, both can be explored.


texts:
I'm stuck with trying to implement the Gilmore-Lawler bound procedure for the quadratic assignment problem (QAP). That is, a bound one can use with a branch and bound algorithm to solve the QAP. I'm gonna explain what I've understood about it and I'd like anyone who knows on the topic correct me, or tell me if I'm right.

As far as I know it's an optimistic (better than any of the possible outcomes) for a given partial solution for the QAP. I'll put it in terms of facilities and locations (which is what I've seen used mostly).

Let's say at a given moment we've assigned m of the n facilities to m locations. From the solution space of the m-n locations that need to be assigned, one can calculate an optimistic bound which corresponds to the sum of three terms.

The first term is the cost of what we already have assigned, so we just calculate the cost for the fist m terms as if the problem was just a smaller one.

For the next two we'll consider each of the pairs of unassigned facilities and unassigned locations, so more formally, each pair (f,l) with f and l in {m-n..n}.

For each pair (f,l) we'll determine the contribution of making that assignment to the total cost of the problem. I've been told that doing this for all pairs of (f,l) corresponds to an (n-m)x(n-m) matrix M1 = (m_fl) with m_fl being the cost (objective function) of a m+1 QAP, with the same distance and flow matrices and m assignments and the m+1th asignment being (f,l).

Also, for each pair (f,l) we'll determine the cost of making that assignment in regards to all the unassigned facilities and locations. We'll define another matrix M2 = m2_fl. To calculate m2_fl let's define two vectors vd and vf, the first it's the vector that corresponds to the distance from l to all the other unassigned locations. The second it's the vector that corresponds to the flow from f to all the other unassigned facilities. Now, m2_fl it's the result of the minimal scalar product of vd and vf —That being the scalar product of vd and vf sorted in opposed orders—.

Now, let's consider the matrix M = M1+M2, and objective value of the linear assignment problem associated to M, which we'll denote by c. Knowing that we can say that the Gilmore-Lawler lower bound to that particular partial sollution is the first term added with c.

Now, I want to know if I am right. It makes sense to me, I've ran some examples by paper and they make sense to me. But papers on this are too complicated, or just trying to improve this bound and not bothering on explaining it to a begginer. So it's really difficult to just know if I'm doing the right thing. I also tried to get the first article written by Gilmore (also the Lawler's one) which would tell the original method but none of them both seems to be free to read.


texts: Proof of undecidability not by reduction from the halting problem

texts:
The usual way of proving undecidability is by reduction from a RE-complete problem such as the halting problem, validity in first order logic, satisfiability of Diophantine equations, etc.

It is known that there are recursively enumerable, but undecidable problems that are not RE-complete, but these are artificial constructions (that is, sets that have been defined just for showing this "density" result).

How would one tackle proving undecidability without reduction from a RE-complete problem? Diagonalization?


texts: Calculating the instantaneous period of a wave

texts:
I have a set of data which represents slightly imperfect waves of varying amplitudes and periods. I wish to calculate the instantaneous period of the wave around any point within this data set - simply finding the local minima and maxima representing each individual wave and calculating the frequency of these is not precise enough for my needs.

Is there a known algorithm that can achieve this? Even better, an existing implementation of this algorithm? I am currently programming in R, but am willing to switch if needed.

n.b. if this is the wrong StackExchange site for this question, please direct me to a better one.


texts: What would be the next step after quantum computing?

texts:
Is their anything that would make Quantum computing obsolete in the future? I know a Matrioksha Brain is the most powerful theoretical computer; but it probably won’t ever be realized. Too large and hard to build. I know about hypercomputing but again that seems also too far-fetched.

So let’s say quantum computing becomes mainstream. What would be the next upgrade?


texts: Brute force search algorithm for semidefinite programming (representation of spectrahedron)

texts:
I was wondering if there exists a brute force search algorithm for semidefinite programming problems. Specifically, can we find finite number of points in the positive semidefinite cone such that for any objective, we can get a good approximation by searching over these finite points?

In a linear program, the answer is positive; we can search over all the vertices of the constraint, which is a convex polytope.

This question is closely related to the representation of a spectrahedron, which is the intersection of the PSD cone with planes or half-spaces. Specifically, if the spectrahedron is finite representable, then we can search the values of the objective over the basis of the representations.


texts: How many exponentiations can the Shamir algorithm reduce?

texts:
The Shamir's algorithm is depicted as follows (cited from

Handbook of Applied Cryptography, chapter 14, algorithm 14.88, page 618)

Shamir's algorithm

INPUT: group elements $g_0,g_1,\dots, g_{k-1}$ and non-negative $t$-bit integers $e_0,e_1,\dots, e_{k-1}$.

OUTPUT:$g_0^{e_0}g_1^{e_1}\dots g_{k-1}^{e_{k-1}}$

Precomputation. For $i$ from 0 to $2^k-1$: $G_i \gets \Pi_{j=0}^{k-1}g_j^{i_j}$ where $i=(i_{k-1}\dots i_0)_2$.
$A\gets1$
For $i$ from 1 to $t$ do : $A \gets A$, $A \gets A \cdot G_{I_i}$
Return($A$)

I wonder; how many exponentiations can the Shamir algorithm reduce? That's to say, usually it needs $k$ exponentiations to compute $g_0^{e_0}g_1^{e_1}\dots g_{k-1}^{e_{k-1}}$; however if we use the algorithm in the above, then how many exponentiations does it amount to when calculating $g_0^{e_0}g_1^{e_1}\dots g_{k-1}^{e_{k-1}}$?

P.S. Actually, this question appears in here. I think it's more proper to ask in this section. However, as I'm a newer I cannot flag or delete this same question from https://crypto.stackexchange.com/.  I'm sorry to do this..


texts:
Is there simple reduction Dominating Set to Vertex Cover?

In the other direction the reduction is simple.

Searching the web returned blog.

It warns This is not finished yet and experiments suggest
the reduction doesn't work.

Added by "simple" I mean graph transformation
$G \to G'$, s.t. $G$ has DS of size $k$ iff $G'$
has VC of size $f(G,k)$ and the transformation
does not depend on $k$ (to avoid reduction to SAT).


texts: What do we know about $\text{P}^\text{NE}$

texts:
I have a $\text{NEXP}$-hard problem, that can be solved by a $\text{NEXP}^\text{NP}$ algorithm using a single oracle call.
So from Hemaspaandra we know it is in $\text{P}^\text{NE}$, giving us
$\text{NEXP}$-completeness under Cook-reductions.

Are there (more or less) natural problems complete for $\text{P}^\text{NE}$?
What do we know about the space between $\text{NEXP}$ and $\text{P}^\text{NE}$?
Anything else that might help to sharpen this result (to Karp-reductions)?


texts: Is anything nontrivial known about the class $\mathrm{CFL}\cap \mathrm{coCFL}$? In particular, is it known whether $\mathrm{CFL}\cap \mathrm{coCFL} = \mathrm{DCFL}$ (certainly the reverse containment is obvious.)? I hope I'm not being stupid here--don't laugh at me too much if this is totally trivial. I ask this because I'm trying to pin down a commutative closure of a regular language over a binary alphabet, and it's clear that it lies inside this set, via a result showing that slip-languages over an alphabet of size two have context-free commutative closure.


texts: Maximum resistor with sublinear number of measurements

texts:
Consider a set $X = \{x_1, \dots, x_n\}$ of positive real numbers (or natural numbers, if you like) to be a set of resistors. For any subset $S \subset X$, we can build resistive circuits and measure the resistance between any two points in a circuit. Is it possible to determine (or even just verify) the maximum number in $X$ (i.e. $\arg\max_i x_i$) with fewer than $n$ measurements? (It is trivial to get $n$, just measure each resistor individually.)
(A resistive circuit is a connected graph $G = (V, E)$, where each edge has a resistance $r(i, j)$, here we ask that $r$ is a bijection between $E$ and some subset $S \subset X$. A measurement between $s, t \in V$ involves inputting 1 unit of current at $s$, which uniquely determines potentials $p(i)$ for every $i \in V$ by physical laws, and the effective resistance $\tilde{r}(s, t)$ between $s$ and $t$ is $|p(s) - p(t)|$ by Ohm's law. So in other words, we are allowed to read $< n$ numbers from the (finite) set $\{\tilde{r}(s, t) : S \subset X, (G, r)$ is a resistive circuit with $r$ a bijection between $E$ and $S$, $s, t \in V\}$. For more details, please see any book about network flows, in particular electrical flows.)
For an easier variant, restrict the resistive circuit to be a series circuit. Then there is only one way to measure each subset $S \subset X$, in particular, by taking the sum of the elements, so we are reading $< n$ numbers from the set $\{\sum_{x_i \in S} x_i : S \subset X\}$.
Is anything known about this problem? Lower bounds, randomized solutions, approximation algorithms, interactive proofs, etc. are all welcome, if relevant.


texts: Separation of classes with different amounts of advice?

texts: The time hierarchy theorem lets one show that, for example, there are problems in P that cannot be solved in time less than const*n^2 by a Turing machine.  But give the Turing machine some advice and all bets are off.  One can't yet show that even a linear size circuit can't solve all of PSPACE.  So, what if we try to compare two different classes in which both have advice?  For example, can one separate polynomial space with logarithmic advice from linear time with linear advice?  That's just a made-up example question, I am wondering what general results there are along these lines.


texts: An edge orientation procedure to generate all acyclic orientations of a graph

texts:
Consider the following scheme for enumerating acyclic digraphs (DAGs) by orienting the edges in an undirected graph $G$ with $n = ||V||$ vertices:

(1) Generate all $n!$ possible permutations $p_i$ of the $n$ vertices in $G$.

(2) For each permutation $p_i = (v_a, v_b, ..., v_n)$, direct any unoriented edges adjacent to $v_a$ away from $v_a$, then direct any oriented edges adjacent to $v_b$ away from $v_b$ (if edges were previously oriented, and perhaps pointing towards $v_b$, leave those oriented edges unperturbed), and so on for all successive vertices in the permutation up to $v_n$.

(3) Check if the resulting acyclic digraph generated in step (2) is an existing element of some (initially empty) list $L$.  If not, add it to the list.

Now my question is --- will $L$ contain all possible acyclic orientations of the initially undirected graph $G$, or might we miss some?  If the latter is possible, can we say anything in particular about the nature of these missed acyclic digraphs?

(Just to be clear, by no means am I suggesting that the above procedure is an efficient way to generate sets of acyclic digraphs!)


texts:
I want to prove that the following optimization problem is NP-Hard.

max $\prod_{i = 1}^{N} \frac{\left[\sum_{j =1}^M x_j \mathcal{R}_{ij}\right]^2}{ \sum_{j=1}^M x_j}$

subject to

$x_j \in \{0,1\}\text{  } \forall j$

$\sum_{j=1}^M x_j \le T$

given

$R_{ij} \in \{0,1\}\text{ } \forall i,j$

As you can see the expression is quite unwieldy, and there does not seem to be any clear way to proceed with the reduction. I tried variants of Knapsack (which seemed closest), as well as other standard reductions but nothing seems to work very easily. The fractional form of the expression, combined with the product makes it quite hard to do reductions. Any help is appreciated!


texts: Circuit's with gate computing only "simple" functions

texts:
I was curious if something like that is known or was studied.

Let's call a function simple if it is computable by $AC_0$ circuit of depth $\leq d$ and size $\leq n^k$ for fixed $k,d$.

Now let's consider general circuits: gates are $\{\vee,\wedge,\neg\}$ of fun-in at most $2$, no depth restrictions.

Let's call a circuit nice if in all gates it computes only simple functions. That immediately implies that if a function is not simple it can not be computed by a nice circuit.

My question is: do we know some simple function that is not computable by linear-size nice circuit? How about other definitions of simple or different models, like arithmetic circuits?


texts: Is there an $\mathcal{L}$-theory and a formula $\phi$ for which Kolmogorov(proof($\phi$)) $<$ Kolmogorov($\phi$)?

texts:
Are there a complete decidable $\mathcal{L}$-theory, a formula $\phi$ and a proof of $\phi$ for which the Kolmogorov complexity of the proof of $\phi$ is less than the Kolmogorov complexity of $\phi$?

Proofs in the proof systems I have seen so far are of the form:

mathematical reasoning
therefore $\phi$

Hence our intuition tells us that the Kolmogorov complexity of the proof has to be at least the Kolmogorov complexity of $\phi$. But this intuition does not prove any statement formally and it does not exclude the possibility of having a proof system where $p$ would be a proof of $\phi$ while Kolmogorov($p$) < Kolmogorov($\phi$) or even Kolmogorov(mathematical reasoning concatenate $\phi$) < Kolmogorov($\phi$).


texts:
A simple (though somewhat pedantic) question: when using big O notation in a sentence, should it be preceded with "a" or "an"?  Example:

  The extra loop results in a/an $\mathcal{O}(N)$ increase in cost.

The ubiquitous Cormen textbook notes on page 47:

  For a given function $g(n)$, we denote by $\mathcal{O}(g(n))$ (pronounced “big-oh of g of n” or sometimes just “oh of g of n”)

which would seem to indicate "a" should precede something pronounced "big-oh".  Later on the same page, however, the textbook uses the phrase "an $\mathcal{O}(n^2)$ upper bound."   Which is used more in the literature?  It seems like a triviality, but as someone working on the edge of theoretical computer science from a primary focus on another field, I'd like not to sound like an outsider.


texts: In System F à la Church, can we automatize type inference for the for-all elimination?

texts:
The question is the following. Generally when one have a term like $\Lambda X.t$, we can eliminate the forall by applying this term to a type, as instance $(\Lambda X.t)[T]\to t[X:=T]$.

Now, suppose this is an arrow and we want to give it an argument, then we would need to apply this term to the proper type such that it can receive such an argument. That is what I am asking if I can automatize: Is it possible to construct a function $f$ taking two terms and returning a type such that
$f<{\Lambda X.t}><{r}>$ give us the type needed to be replaced by $X$ in $t$ such that $t$ can accept the argument $r$?

Some examples:

$f<{\Lambda X.\lambda x^{X\to X}.t}><{\lambda x^T.x}>=T$.
$f<{\Lambda X.\lambda x^X.r}><{(\lambda x^{R}.t^T)~s}>=T$


texts: Max flow with restriction of individual flows

texts:
What is known about the complexity of solving max flow with restrictions on individual flows for some nodes?

More precisely, in addition to wanting the max flow, you have a constraint for some vertices $S\subset V$ where $\forall s \in S, \forall u\in \{u | (u,s) \in E \} , f(u,s) \leq \frac{1}{2} \sum_{u} f(u,s) $

Meaning no one edge contributes more than half the total flow into a node.

Also, the flows must be integral [and the capacities are integral]


texts: Does $\textbf{PCP}[poly(n), O(1)] = \textbf{coRP}$?

texts:
Something has been buzzing me recently. It is well-known that $\textbf{PCP}[poly(n), 0] = \textbf{coRP}$, but does $\textbf{PCP}[poly(n), O(1)] = \textbf{coRP}$ ?

I have found a proof for this statement but something feels wrong about it. Here it goes :

Let $L \in \textbf{PCP}[poly(n), O(1)]$. There is a verifier $V$ for $L$ which flips $poly(n)$ random coins and reads $q$ bits from the certificate, where $q$ is a constant.

The proof query of $q$ bits can return $2^q$ possible values. My idea is to build a $\textbf{coRP}$ algorithm $V'$ for $L$ by simulating $2^q$ copies of $V$, where each copy is given a different answer to the certificate query. $V'$ accepts if at least one of the copies of $V$ accepts.

If the input is in $L$ then there exists a certificate so that $V$ accepts with perfect completeness. The queried bits from that certificate are necessarily in our $2^q$ possible values, so at least one of the simulated copies of $V$ accepts with perfect completeness.

If the input is not in $L$, then all copies have probability < 1 of accepting. Thus $V'$ has some probability $\rho < 1$ of accepting.

Using amplification, we can then boost $\rho$ to $\frac{1}{2}$ to match the definition of $\textbf{coRP}$.

Is this proof correct ?


texts: Minimizing a submodular function given noisy oracle access

texts:
Let $f\colon 2^{[n]} \to \mathbb{R}$ be a submodular function (one can assume $f$ is bounded, if this helps). We are given noisy oracle access to $f$: on any $S$ and for any $\tau > 0$, one can obtain an additive $\tau$-approximation of $f(S)$ (at cost $\operatorname{poly}(1/\tau)$).

I am interested in what is known in minimizing (up to some arbitrary (additive) accuracy $\alpha>0$) $f$, given this sort of access:

If we had exact oracle access, then this could be done in polynomial time, exactly; what about robustness to approximate queries? Is there any algorithm (or, on the other side of the spectrum, lower bounds) for it?


texts: What is the running time of taking a limit?

texts:
I'm interested in finding the running time(s) for determining mathematical limits.

For instance, $\lim_{x \to 2} \frac{1}{x} = \frac{1}{2}$.

I'd like to know more about algorithms for determining mathematical limits such as this, and I'm primarily concerned with the runtimes of such algorithms.

If it helps, there are only certain types of limits that I'm concerned with.

Specifically, I'm concerned with limits of one variable.  I'm also really only concerned with rational functions of polynomials.  For example, given two polynomials $p(x)$ and $q(x)$, I'm interested in finding the limit $\lim_{x \to 1}\frac{p(x)}{q(x)}$.

There is additional information that should greatly help.  I only really want to find the limit as $x$ approaches 1.  Further, the limit itself is bounded $-O(2^n) \leq \lim_{x \to 1} \leq O(2^n)$.

The function $p/q$ itself is actually a description of a polynomial with powers at most $O(2^n)$, and coefficients $c_i \in {-1, 0, 1}$.

This may not be the best method, but I'm essentially trying to sum the coefficients of a polynomial.

  An Additional Interest

I'm also interested in expanding the problem to include limits of rational functions of multiple polynomials, i.e. polynomials $p_i(x)$ and $q_j(x)$ to find:

$\lim_{x \to 1}\frac{\prod_{i=0}^m{p_i(x)}}{\prod_{j=0}^n{q_j(x)}}$

Note that the polynomials $p_i(x)$ and $q_j(x)$ are very sparse in this representation, consisting of no more than 2 terms.


texts: Are there any counterintuitive results in theoretical computer science?

texts:
Some math and logic paradoxes could be automatically applied to computers probably, but are there any paradoxes that were discovered in computer science itself?

By paradoxes I mean counter intuitive results that look like a contradiction.


texts: What are the simplest turing-complete systems?

texts: Lambda Calculus is very simple. Are there even simpler turing-complete systems? Which is the simplest of them all?


texts: How to do Type Inference using an SMT solver?

texts:
I understand that Hindley-Milner Type Inference can be implemented using an off-the-shelf SMT (Satisfiability Modulo Theories) solver?

How would this work, for example for a very simple type system (just primitive base types and function types, no polymorphism, no subtyping, no nuthin')?


texts: What is the fastest algorithm known for factoring polynomials with $n$ variables and total degree $\leq d$? Here, $n$ is growing and $d$ is fixed. Most work seem to consider the case when $d$ is growing and $n$ is fixed. I am interested in results both over finite fields and over rationals.


texts: Can Scheme's call/cc implement all known control flow structures?

texts:
The page "Advanced Scheme: Some Naughty Bits" states:

  Continuations are a powerful control-flow construct from which
  nearly any other control-flow structure [...] may be derived.

I thought that Scheme's call/cc, being related (*) to Peter Landin's J operator, could be used to implement any known control flow structure?

With "control flow structure" I'm specifically thinking about Wikipedia's description of them, e.g. exceptions, coroutines, green threads and so on.

Specifically, are there any examples of control flow structures that cannot be implemented using call/cc?

(*) I haven't been able to dig up any paper that establishes that call/cc is as powerful as the J operator.  A paper by Felleisen (which I haven't read and admittedly have problems understanding it fully) investigates this, and seems to conclude that even though they are in different complexity classes, they are formally equivalent.

(Also note that I have updated the question based on the comments below)

Update

Based on the excellent answer by @Neel below, I've looked at sites commenting on delimited and undelimited continuations, and it does indeed seem that while call/cc, being undelimited, is not sufficient. Meanwhile, first-class, delimited continuations (like shift/reset) can be used, it seems, to express any control-flow structure.


texts: Patience Sort+ ping pong merge implementation

texts: A recent paper out of Microsoft Research describes a new, faster implementation of the patience sort algorithm.  A key part of the implementation is an improved merging strategy dubbed the "ping-pong" merge.  I am confused as to why this merge strategy uses two arrays to perform the merging, instead of just using a single array and always performing a "blind merge" as described in the paper.  It seems that always performing blind merges, and thus only using a single array to perform the merge, would cut down memory usage with no change in runtime.


texts: Rank-robustness of the parallel complexity of linear algebra problems

texts:
It is known that most computational problems related to linear algebra
can be computed in $NC^2$ - i.e. for an $n\times n$ matrix $A$, over the reals
or a finite field, we can compute the rank of $A$, $\det(A)$ or $A^{-1}$, etc. in parallel time $O(\log^2(n))$.

The complexity of these linear-algebra problems remains the same (i.e. in $NC^2$) even if the rank of $A$ is say $n^{\epsilon}$ for some small constant $\epsilon>0$ (just by padding zeros)
but what happens to the complexity of these problems when $A$ has very small rank, i.e. $r = rank(A) \leq \log(n)$?

Clearly, if $A$ is ${\it given}$ to us as a full-rank matrix of dimension $n \times r$ then the complexity drops:
Consider for example the problem of determining whether $A x = b$ for inputs $A,b$ over $\mathbf{F}_2$ for some vector $x$.

One can simply enumerate over all possible column subsets of $A$, and compute $x$ in constant parallel time ($ACC^0[2]$).
However, the problem is that we do not posses such a succinct description from the input.
Naively, trying to brute-force enumerate over all possible column combinations of size $\log(n)$ results in time ${n\choose \log(n)}$ which is quasi-polynomial.


texts: Getting started with Hashing for Information retrieval

texts:
I  recently finished my bachelors and now work on Cross-lingual language  search. I want to get started in hashing and see how they are useful  in information retrieval. (Yes, I know what hashing is), but there are so many methods and all of them  sound  pretty fascinating,  so it will be awesome to have a list of resources, which can be referred to,  starting from absolute newbie level to the current state-of-the art.

Please don't refer me to something like a Knuth because while Knuth is pretty awesome, it is not what i am looking for.


texts: Matrix-convexity of inverse of the cofactor matrix

texts: Consider the matrix-valued function $f(A) = \frac{A}{\det(A)}$ on the set of $3\times 3$ positive-definite matrices. Is this function matrix-convex ? (i.e., Is $tf(A) + (1-t)f(B) - f(tA+(1-t)B)$ positive definite $\forall \ t \in [0,1]$?)


texts: Squash type vs Propositional truncation type

texts: Homotopy type theory has a notion of propositional truncation type. It seems to me that it's strongly related to a notion of squash types. (See https://www.cs.kent.ac.uk/people/staff/sjt/TTFP/ttfp.pdf p. 265). It seems that squash types have serious problems with definitions (see the book), and prop. trunc don't. Why this is so? What are these problems? (The book mentions them, but I can't  understand well what they are, they have an example for subtypes but, AFAIU it doesn't apply to squash types).


texts: Open Problems About Nowhere-Dense Classes of Graphs

texts:
I'm writing a survey about nowhere-dense graphs. I would like to list some of the main open problems in the field. In particular I would like to list problems of the following form.

The problem has been shown to be efficiently solvable (meaning in polynomial time, FPT time, XP time, depending on the context) on the "largest" proper sub-classes (such as bounded expansion, excluded minor, etc) but it is not known to be solvable efficiently (poly time, FPT time, XP time, depending on the context) on general nowhere-dense classes of graphs.

Until now, every problem I found that can be solved efficiently on the "largest" proper subclasses has been shown later to be solvable efficiently for nowhere dense graphs. But I'm sure that I'm missing some references.


texts:
I have just read on the German Wikipedia that an infinite graph is a graph with an infinite number of nodes or an infinite number of edges. I only know applications and algorithms for finite graphs.

What are infinite graphs good for?

What are applications of those? I can't imagine algorithms that would work on infinite graphs, as you can't store an infinite graph. So you can't operate on it.


texts: Toy Examples for Plotkin-Shmoys-Tardos and Arora-Kale solvers

texts:
I would like to understand how the Arora-Kale SDP solver approximates the Goemans-Williamson relaxation in nearly linear time, how the Plotkin-Shmoys-Tardos solver approximates fractional "packing" and "covering" problems in nearly linear time, and how the algorithms are instantiations of the "learning from experts" abstract framework.
Kale's thesis has an excellent presentation, but I find it very difficult to directly jump into the abstract framework, and I would prefer to start from an example of a simple problem for which it's absolutely obvious what to do, and then move to more general problems, progressively adding "features" to the algorithm and to its analysis.
For example:

How does Plotkin-Shmoys solve the linear programming relaxation of unweighted vertex cover? Weighted vertex cover? Set cover? Bipartite matching?
What is the simplest example in which the Arora-Kale algorithm is doing something interesting? How does it compute the largest eigenvalue of the Laplacian of a graph?

(Computing the largest eigenvalue of the Laplacian is equivalent to the problem of solving a weaker version of the Goemans-Williamson SDP relaxation of Max Cut, in which, instead of requiring each vector to be of length one, you want the sum of the squares of the norms to be |V|.)


texts:
The starting point of this question is the observation that the smallest positive integers $a,b,c$ satisfying

$$\frac{a}{b+c} + \frac{b}{a+c} + \frac{c}{a+b} = 4$$

are absurdly high. This leads to the following general question: Is the set $C\subseteq {\mathbb N}$ defined by $$ C = \left\{n\in\mathbb{N}\setminus\{0\}: \big(\exists a,b,c \in\mathbb{N}\setminus\{0\}\big):\frac{a}{b+c} + \frac{b}{a+c} + \frac{c}{a+b} = n\right\}$$
computable?


texts: Ramification of An Impredicative Type Theory

texts:
Most type theories that I'm aware of are predicative by which I mean that

Void : Prop
Void = (x : Prop) -> x

isn't well-typed in most theorem provers as this pi type belongs to the same universe as Prop and it isn't the case that Prop : Prop. This makes them predicative and disallows impredicative definitions like the above. However, an awful lot of "blackboard languages" such as System F or CoC are in fact impredicative. In fact, this impredicativity is vital to defining most of the constructs not included primitively in the language.

My question is why would one wish to give up impredicativity given it's power in defining logical constructs? I've heard a couple people remark that impredicativity screws up "computation" or "induction" but I'm having trouble finding a concrete explanation.


texts: Is there any book on the philosophical implications of Theoretical Computer Science?

texts: I find some books about computers, but all of them are about technology. I want something more linked to theory.


texts:
i'm trying to find an algorithm
that will divide my graph in 2 parts by telling me what connections should be broken
but the 2 parts should contain about the same number of nodes

its for a practical problem that i'm implementing. the graph will never have more then 64 nodes.

edit

this will be applied to a 64 nodes graph every time the program runs.
the connections have distances from 0-90, where 90 is far apart

the described algorithm sounds good
is it an existing one? can you get a link to pseudo code?
or should i try implementing it myself ^^


texts: Combining multiple time-based datasources with different periods

texts:
I have two time-based data sources (one providing data by month and the other by week) that must be combined to create a third daily source (recognizing that at best we're getting one possible projection of those two data sources).  To make things really interesting, they do not cover entirely the same timeframe (the monthly stops at the most recent month end at least 45 days ago, while the weekly data covers only the last six weeks).  The main issue (for me) is addressing the days where the two datasources overlap.

Not looking for someone to give me a fish, but for some papers on how to fish (actually, I hate fishing).


texts: Time complexity of d-dimensional convex hull

texts:
Consider the convex hull problem in $\Re^d$:

  Input: a list of $n$ points $S$ in $\Re^d$,
  Output: the vertices of the convex hull of $S$.

What is the best lower bound on the time complexity of the
$d$-dimensional convex hull problem?


texts: Choosing a research topic using game theory

texts:
This recent game theory question got me thinking (this is a tangent, of course): Is it possible to efficiently optimize a personal strategy for choosing research questions to work on using game theory?

In order to head towards a formalization of the question, I'll make the following (informally stated) assumptions:

I equally "enjoy" any particular problem available for me to work on (in order to avoid the "soft" (and correct!) answer of "Do what you like!").
I may or may not be successful at finding an answer to any given problem I choose to work on. For any given problem, I have some estimate of the probability of how good I will be at solving a problem (after investing time in it).
My goal is to maximize my payoff when being evaluated down the line (applying for a job, applying for tenure, applying for a fellowship, etc.), which is a function of how many problems I solve and how important or hard the problems are. I do not have a clear idea of the exact payoffs per problem, but I can make a reasonable estimate.
There is a loose inverse relationship between problem payoff and problem difficulty. Another statement of my goal is to "game" the differences (i.e. look for "low-hanging fruit").
An instance of this overall problem is specified by a list of research questions (possibly infinite in number), to which I firmly attach (at no computational cost; it's given as input) an estimate of the question's worth and the question's difficulty. I am playing this game against an adversary (the person evaluating me); nature decides, given the probability of me solving a given problem, whether I solve it successfully after I choose to attempt it.

In an effort to really formalize what's going on (and sidestep uninteresting or argumentative/discussion-type responses), I will view this problem as an extensive-form game with incomplete information with an infinite action set.

Question: I assume games of this type are not efficiently computable. However, is there a polynomial time algorithm to approximately maximize my payoff? What about a PTAS?

Or, alternatively, is there a more accurate game-theoretic model for this problem? If so, the same question holds: Can I (approximately) maximize my payoff efficiently? If so, how?


texts: How do I construct an optimal affix code?

texts:
An affix code is a code that is simultaneously a prefix and suffix code. That is, no codeword is neither the prefix nor the suffix of any other codeword. Affix codes can be instantaneously decoded in both directions (forward and backward).

I want to create one that optimally compresses a given input symbol distribution, given a set of output symbols.

The Huffman algorithm (which creates prefix codes) comes closest, but due to its greedy strategy, it seems unsuitable for modification to this purpose.

How can optimal affix codes be found?


texts: Single author papers against my advisor's will?

texts:
I am a third year PhD student in an area of theoretical CS that would like advice for a difficult situation with my advisor.

My advisor is not involved in my research projects at all. In particular, I have come up with all of my paper ideas, and have executed the papers alone. However, she always insists on adding her name as a co-author. This has started to increasingly bother me, as I work very hard (alone) on my research and believe I should get credit for that. In addition, she is a bully and treats me quite badly, so it makes it even harder for me to benefit her in this way.

For my most recent paper, I brought up how I didn't believe she was meeting the IEEE 1 or ACM 2 guidelines for authorship, and told her that I believed I should be sole author on my paper. She agreed that she shouldn't be an author, although she was visibly angry. She said that I was a "weirdo" for doing this, and said that everybody already knows that advisors take credit for their student's work and that publishing with your advisor is the same as publishing alone. But most importantly, she told me that she would not approve my proposal/dissertation if I did not add her name to several more top-tier papers because then I "have no ties to the university" since I am not working with a professor, and therefore cannot receive my PhD.

Obviously, I need a new advisor. However, there is really no one in my department in my research area. Switching research areas or departments are not options. So the remaining options are the following:

(1) Add her name to several more papers. I do not like this idea because it is unethical, and there is no guarantee that anything is even gained in this option. She could simply refuse to recommend me in the end after I got her a bunch of papers.

(2) Ignore her threats, and force my way to finishing my PhD while publishing single author papers. I do not believe she could stop me from graduating since I already have a decent publication record, and presumably will continue getting my work out. I have a fellowship, so she can't control my funding. Clearly, I will not have a letter of recommendation in this case. On the other hand, I will have a bunch of single author papers.

(3) Try to convince a professor in an unrelated research area to be my advisor, emphasizing that I am independent and can do my work alone. There are a few theory professors in my dept, although they are totally different areas. I have no idea the chance of this working out.

(4) Go to the department chair and tell him the whole story, ask what to do.

What do you think I should do?


texts: Given two sets of points A and B, both in $R^d$, is there a relation between the convex hulls of A and B, i.e. conv(A) and conv(B), w.r.t. the Hausdorff distance between A and B? In other words, does the computation of the hulls for the two point sets in question pose any advantage when computing the Hausdorff distance between the point sets? Would be nice if someone could reference a paper that helps understand this relation.


texts: Is there any algorithm that can orient undirected graph G(V,E) (i.e., assign directions to edges) to achieve maximum flow in the network? Any suggestion?


texts: Complexity of minimizing monotone arithmetical formulas

texts:
Let's say that I have a multi-variate arithmetical expression $A(x_1, \ldots, x_n)$ that uses addition and multiplication operations and is also in a very simple form of sums of products, e.g., $A_1(x_1, x_2) = x_1\cdot x_1 + x_1\cdot x_2$.

Let's also say that the size of an expression is the number of addition/multiplication operators that appear in that expression. For example, size of $A_1(x_1, x_2)$ is three.

Now, I want to find another expression (also only using addition and/or multiplication) that is equivalent to the given expression $A$ and is of the minimum size. For example, formula $A_2(x_1, x_2) = x_1\cdot(x_1+x_2)$ of size two would be the answer to input $A_1$.

My question is about the complexity of finding $A_2$ from $A_1$. The decision version of this problem (does there exist such $A_2$ of size at most $k$) is obviously in NP but is it NP-complete?

If yes, then do we have any good approximation algorithm for it? Or other heuristic algorithms?

If not, what is the best known algorithm to solve it?


texts:
Being a software engineer for the most part of my life I have absolutley no idea how to start with publishing an "academic" kind of paper. During my latest research I've found an interesting algorithm for the task I've been solving (related to some calculations on financial markets). It's not some great result but I think it can be interesting for people doing the similar tasks and I'd like to publish it.

I'm of course familar with a style of research papers since I use them extensivly at my job (thanks to Google Scholar and all the good people out there) and I'm able to google for free manuals on academic writing style and how to use LaTeX and I have a lot of friends mathematicians who will check my paper and help to make it look ok.

But I have absolutely no idea what to do next! I don't belong to any academic institution or recognizable research entity, I work in a small local company, which will be happy to have its name on some paper published but this name will say nothing to anybody. I don't know anybody who is doing research in this area, I mean I've never communicated with anybody.

How can I found the right place to send paper to? Do I need some sort of recommendation or review and how and where can I try to get them? What are my steps?.. I realize that all these are absolutely obvious things for you if you are a professional sceintist but I have no idea where to start :)


texts: Proof of an Ising model representation of graph isomorphism problem

texts:
I am going to through Ising formulations of many NP problems by Andrew Lucas. In section $9$ on page 22, the author introduced an exact Ising formulation of the graph isomorphism problem. Given two gaphs, $G_1$ and $G_2$, the Ising Hamiltonian, $H$ is,

$$
H = A \sum_v \left(1 - \sum_i x_{v,i}\right)^2 + A \sum_i \left(1 - \sum_v x_{v,i}\right)^2 \\
+ B\sum_{ij\not\in E_1}\sum_{uv \in E_2} x_{u,i} x_{v,j} + B \sum_{ij \in E_1}\sum_{uv \not\in E_2} x_{u,i} x_{v,j}
$$

Here, $|G_1|=|G_2|$ and the binary variable $x_{v,i}$ is $1$ when if vertex $v$ in $G_2$ is mapped to vertex $i$ of $G_1$. For an isomorphic pair, $H = 0$.

My questions:

Is there any rigorous proof that this model is correct?
I understand that the classical computational complexity of the graph isomorphism problem is not known but it is conjectured to be NP-intermediate. On the other hand the classical computational complexity of the Ising model is well understood. So, if the graph isomorphism problem can be reduced to an Ising model in polynomial time, shouldn't be it's complexity same as the Ising model problem?
When I code it up using Mathematica (assuming $A = B = 1$) for the following two isomorphic graph pairs, I am getting false positives.

The graphs are:

 and .

For this pair of graphs, I get the following configurations which are correct isomorphisms and for them $H=0$. They are:

$x_{1,1}, x_{2,2}, x_{4,3}, x_{3,4}$
$x_{4,1}, x_{3,2}, x_{1,3}, x_{2,4}$
$x_{1,1}, x_{3,2}, x_{4,3}, x_{2,4}$
$x_{4,1}, x_{2,2}, x_{1,3}, x_{3,4}$

But when I evaluate the Ising formulation with all possible inputs using Mathematica, I get five more false positives along with these four. They are:

$x_{1,4}, x_{2,3}, x_{3,2}, x_{4,1}$
$x_{1,4}, x_{2,2}, x_{3,1}, x_{4,3}$
$x_{1,3}, x_{2,4}, x_{3,1}, x_{4,2}$
$x_{1,1}, x_{2,4}, x_{3,3}, x_{4,2}$
$x_{1,4}, x_{2,3}, x_{3,1}, x_{4,2}$

What am I missing?


texts: Framing the Count-Min Sketch as a Random Projection?

texts:
The count-min sketch data structure is used to estimate the frequencies of individual elements in a data stream. The authors note that the analysis of their data structure is simpler than other related data structures like the count sketch, technically because they're able to use Markov's inequality rather than Chebyshev's inequality, but conceptually because previous data structures are based on random projection models related to the Johnson-Lindenstrauss lemma and the tug-of-war sketch.

Has there been any work done in reframing the count-min sketch as some sort of random projection in the style of these previous data structures? Or has there been any work done showing that it's not possible to frame the data structure this way? Intuitively, I'd imagine there would be some technical difficulties involved in making this approach work because the count-min sketch is not an unbiased estimator and therefore isn't likely amenable to techniques showing that it works by embedding a higher-dimensional space inside a lower one with low distortion, but it would be interesting to see if there was a way of casting the analysis in this light.


texts: Is there such a thing as control logic complexity classes?

texts:
I am currently reading the paper "On the computational complexity of Algorithms" by J. Hartmanis and R. E. Stearns ( http://www.jstor.org/pss/1994208 )

It includes a proof that any $T$-computable sequence is also $\lceil kT \rceil$-computable, where $k$ is a computable, positive real number, $T$ a time-function and $\lceil kT \rceil$ denotes the smallest integer $m$ such that $m \ge kT$.

The proof idea is to use a (multitape) TM that has a head that can read 2 symbols at once, while storing internally the symbol to the left and right of that head, so that the new TM can simulate 2 steps of a normal (multitape) TM in only once step. By doing the same trick on the new TM using induction, one can prove 1/2k speed-up.

I have two questions, which revolve around the same thing:

First of all, can I extend this idea and use a head so large that reads the entire input at once? That would require to save a super-constant number of symbols internally in the TM. Would that be a violation of the model?
Reflecting to my first question, whatever the answer is : Are there "complexity" classes that restraint the TM's control logic somehow? e.g. allowing up to a specific number of states or for a specific structure of the automaton?


texts: randomness extraction of real valued sequences of numbers

texts:
I have a sequence of numbers $x_1, x_2, \dots, x_n, \dots \in \mathbb{R}$ I would like to extract fair bits from that sequence.

My first thought was to use the Von Neumann extractor.  For a sequence of 0 and 1,

divide sequence into pairs
eliminate all occurrences of 00 and 11
apply transformation 01 → 1 and 10 → 0

This produces a sequence of fair bits from biased bits *even if you do not know the bias $p = \mathbb{P}[x_i = 1]$ as long as your sequence is

a Bernoulli trial
independently distributed
identially distributed

The sequence of numbers I have is the hourly readings from a sensor, so it exhibits cyclic behavior every 24 hours + every week.  If I compute the expected value over time, it may be possible to subtract out the daily and weekly cycles leaving sequence of loosely self-correlated real numbers.

How can I extract randomness from here in a simple way?


texts: Integer priority queue with distribution-sensitive deleteMin

texts:
Is there in an integer priority queue that uses $O(n)$ words of space with the following operations, all in worst-case time and without access to randomness:

createEmptyQueue in $O(lg^c U)$ for some constant $c$.
insert in $O(1)$.
deleteMin in $O(\delta_{\min})$, where $\delta_{\min}$ is the difference between the smallest and the second-smallest key.

Furthermore, once a key $k$ has been subject to a deleteMin, all further inserts are $> k$.

Related work:

Bose et al.'s "Fast Local Searches and Updates in Bounded Universes", which is faster than I need for deleteMin but slower than I need for insert.

Brodnik et al.'s "Worst case constant time priority queue", which uses the exotic "Yggdrasil memory". For the purposes of this question, I'm interested in more standard integer RAM models.

Brodnik and Karlsson's "Multiprocess Time Queue", which limits insert to elements with keys in $(k_{\min}, k_{\min} + \delta_{\min}]$, where $k_{\min}$ is the value of the minimum key.

Note that this is pretty simple with a hash table, but that uses amortization and randomness:

Queues are pairs of a hash table of keys and a copy of the minimum key.
insert adds the key to the hash table and updates the minimum key copy if appropriate.
deleteMin looks up the minimum key in the hash table, then searches for the next minimum key by searching for $k_{\min} + 1, k_{\min} +2, k_{\min} + 3, \dots$ in order.


texts:
Is there a practical programming language that has an extensible type system?
Or alternatively, an add-on type system that can be used with existing languages?

With extensible I mean that the typing rules are specified externally and can be changed by the user without rewriting the typechecking code.

The use would be to add additional checkable constraints to a program (for example physical dimensions, uniqueness types, reference frames, nulled memory etc.).

In the programming language part, one would annotate the expressions with their types:

    import units # library for physical units
    # x has type float and the type meter
    x:{float,units.meter}
    y:{float,units.meter**2}
    def f(x): return x*x
    y=f(x)

(I am using Python as an example language as the semantics are independent of the optional type annotations, but any language would do)

In the above case x has multiple types: float and a physical dimension.
Each of those have different typing rules, and it makes sense to treat them differently.
In the units type library, we would provide typing rules of the following form (assuming that the rules for float are defined elesewhere):
$$\frac{\Gamma \vdash x:Meter, n:Nat, m:Nat}{\Gamma \vdash x^\frac{n}{m}:Meter^\frac{n}{m}}$$

While for example physical dimensions can be dealt with through a runtime library somewhat unsatisfactorily, doing dimensional analysis with the tools of types is much more elegant, doesn't incur any runtime overhead and proves dimensional correctness.

For example, the only mainstream language that I am aware of that provides physical dimensions is F#, but unfortunately it is broken as it does not support fractional exponents https://stackoverflow.com/questions/11333135/fractional-power-of-units-of-measures-in-f/11334159#11334159
Providing the physical dimensions as a typing library instead of a language internal would allow the user to fix this problem and add other dimensional systems, like directional units or Siano's orientational dimensions.

The annotated AST and the typing rules would be processed by a constraint solver to issue type errors and warnings for insufficiently typed expressions.

Why am I asking for this?

It would be great for understanding type systems
Existing software could be made more secure by adding extra type constraints.


texts: In the original article on R+ tree, Algorithm Insert recursively searches for all leaf nodes that overlap the given input rectangle IR and adds IR to each of those leaves. But what if part of IR is not covered by any existing leaf? How will that part ever be indexed?


texts:
A family $H$ is $(r,cr,p_1,p_2)$-sensitive if for all $x,y \in \mathbb{R}^d$ we have:

$\lVert x-y\rVert <r\quad \Rightarrow\quad \Pr[h(x)=h(y)] \geq p_1$, and
$\lVert x-y\rVert > cr \quad \Rightarrow\quad \Pr[h(x)=h(y)] \leq p_2 $

We can amplify  the gap between $p_1,p_2$ by using concatenation:
$g(x) = h_1(x)h_2(x)\cdots h_k(x)$
and $L$ tabels, so we have $g_1,\dots,g_L$

For each $\delta > 0$ we can choose $k,L$ s.t. for a query point $q$, if
$\lVert x-q\rVert <r$ then $\Pr[\exists i \: \: s.t. \: g_i(x)=g_i(q)]>1-\delta$

My question is: what guarantees do I have for the "bad" points?
Given a query point $q$, what is the ratio between good points (i.e., $r$-close or $cr$-close points) and the bad points (far points) in the bucket $g_i(q)$. Can I bound it for some (carefully chosen) $k,L$ ?


texts: To what extent, computational ability for hard tasks helps in solving easy tasks

texts:
In short, the question is: to what extent, computational ability for hard tasks really helps you in solving easy tasks. (There could be various ways to make this question interesting and non-trivial, and here is one such attempt.)
Question 1:
Consider a circuit for solving SAT for a formula with n variables. (Or for finding Hamiltonian cycle for a graph with $n$ edges.)
Suppose that every gate allows the computation of an arbitrary Boolean function on $m$ variables. For concreteness let’s take $m=0.6 n$.
The Strong exponential time hypothesis (SETH) asserts that even with such strong gates we need superpolynomial circuit size. In fact, we need size at least $\Omega (2^{(0.4-\epsilon) n})$ for every $\epsilon.$ In a sense, gates on fraction of the variables that represent very complicated Boolean functions (much beyond NP-completeness) do not give you much advantage.
We can further ask:
(i) Can we have such a circuit of size $2^{0.9 n}$? $2^{(1-\epsilon)n}$?
A “no” answer will be a vast strengthening of the SETH . Of course, maybe there is an easy “Yes” answer, that I simply miss.
(ii) If the answer to (i) is YES, do gates that computes arbitrary Boolean functions give some advantages compared to gates which “just” compute (say) arbitrary NP functions; or just smaller instances of SAT itself ?
The next question attempts to ask something similar for questions in $P$.
Question 2:
As before let $m< n$ and for concreteness put $m=0.6n$. (Other values of $m$ such as $m=n^\alpha$ are also of interest.) Consider the following types of circuits:
a) In one step you can compute an arbitrary Boolean function on $m$ variables.
b) In one step you can solve a SAT problems with $m$ variables. Or perhaps an arbitrary nondeterministic circuit of polynomial size in $m$ variables.
c) In one step you can perform an arbitrary circuit on $m$ variables of size $m^d$ ($d$ is fixed).
d) In one step you can perform ordinary Boolean gates.
Let us consider the question of finding a perfect matching for a graph with $n$ edges. Matching has a polynomial size circuit. The question is if the exponent in such a matching algorithm can be improved when you move from circuits of type d) to circuits of type c), and from circuits of size c) to circuits of size b), and from circuits of size b) to circuits of size a).
(This may be related to well-known issues about parallel computation or about oracles.)


texts: Is there any research on Turing machines with transition relation homomorphic to given algebraic structure?

texts:
A Turing machine is defined as a structure $ TM(L,Q,T) $, where $L,Q$ are sets of symbols and internal states of TM respectively, and T is a transition relation:

$T: L \times Q \to L \times Q $

for simplicity suppose that $Q$ contains all "terminal states" that is $ \{ START,STOP \} $, and information about next move of the head on the tape, that is $\{L,R\}$ - it is just another information about internal state of the machine. $L$ contain all terminal symbols. This are finite sets.

This assumptions are for simplicity and easy notation, because full definition of TM is well known, and there is no need to explain it I presume. Please take a look for other questions below where such simplification is provided in more detailed way.

$T$ is then a table with for example elements $Q$ in the column and elements of $L$ in  the rows. An element of such table is value of $T$ for its arguments that is:

$T(q_i,a_k) = (q_j,a_s)$

Suppose that there is a homomorphism between $T(q_i,a_k)$ (as table) and certain finite algebraic structure (group, monoid, algebra, possibly some exotic structure). Or suppose that such transition relation has certain symmetries (for a stupid example here let me write: $T(q_i,a_k) = T(q_k,a_i)$) or "subtables" with structure or symmetries homomorphic to given algebraic or other structure.

For given structure of $T(q_i,a_k)$,
are there any known facts about
class    of TM with that structure?
Are there any known equivalence
classes of $T(q_i,a_k)$ arising from algebraic
properties of $T(q_i,a_k)$ ?

Asking this question I follow the suggestion of  Dave Clarke. This is question related to following questions:

asked here - Turing Machine which generates order on the set of its states
asked on mathoverflow (and for which there is an answer by Joel David Hamkins) Turing Machine which generates order on the set of its states


texts: Are there any toy examples that provide 'essential' insights into understanding the three known barriers to $P = NP$ problem - relativization, natural proofs and algebrization?


texts: Analogue of $k$-wise independence for other distributions than uniform

texts:
I am looking for the name of the following notion (in order to look it up for myself), and possibly pointers to the corresponding literature.

Let $D$ be a fixed distribution over $\{0,1\}^n$, and $1\leq k\leq n$ a fixed integer. A random variable $X$ over $\{0,1\}^n$ is said to be $(k,D)$-something if all size-$\ell$ marginals of $X$, for $\ell\leq k$, match those of $D$.

In particular, for $D$ product distribution (and, in most derandomization literature I have seen, actually for $D$ uniform), this is $k$-wise independence. I am looking for $D$ non-uniform, however -- for instance, $D$ being the distribution of the $n$ bits indicators obtained when choosing a subset of $[n]$ of size exactly $n/2$.

  Does something have a name?


texts: A simplified version of card game Winner

texts:
I've asked this problem in MathOverflow, without any satisfactory answer.

Consider the following two-player game, which is a simplification of the card game called Winner.  (The following formulation was taken from a comment by Guillaume Brunerie on MathOverflow.)

There are two players A and B. Each player has a set of cards (a subset of $\{1,\dots,n\}$), visible from both players. The aim of the game is to get rid of its own cards. The first player plays any card on the table, then the other player must play a (strictly) bigger card, and so on until one of the players cannot play or decides to pass. Then the cards on the table are discarded, and the other player start again by playing any card (which will be followed by a bigger card). And so on until one of the two players run out of cards and win the game.

I want to know the best strategy for the players (if he can win).

Formal definition

Denote by $w(i,A,B)$ the configuration of the game where the set of the first player's cards is $A$, the set of the second player's cards is $B$, and the largest card on the table is $i$, where $i=0$ means that there is no card on the table.  I would like an algorithm to compute, given $i,A,B$, whether the first player has a winning strategy in configuration $w(i,A,B)$.

Formally, I would like an algorithm to compute the function $f$ defined as follows:

Let $\mathbb{Z}_n = \left\{1, 2, \cdots, n\right\}$, $\mathrm{Bool} = \left\{\mathrm{False}, \mathrm{True}\right\}$.

Function $f:\;\left\{ 0, 1, \cdots, n \right\} \times 2^{\mathbb{Z}_n} \times 2^{\mathbb{Z}_n} \to \mathrm{Bool}$

where
$$  f ( i, A, B ) = \begin{cases}
        \mathrm{False} & B = \emptyset \\
        \mathrm{True} & B \ne \emptyset \land \exists j \in A: j > i, f(j, B, A - \left\{j\right\}) = \mathrm{False} \\
        \mathrm{True} & B \ne \emptyset \land f(0, B, A) = \mathrm{False} \\
        \mathrm{False} & \textrm{otherwise}
    \end{cases}
$$

Wrong strategies

Here are some wrong strategies:

Always play the smallest card. Let $n = 3, A = \{1,3\}, B = \{2\}$, the winning strategy for player A in configuration $w(0, A, B)$ is to play card $3$. If player A plays card 1, he will lose.
Play the smallest card unless the other player has only one card.
It is a stronger strategy than strategy 1, but it is also wrong.
Only think about configuration $w(0, \{1, 4, 6, 7\}, \{2, 3, 5, 8\})$. If player A uses strategy 2, he'll lose: $1\rightarrow2\rightarrow4\rightarrow5\rightarrow6\rightarrow8\rightarrow\textrm{pass}\rightarrow3$, thus player A lose.


texts:
What are some concrete and compelling applications for estimating the volume of convex polyhedra of the sort considered in the more recent papers on random walk methods?

These papers on volume estimation mention numerical integration as one motivation. What are examples of integrals that people want to compute in practice which are very hard to compute using previous methods?  Or is there some other compelling practical application for computing the volume of a 1000-dimensional polytope?


texts: Take a NEXP-complete problem and then have the input in unary. Why is this not NP-complete?

texts:
It is known that if any unary language is NP-complete, then P=NP.

Suppose we take a NEXP-complete language with input $x$ in binary and witness $y\in\{0,1\}^{2^{poly(|x|)}}$ such that the verifying TM runs for time $2^{poly(|x|)}$ on input $(x,y)$.

Now change the problem such that $x$ is specified in unary. Let $|x|_u$ be the unary length. Now $y\in\{0,1 \}^{poly(|x|_u)}$. The verifying TM then runs for time $poly(|x|_u)$ and will deterministically output whether $y$ is a valid witness.

It seems like since the original problem was NEXP-complete, the unary version of the problem should be NP-complete. However, surely this would then imply P=NP. What am I missing? Should the witness $y$ be specified in unary too?


texts: Does requiring uniqueness of valid answers for Merlin limit the power of Arthur-Merlin protocols?

texts:
Preamble.

The complexity class AM are those problems which can be solved by a two-round interactive proof system between a prover "Merlin" and a verifier "Arthur". A problem — which tests some property of an object X — is in AM if:

For YES instances, for a random "challenge" message (of polynomial length) Arthur generates, with high probability Merlin can formulate a (polynomial length) reply which Arthur can use as evidence that X has the property;
For NO instances, for a random challenge message Arthur generates, with high probability Merlin cannot formulate any reply which can be used as evidence for the property being tested for on X.

— The class described doesn't change if we require Merlin to give a useful answer not just with high probability, but for any challenge that Arthur may issue; we might say in this case that we require Merlin's answer always to be valid for YES instances, and what Arthur tests is the validity of the answer. So if Merlin ever produces an invalid response, Arthur knows that the problem instance is a NO instance. This is the setting I'd prefer to consider.

An example is Graph Non-Isomorphism: given graphs G and H with the same set of vertex labels, Arthur can randomly select one of the graphs and produce a "scrambled" version F by permuting its vertex labels, sending a presentation of it to Merlin. If the two graphs are non-isomorphic, Merlin can identify which of G or H Arthur chose by determining whether F ≅ G or F ≅ H, and can respond by identifying which of the two F is isomorphic to. If the two graphs G and H are isomorphic, however, Merlin cannot distinguish which graph F came from, and any answer he gives can only be correct by chance. Thus, for YES instances Merlin can always send a valid response to any challenge; for NO instances any  response which Merlin might send will be with high probability invalid.

In the above problem, not only does there exist a valid response that Merlin can issue to Arthur for each challenge, but in fact there is a unique valid response: i.e. indicate which of G or H Arthur chose, given that this can be determined by identifying which is isomorphic to F.

Question.

Does imposing a constraint along these lines — that for YES instances, for any challenge Arthur might send, there is exactly one valid response for Merlin — yield a more restrictive class, in the sense of yielding a class which is not known to equal AM?


texts:
I am curious if there are graphs problems for which either -

we know that time and/or space complexity is independent of graph sparsity
we do not know whether or not graph sparsity can be exploited to reduce time and/or space complexity

Among many possible notions of the sparsity, I am particularly interested in the one that relies on edge density (or alternatively, average degree).


texts: Does this notation have a special meaning?

texts:
I am currently reading a paper and I don't know how to interpret this notation you can see on the screenshot.

http://moxn.brainex.de/pub/dfg.png

Do the pointy angle brackets have a special meaning or did the author choose them just to confuse me?

I googled it and apparently they are commonly used in group theory, which does not make much sense to me here.

Thanks for your input.

btw: The paper is called "A Formal Definition of Data Flow Graph Models" by Kavi, Buckles and Bhat, and is available here.


texts: Maximizing the number of heads in $N$ tosses by choosing which coin to toss

texts:
Assume you have two coins $A,B$ with biases $P_A,P_B$ respectively.
We would like to make $N$ coin tosses and get the maximal number of heads possible.
Unfortunately, we know $P_B$, but $P_A$ is unknown at the beginning of the process.

What is the best possible strategy for selecting which coin to toss at each step?

Note: I'm looking for actual optimization of the selection, not heuristic methods. You may assume a reasonable prior distribution on $P_A$ if needed.

EDIT:

Here is a formal definition of the objective.
Let $P_A,P_B\in (0,1)$ and $P=max\{P_A,P_B\}$. The optimal strategy in hindsight will achieve on average $P\cdot N$ head tosses.
Let $a(P_A,P_B)$ be the expected number of times our strategy picked coin $A$ given that the probabilities were $P_A,P_B$.

The Optimization Objective: minimize the expected regret, i.e. $$Regret=P\cdot N - P_A\cdot a(P_A,P_B) - P_B\cdot (N-a(P_A,P_B))$$

The Goal: Devise a selection strategy that guarantees (expected) $Regret\leq r$ for any values of $P_A,P_B$ (for the smallest value of $r$ possible).

Note that if $P_A\approx P_B$ this is not a problem in this definition as it means our regret will be small regardless of which coin we flip.

If $N$ is unknown (i.e. the process may end arbitrarily after an adversarialy chosen number of tosses), the best strategy would be to occasionally explore coin $A$ to get a better $\widehat {P_A}$ estimation, and in the rest of the time toss coin $A$ iff $\widehat {P_A} > P_B$.

In the scenario $N$ is known, it's not hard to argue that the optimal strategy makes a series of tosses of coin $A$ and then either keeps on tossing $A$ for the remaining tosses or starts tossing only coin $B$, but how can we optimize the cutoff (i.e. the switch to tossing coin $B$) to maximize the expectancy of head results?


texts: Fast Algorithm to Check if a Set of Sets forms an Anti-chain

texts: Given a set $S$ of sets, what is the fastest algorithm to check if elements of $S$ form an anti-chain with respect to subset ordering? That is, how can I quickly decide if there exists two sets $A$ and $B$ in $S$ such that $A \subseteq B$?


texts: Evidence that matrix multiplication can be done in quadratic time?

texts:
It is widely conjectured that $\omega$, the optimal exponent for matrix multiplication, is in fact equal to 2. My question is simple:

  What reasons do we have for believing that $\omega = 2$?

I'm aware of fast algorithms like Coppersmith-Winograd, but I don't know why these might be considered evidence for $\omega = 2$.

Naively, it seems to me like a classic example where a community just hopes that a result is true purely for aesthetic reasons. I would love to know if that's essentially the case here.