texts: Sign patterns for Fourier coefficients of Boolean functions

texts:
Given a sequence of real numbers $(a_i)$, the sign-pattern sequence $(s_i)$ is defined by $s_i = +$ if $a_i \geq 0$ and $s_i = -$ otherwise.

For a boolean function $f: \{0,1\}^n \to \{0,1\}$, consider its Fourier coefficients defined, as usual, in the following way: $\hat{f}(\alpha) = \mathbb{E}_x[f(x)\cdot (-1)^{\langle \alpha, x\rangle}]$. Is there a characterization of the sign-pattern of Fourier coefficients of boolean functions?

Note that there are $2^{2^n}$ many boolean functions $f: \{0,1\}^n \to \{0,1\}$ and the same number of sign-pattern sequences of length $2^n$. But not all of the $2^{2^n}$ sequences can be realized. To see this, let $b$ be a bent function where each nonzero Fourier coefficient is $\pm 2^{-n/2}$, and let $b'$ be a boolean function which differs from $b$ at exactly one point. Clearly, each Fourier coefficient of $b'$ differs from that of $b$ by $\pm 2^{-n}$, so that the sign pattern of the Fourier coefficients of $b$ and $b'$ are the same.

I'd like to conjecture that the number of possible sign-patterns for Fourier coefficients of Boolean functions is at most $c\cdot 2^{2^n}$ where $c$ is a constant less than 1. But any information about signs of Fourier coefficients is very welcome.


texts: Gowers "discretized Borel determinacy" approach

texts:
Gowers has recently outlined a problem, which he calls "discretized Borel determinacy," whose solution is related to proving circuit lower bounds.

Can you provide a summary of the approach that is tailored to an audience of complexity theorists?
What would it take for this approach to prove anything, including re-proving known lower bounds?


texts: What is the fastest gradient based algorithm to get to criticality of a "nice" non-convex function?

texts:
I am allowing for the following properties for a once differentiable non-convex $f : \mathbb{R}^d \rightarrow \mathbb{R}$,

(a) Let there be a $\sigma >0$ s.t the norm of the gradient of the function is bounded by $\sigma$.

(b) Let the function's value itself be upper and lower bounded.

(c) Let the function be "L-smooth" as in for any two points, $x$ and $y$ in the domain lets say we have, $f(y) \leq f(x) + \langle \nabla f(x), y-x \rangle + \frac {L}{2} \Vert y - x \Vert ^2$

Under these conditions whats the fastest gradient based algorithm known to get to a point $x_*$ s.t $\Vert \nabla f(x_*) \Vert \leq \epsilon$ ?

I checked the old results I am aware of and the new papers that I know of but I am unable to locate any result which can exploit all these properties.
I am not sure if there is any implicit constraint between $\sigma, L$ and the bounds on the function value. Kindly let me know if something like that is getting implied!


texts: Subset of a bipartite graph with maximal number of minimal unmatched vertices

texts:
Given a bipartite graph $G = (U \sqcup V, E)$ with sets of vertices $U$ and $V$ and edge set $E \subseteq U \times V$, a matching $M$ is a subset of $E$ whose edges have no common vertices: for all $(u, v)$ and $(u', v') \in M$, $u = u'$ or $v = v'$ implies $(u, v) = (u', v')$. A maximum matching is a matching containing the maximum number of edges. It is immediate that a maximum matching is a matching achieving the minimal number of unmatched vertices, where I say that $u \in U$ is unmatched in $M$ if there is no $(u', v') \in M$ such that $u = u'$, and likewise for $v \in V$. Hence, the minimal number of unmatched vertices in $G$ over all possible matchings of $G$, that I write $f(G)$, can be computed by finding a maximum matching, which can be done in polynomial time with, e.g., the Hopcroft-Karp algorithm.

I now consider the following problem: from a bipartite graph $G = (U \sqcup V, E)$, what is the maximum, over all subsets $U'$ of $U$, of $f(G_{|U'})$? By $G_{|U'}$ I mean the bipartite graph which is the restriction of $G$ to $U'$, namely $G_{|U'} = (U' \sqcup V, \{(u, v) \in E \mid u \in U'\})$.

Is this problem NP-hard, or can it be solved in PTIME? On the one hand it seems related to set cover or exact cover which are NP-hard, but on the other hand the subproblem of maximum matching is PTIME and maybe there is a clever way to identify what is the worst subset.

To motivate this problem, here is a rephrasing in terms of assignments of agents to tasks. $U$ is a set of tasks, $V$ a set of agents, and $E$ indicates which agents can perform which tasks. A matching is a way of assigning tasks to agents such that each agent does at most one task and each task is done by at most one agent. The cost measure is the number of unmatched vertices, namely the number of undone tasks plus the number of unoccupied agents. I want to know what is my worst possible cost in this sense, over all subsets of the tasks (think of $U$ as a set of possible tasks from which an arbitrary subset will be requested, and $V$ as a fixed set of agents that I cannot adjust but which I can allocate freely once a subset has been requested).

To see why this problem is not trivial, observe that choosing the empty subset $\emptyset \subseteq U$ yields a cost of $|V|$ (the cost of leaving all agents unoccupied), the complete subset $U \subseteq U$ yields a certain cost and may be the worst if e.g. $|U|$ is much larger than $|V|$, but in general my best solution may be to choose a subset of $U$ which retains the tasks than can be done by only few agents (so that many of them will have to remain undone as each of those agents can do only one task) but would not retain the tasks that can be done by otherwise unoccupied agents (so that those agents remain unoccupied and contribute to the cost).

If this problem is in PTIME, I am also interested to know if the following weighted version is also PTIME: each vertex and each edge has a weight, the cost of a matching is the sum of the weights of the unmatched vertices plus the sum of the weights of the retained edges, and I want again to find the subset of $U$ with the worst minimal cost in this sense. In the vocabulary of the assignment problem, this means that each task and each agent has an individual cost of remaining undone or unoccupied, and assigning a task to an agent is not free anymore but carries a certain cost indicated on the edge.


texts:
The simplex algorithm is often treated either within real arithmetic, or in the discrete world with exact computations. However, it seems to be implemented most often with floating-point arithmetic.

This leads to the question whether the simplex algorithm should be regarded as a numerical algorithm, in particular how round-off errors affect the computation. I am not interested in practical implementations, but rather in theoretical foundations.

Are you aware of any research on this issue?


texts:
It is well known that lower bounds on circuits implies lower bounds on time complexity, just because circuits can efficiently simulate algorithms.

By the continuous work started by Ryan Williams, we know that upper bounds on the algorithms can imply circuit lower bounds [1].

Another connection between uniform and non-uniform complexities is that there exist algorithms that uses efficient circuits to gain a speed up. For example, first subquadratic algorithm for 3-sum [2] uses efficient decision trees.

I'm looking for results in the direction I haven't discussed yet: can lower bounds for time complexity imply lower bounds for circuit complexity. It is worth mentioning that algorithms that uses efficient circuits are taking advantage of the actual constructions rather then pure existence.

[1] Improving exhaustive search implies superpolynomial lower bounds. Ryan Williams.

[2]Threesomes, Degenerates, and Love Triangles. Allan Grønlund, Seth Pettie


texts: Where does the information in a fractal come from?

texts:
When I view a fractal such as the Mandelbrot, my first thought is, where did this interesting picture come from. For a picture of this complexity, the information that generated this picture must be stored somewhere. Then I found that the Mandelbrot is generated by computational processes based upon mathematics in the area of complex numbers.

However, my question still holds, where did the information come from? The nice picture wasn't input when the program was written, where did the information for this picture come from?


texts: Is there any algorithm outputing $e$ in real time?

texts:
The Hartmanis-Stearns Conjecture says that a number computed in real time by a Turing Machine is either rational or transcendental. We know that there is some transcendental (Liouville) number that can be computed in real time. The BBP algorithm for computing $\pi$ outputs the first $n$ digits in nearly linear time ($O(n (\log n)^c)$; linear time for this being the same as real time), so it's at least plausible that $\pi$ is real-time computable.

  Is there an algorithm outputting $e$ in  real time?


texts:
Most dependent type theories aim for some notion of correctness in two respects:

The type system must be decidable.
The type system must be consistent. e.g. $\forall \tau. \tau$ should not be provable.

The first is a topic that has been debated a bit. You could relax this requirement to semi-decidability. The second has not been debated as a desirable property but many have mentioned that $Type : Type$ would be useful for "practical" programming languages. I've become interested in what such a "practical" programming language might look like. In this question, I'll use "practical" to mean "computationally complete and not directly intended to be used for any kind of proof". The debate over whether that is a fitting definition is another topic. For instance the calculus of constructions equipped with a fixed pointer operator of type $\Pi A : Type. (A \to A) \to A$ would qualify as such a "practical" programming language. Such a language would be inconsistent but would (I think) still be type safe and computationally complete.

Additionally, most type systems have a third property, generally called "type safety." This property ensures that well-typed programs "don't get stuck" (not sure who I got that quote from). In actual practice, there is generally a way to violate type safety but I'll include in my definiton of "practical" that the language must be type safe. For such "practical" programming languages consistency is generally moot, but type safety is still a desirable property and the main property trying to be achieved in systems like System-F for instance. In such systems, the range of allowed well-typed terms is expanded as far as possible while type safety is still met. You can generally make these systems computationally complete by adding a fixed point term to the theory.

Dependent type theory almost completely blurs the line between types and terms. The remaining distinction between the two is just what types are just terms $\tau$ such that $\tau : \mathcal{U}$ where $\mathcal{U}$ is some distinguished term in the theory (or cumulative hierarchy or such). This uniformity is a very aesthetically pleasing property.

There is an analogue of fixed points over terms for types often just known as a fixed point type or $\mu$-type. Such types generally come with a "wrap" and "unwrap" terms to manipulate terms of these fixed point types. This diverges from the term level equivalent of fixed points. This, however, seems somewhat unavoidable as if you consider adding a fixed point term in a system with $Type : Type$ it doesn't actually let you make useful types like the natural numbers (but you can use it to make type familes like $Fin$ by recursion over non-type terms). The expected result there is just your type checker infinitely looping. As an example consider the type $fix \,\, Type \,\, (\lambda A : Type. 1 + A)$ as an attempt at defining the natural numbers. Unless there is some clever trick I'm missing it doesn't seem like this terminates or produces a useful type. The thought springs to my mind that if types were evaluated lazily somehow that this would be fine but I don't have a clear picture on how that should work.

Are there any works that consider semi-decidable type systems that have $Type : Type$ and allow for fixed point types to be used? Can fixed point terms and fixed point types be unified? How would one account for least and greatest fixed points of types in such a case? In a nutshell is there any literature on type safe "practical" programming languages? Ideally I'd like to see this in the case of $Type : Type$


texts: Graph traversal with vertex and edge deadlines/windows

texts:
Hello the question was also posted on stackoverflow, but since this is theoretical oriented, thought I'd give it a try. I have an undirected graph similar to the one below, I need to implement a graph traversing algorithm.
Example:
http://i.imgur.com/15L6m.png

The idea is that each vertex is a city, and each edge is a road.
The weight of an edge represents the time needed to traverse the specified edge.
The conditions are:

Each edge is open for traversal in a specified time window: Time Open1, Time Open2, TimeClose1, Time Close2 - the current time must be in these intervals in order to traverse the edge.
Only some vertices must be visited. The vertices must be visited at leas once in the specified time window for each one:  Time Open1, Time Open2, TimeClose1, Time Close2 - the current time must be in these intervals in order to mark the vertex as visited.
The starting point is always vertex 0

For my example I have:
Vertices that must be visited and their time window (values with -1 are not taken into consideration):

Vertex To1  Tc1  To2  Tc2
  1    0    260  340  770
  4    0    240  -1   -1
  5    170  450  -1   -1

Edges are open in the following time window (values with -1 are not taken into
consideration):

Edge To1  Tc1  To2  Tc2
0-1  0    770  -1   -1
0-4  0    210  230  770
0-5  0    260  -1   -1
1-2  0    160  230  770
1-5  40   770  -1   -1
2-4  80   500  -1   -1
3-4  60   770  -1   -1
3-5  0    770  -1   -1

So the basic idea is to start with vertex 0 and find the shortest route to traverse
vertices 1, 4 and 5 taking in consideration the specified time.
Also if for example you have done 0-1 but you can't use 1-5 you can do 0-1-0-1-5.

I start with vertex 0, end with one target vertex while I have visited all other target vertices at least once respecting the conditions imposed on the edges and target vertices.
For example:
A possible solution is 0 - 4 - 3 - 5 - 1 with a total time of 60+50+60+50=220
From 0 I can also go directly to 5 but as stated in conditions in order to mark vertex 5
I must have a cumulative time between 170 and 450. Also if I go 0-4 I can't use edge 4-2 because it opens at 80 and my cumulative time is 60. Note I can use 0-4-3 because 4-3 opens at 60 and to do 0-4 it takes a time equal to 60.
So is there a way to solve this using dijkstra or other path finding algorithms ?

Thanks in advance for any help!

Edit

My solution for now is something like this

         0
  1      4      5
0 2 5  0 2 3  0 1 3

Basically I try all possibilities. The conditions for stopping in expanding a branch are:
1. I have too many duplicates like I have 0 1 0 4 0 1 0 - so I stop because I have a set number of duplicate 0 values which is 4
2. I find a road that contains all the vertices to mark
3. I find a road that takes longer than another complete road


texts: Reference request: Classical analog of quantum threshold theorem

texts:
For quantum circuits, once the gate error is below a threshold, the error probability of an entire computation can be driven exponentially small with polylog costs in time and space:

http://arxiv.org/pdf/quant-ph/9611025v2.pdf

The classical version should be entirely analogous, and was presumably proven long before the quantum case.  Who proved the classical version?


texts: Suggestions on a matching/scheduling algorithm.

texts:
I have a problem where mentors need to paired with courses, this is similar to the marriage problem or the hospitals/residents problem except that it isn't. The current solution is terribly written and needs to be expanded, plus it's a monte-carlo algorithm. I want to change it to something deterministic

(I'm using weird terminology with "mentor" because my university is weird think of a mentor as a T.A.)

Courses don't "care" which mentor is assigned.
All courses must be assigned a mentor.
All mentors must be assigned one course.
No mentor may be assigned to more than 2 courses.
A mentor may not be assigned 2 courses with identical or overlapping time-slots.
Courses have 3 attributes:
time-slots (may be web-only or hybrid web/classroom)
theme
professor
faculty and/or time-slot may be TBD (too be decided)

Mentors are asked a series of questions:
rank your top 5 time-slots
rate (weight) the value of various themes from 1-7 or dont' care (don't care is the same as a 4 in the current algorithm)
rate (weight) faculty you'd like to work with from 1-7 or don't care (don't care is the same as a 4 as above)
Are you willing to mentor two courses? yes/no
Are you willing to mentor an online or hybrid course? yes/no
Are you trained to mentor an online/hybrid course.

Current system assigns a "score" to each assignment using the questions above and tries to minimize the score.

When combining assignments into a schedule, no extra weightings are added. However, some schedules are considered invalid (as above): assigning a mentor to more than 2 courses or more than 1 if they didn't select "yes" to "I'm willing to mentor 2 courses" and time-slots aren't allowed to overlap.

More complications/edge cases:
certain mentors may be pre-assigned courses. This doesn't take the mentor out of the running but it does take the course out. A mentor may be assigned to multiple courses, so there first one might be pre-assigned, but there second one cannot.
Also, some mentors are "owned" by a certain department, and so may only be allowed to teach "urban studies" courses.

Thoughts on an algorithm I should use?

Edit: for clarity and to answer some questions.
The current solution (monte-carlo) has a function that generates a cost based on your options 1st choice is 0.0 cost, 2nd choice is .33, etc. 7th choice is 4.0. Then the weights for all parameters are summed and the algorithm has to optimize for the lowest score. There are also some other parameters like untrained (0.0 if web and trained, +2.0 to cost if web course and untrained, +2.0 to cost if unwilling to teach web course and web course)


texts: Does Memcomputing really solve an NP-complete problem?

texts:
I came across an article published in Science "Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states", which makes some pretty astonishing claims.

  Memcomputing is a novel non-Turing paradigm of computation that uses interacting memory cells (memprocessors for short) to store and process information on the same physical platform. It was recently proven mathematically that memcomputing machines have the same computational power of nondeterministic Turing machines. Therefore, they can solve NP-complete problems in polynomial time and, using the appropriate architecture, with resources that only grow polynomially with the input size.

(Italics mine).

I would dismiss this off the bat as non-serious, given the strong nature of the claims, if it weren't for the fact that this was published in Science, and that related material by some of the authors was published in Nature Physics, in an IEEE journal and in Physics Review E, all of which are reputable peer-reviewed publications that wouldn't let such claims get published without them being serious.

So is it true? Can these people solve NP-complete problems in P-time using their model?


texts: Is unbounded quantum fanout operation experimentally feasible?

texts:
It is known that the "unbounded quantum fanout operation" is very powerful: (See, for example, Hoyer et al. : http://theoryofcomputing.org/articles/v001a005/v001a005.pdf).

In particular, it is known that many operations that cannot be done in constant depth classical circuits can be done in constant depth quantum cicuits that include the quantum fan-out operation.

However, I can't seem to find any discussion as to whether "constant depth" fanout is possible physically.

In classical computation, it seems fairly reasonable to consider "fan-out" to be an operation that does not add to the "depth" of a circuit: such a computational model models the latency of actual physical circuits of reasonable size.

For a fair comparison, unbounded quantum fanout would need to be achievable using some kind of experiment with a latency that scales as a constant with the size of the fanout (if it scales even logarithmically, then that kind of defeats the whole advantage of the quantum fanout operation).

Is there any experimental evidence to suggest whether such constant-latency quantum fanout unitary operations are feasible?


texts: Do the quantum communication complexity lower bounds hold when parties can send a "duplicated" qubits?

texts:
This question continues from the previous question where I mistakenly asked a question that is too general.

In quantum communication complexity, we always assume that Alice and Bob have unlimited computational power and are still prove lower bounds such as the Ω(n) lower bounds of parity.

What happens if we assume that Alice and Bob can do something that they cannot do due to  the the law of physics? One particular ability that I'm interested in is when each party can send a qubit to the other party without losing their own qubit. In other words, before sending their qubits to the other party, they can make ONE copy of it. (Note that this is allowed only when they are about to send a qubit.)  Do the known lower bounds hold in this case?

A particular result that I'm interested in is the lower bound in Razborov's paper "Quantum communication complexity of symmetric predicates".

Also, is this ability already included in the formal definition, e.g., as defined in Razborov's paper?

(As you can guess, my understanding in quantum algorithm is very limited. So, besides the full answers, I would appreciate any pointer to anything in the literature as well.)


texts:
So there are many well known algorithms for approximate nearest neighbor on the $\ell_1$ distance. My question is, what about the weighted version of the problem (where the weights are specified along with each query). Is there anything known in the research literature already, or is it a trivial extension of established techniques?

More rigorously, the classical nearest neighbor problem is given point set $P$ and query point $q$, find $\text{argmin}_{p \in P} \sum_i | p_i - q_i |$.

A weighted nearest neighbor problem would be, given point set $P$, query point $q$ and weight vector $w$ s.t $\sum_i w_i = 1$ and $w_i \geq 0, \forall i$., find $\text{argmin}_{p \in P} \sum_i w_i | p_i - q_i |$.

Obviously one can do a linear scan for each specified $w$ and $q$, but that seems heavily redundant. So I was just curious if this has already been solved or is a trivial reduction.

The exact version of this is generally hard, so I'd expect the approximation version of this to be more studied or known.

Although the application I have currently is a specific one, its easy to come up with scenarios where a weighted $\ell_1$ distance is reasonable. For instance, say the points correspond to sets of features and the user decides for certain queries they want to accord more importance to specific target dimensions.

Having thought about this some more, if you fixed $q$ to be $0$ and varied $w$, then this problem becomes finding the minimum dot product in $P$ with $w$. As such its at least as hard as MIPS (maximum inner product search). Whether its harder is a more open question.


texts: Sparse coding and matching pursuit algorithms

texts:
Is it true that all known sparse coding algorithms which work efficiently in practice don't have convergence proofs and always use an intermediate step of a matching/subspace pursuit algorithm on the current dictionary? And that this step of using a pursuit algorithm intermediate to solve a compressed sensing problem on the intermediate dictionaries is what is the hard part which is analytically intractable?
Or is there any hardness result known for either matching pursuit algorithms or sparse coding?
I understand that there are sparse coding algorithms with proofs like, arXiv:1206.5882 (full rank dictionary), arXiv:1309.1952, arXiv:1310.7991, arXiv:1503.00778, arXiv:1407.1543 but I would like to understand why these aren't the ones that is probably ever used in practice.

It would be helpful if you could kindly add in other references that you might know of for either provable sparse coding or matching pursuit algorithms.


texts: Are there experiments in artificial life on the emergence of sexual reproduction (analogues)?

texts:
I'm aware of quite a few experiments on the emergence of replicators in various artificial life areas, e.g. from cellular automata to computer programs.

Have any similar result been obtained on the emergence of a recombination mechanism that can be argued to be similar to sexual reproduction?


texts: Route existence between n pairs of nodes

texts:
Given a directed acyclic graph with $2n$ nodes how can one determine if there is a path between any of following n pairs of nodes $(1 \rightarrow n+1), \ldots, (n \rightarrow n+n)$? There is a simple algorithm in $O(n \cdot (n + m))$ (where m is the number of edges) by doing a search from each node $1 \ldots n$, but can it be done better?

EDIT: I'm looking for existence, not complete paths.


texts: Nonnegative Permanent and Ellipsoidal Method

texts:
Famously, Barahona gave an algorithm for Max Cut for Graphs without K5 complete as Subfactor Graph.

This was based on the Ellipsoidal Method.

Finding a Max Cut is the same for Bipartite Graphs as finding a Perfect Matching. Therefore, is seems to me that if you could Count the solutions to Barahona Ellipsoidal Method, you could have fast fpras for Nonnegative Permanent!

Question: Has any work been done in this direction? Thanks in advance!


texts: Consider a large sparse rectangular integer matrix. Is there a way to compute its exact rank that is better in terms of speed and/or memory usage compared to a dense matrix?


texts: Why is it important to prove that a problem is NP-complete?

texts: Am I correct in understanding that proving a problem NP complete is a research success? If so why?


texts: What is the minimum complexity oracle that separates PSPACE from the polynomial hierarchy?

texts:
Background

  It is known that there exists an oracle $A$ such that, $PSPACE^A \neq PH^A$.

  It is even known that the separation holds relative to a random
  oracle.  Informally, one may interpret this to mean that there are
  many oracles for which $PSPACE$ and $PH$ are separate.

Question

  How complicated are these oracles that separate $PSPACE$ from $PH$.
  In particular, is there an oracle $A \in DTIME(2^{2^{n}})$ such that
  $PSPACE^A \neq PH^A$?

  Do we have any oracle $A$ such that $PSPACE^A \neq PH^A$ and $A$ has a known complexity upper bound?

Note: the existence of such an oracle may have ramifications in structural complexity theory.  See the following update below for further details.

Update with details on a lower bound technique

Claim: If $PSPACE = PH$, then for all oracles $A \in P/poly$, $PSPACE^A = PH^A$.

  Proof Sketch: Suppose that $PSPACE = PH$.

  Let an oracle $A \in P/poly$ be given.  We can build a polynomial time
  $\Sigma_2$ oracle Turing machine $M$ that for a given length $n$,
  guesses a circuit of size $p(n)$ using an existential quantification
  and verifies that the circuit decides $A$ by comparing the evaluation of the circuit and the query result for every length $n$ string
  using a universal quantification.

  Further, consider a decision problem that I'm referring to as
  quantified Boolean circuit (QBC) where you are given a quantified
  boolean circuit and want to know if it valid (similar to QBF).  This
  problem is PSPACE-complete because QBF is PSPACE-complete.

  By assumption, it follows that QBC $\in PH$.  Let's say $QBC \in
\Sigma_k$ for some $k$ sufficiently large.  Let $N$ denote a
  polynomial time $\Sigma_k$ Turing machine that solves QBC.

  We can intermingle the computation of $M$ and $N$ (similar to what is
  done in the proof of the Karp-Lipton theorem) to get a polynomial time
  $\Sigma_k$ oracle Turing machine that solves $QBC^A$.

  Informally, this new machine takes as input an oracle QBC (that is a
  QBC with oracle gates).  Then, it computes a circuit that computes
  $A$ on inputs of length $n$ (simultaneously pealing off the first two
  quantifiers).  Next, it replaces the oracle gates in the oracle QBC
  with the circuit for $A$.  Finally, it proceeds to apply the remainder
  of the polynomial time $\Sigma_k$ algorithm for solving $QBC$ on this
  modified instance.

Now, we can show the conditional lower bound.

Corollary: If there exists an oracle $A \in NEXP$ such that $PSPACE^A \neq PH^A$, then $NEXP \nsubseteq P/poly$.

  Proof Sketch: Suppose that there exists $A \in NEXP$ such that $PSPACE^A \neq PH^A$. If $NEXP \subseteq P/poly$, then we would get a contradiction.

  In particular, if $NEXP \subseteq P/poly$, then by the claim above we
  have $PSPACE \neq PH$.  However, it is known that $NEXP \subseteq P/poly$ implies that $PSPACE = PH$.

  (see here for some details on known results for P/poly)


texts: Heuristics for estimating the efficiency of Reduced Ordered Binary Decision Diagrams?

texts:
Reduced Ordered Binary Decision Diagrams (ROBDD) are an efficient data structure for representing boolean functions of multiple variables $f(x_1,x_2,...,x_n)$. I would like to get an intuition for how efficient they are.

For instance, for data compression, we know that data with low entropy (some symbols appearing more often than other, many repetitions) can be compressed very well while completely random data cannot be compressed.

  Is there an analogous intuition for estimating how efficiently ROBDDs can represent a given boolean formula?

For example, I have heard that multiplication of $n$-bit numbers cannot be represented efficiently, the minimum ROBDD size is exponential in $n$. Do you know of an intuitive argument that explains why this is the case?

Related question: intuition about efficiency of BDDs that calculate numbers (multiple terminal BDDs, etc.)


texts: Boolean functions with exponential size OBDD representation in all orders except one order?

texts:
Are there boolean functions with exponential size OBDD representation in all orders except one order?

...exponential size in all orders except very few orders?

The exceptional orders should be polysize.


texts: Expressive power of computer languages: it's all about the syntax/logic?

texts:
When analyzing the theoretical expressive power of programming languages (not the verbosity of the programming languages or how concise programs are) are there further criteria besides the class of formal grammar in the Chomsky's hierarchy and the type of logic chosen (for example first/second/higher-order, type logic or whatever other logic formalism)?

Is there an analysis of expressive power of data structures? Are there other constrains that limit the expressiveness of a computer language?

It seems that all these formalisms deal only with how we combine ideas, but not how well we can express an idea using a programming language. For example, they don't enter into the question of the limitations of an imaginary programming language with only a binary and integer primitive type.


texts:
This question is about structural risk minimization and model selection. Let $H_n$ be the collection of all binary classifiers on some fixed set with an $n$-bit description length in some fixed encoding. The learner receives a sample of $m$ iid points drawn from an unknown distribution and labeled correctly by some $h^*\in H:=\bigcup_{n\ge1}H_n$. Consider the Occam learner, whose strategy is to choose a consistent $\hat h\in H$ with the smallest description length $|\hat h|$. It is easy to show (see Question 2 here
https://www.cs.bgu.ac.il/~inabd161/wiki.files/exercise3.pdf
) that with probability at least $1-\delta$, the generalization error of $\hat h$ is at most
$$
\frac{|\hat h|\log 4+\log(1/\delta)}{m}
\le
\frac{|h^*|\log 4+\log(1/\delta)}{m}
$$
(because by construction, $|\hat h|\le|h^*|$).
It's obvious from the no-free-lunch theorem that no learner can achieve a risk rate independent of $|h^*|$. It's less obvious -- but seems plausible -- that no learner can achieve a risk rate $o(|h^*|/m)$ uniformly over all distributions. Is this sort of thing known? To rule out degenerate cases, assume that the VC-dim of $H_n$ is $\Theta(n)$.


texts: Multidimensional knapsack STRONGLY NP-complete

texts:
Who can point me to a reference where it is actually shown that multidimensional knapsack is strongly NP-complete? I have found loads of papers where they claim it is, without citation; I have found another load where they cite Garey & Johnson, although it is not in their list of strongly NP-complete problems (Sec. 4.2); many actually cite Garey & Johnson as "An introduction to" instead of "A guide to", so these authors probably copied from one another. In fact, some authors claim that it is not strongly NP-complete, an example is "The multidimensional 0–1 knapsack problem: An overview" by Freville, but the argument (generalize the DP for single-dimension knapsack) is obviously bogus, see below.

Multidimensional knapsack tries to maximize $\sum_j c_j x_j$ such that $\sum_j a_{ij} x_j \le b_j$ for $i=1,...,m$, with $x_i$ being integer $\ge 0$ (and all $c_j, a_{ij}, b_j$ being $\ge 0$). We can also demand $x_i \in \{0,1\}$, the 0/1-version of the problem. I would be happy for a proof of either of the two to be hard (hardness of the other should follow easily).

Strongly NP-hard applies only to number problems, and restricts the (some) maximum of the numbers to be polynomial in the size of the problem instance (bits needed to encode it). Strongly NP-hard rules out the existence of a pseudopolynomial algorithm for the problem, with running time polynomial in the numbers that appear in the instance. The usual knapsack (single-dimensional) obviously has a pseudopolynomial algorithm (DP), but this algorithm cannot be generalized to multidimensional KP, as the dimension of the KP appears in the exponent of the running time. I hope that I did not mess up anything in my definitions...


texts:
I'm trying to find the first article/paper that the complexity class search-BPP appeared in. Search-BPP, as defined as follows (in [1]):

A binary relation $R$ is in search-BPP if there is a probabilistic polynomial-time search algorithm $A$ that given $x \in R_L$ (the language defined by membership in the relation), outputs $y$ s.t. with probability $\geq 2/3$, $(x,y) \in R$.

Essentially, this is the generalization of BPP to search problems. The earliest article I could find mentioning search-BPP was in Goldreich's 2011 paper "In a world of P=BPP" (http://www.wisdom.weizmann.ac.il/~oded/COL/bpp-p.pdf). Was this introduced earlier? If so, could someone please provide a reference.

[1] Pseudo-Deterministic Proofs, Shafi Goldwasser, Ofer Grossman, and Dhiraj Holden (https://arxiv.org/abs/1706.04641)


texts: Is a software implementation of a PCP encoder available?

texts: We all know the PCP Theorem. Is there any software package availalbe taking a CNF in e.g. DIMACS format as input, and producing a PCP encoding in the same format as output? It might be interesting to run existing SAT solvers on such encoded instances and compare the performance relative to plain instances.


texts: How to efficiently compute a bounding box of a 2D compact function support?

texts:
I've come to an interesting problem. Let's have a 2D scalar function F and make some assumptions on it:

it has compact support (region where it is defined and non-zero)
its support consists of at most one continuous region (not several parts)
its support is continuous
at the border of the support there there might be discontinuities (steep cliffs) of the function F
the support might not be convex
the support is subset of a finite rectangle A parametrizable as [0;1]^2 topologically equavalent to cylinder without caps (left and right sides are wrapped around)

An example of such function might be an analogy to 2D box function where the support is hexagon-shaped, star-shaped or crescent-shaped.

We can also work with the characteristic function X of the F's support
(which indicates true iff the point is within the support).

The problem is to find an axis-oriented 2D bounding box (BB) of the support - either exact or approximate (slightly larger). The bounding box must contain the whole region and if possible should not miss any part of it. One goal is to make the bounding box embrace the support as tightly as possible. Second goal is to make the computation as fast as possible, even at the cost of geting just an slightly larger approximate bounding box.

Also the computation will be performed many times in succession on functions of very similar support, just moving around and slightly changing their shape.

I've thought about the possible solutions to the problem, but still haven't found a solution which would be elegant and robust. The possibilities are:

(1)

sample the rectangle A with some random points
mark each point with the characteristic function X as being either inside or outside the support
sort the X and Y coordinates of the sampled points
take the maximum outside X less or equal than the minimum inside X -> left BB side
take the minumum outside X greater or equal than the maximum inside X -> right BB side
(...and analogously for Y)

I'm not sure if this algorithm can guarantee that no parts of the support will be missed. It would probably converge to the right BB, but from the inside, not from outside.

We could always extend the computed BB by some percent, but it seems a bit ugly to me.

(2)
To save generating of some random points we might incrementally build the BB from inside and not generate any more random points inside the BB as their information is useless (they can't extend the BB).

(3)

find a "seed" which is inside the support

eg. generate some random points within rectangle A

go linearly or by binary searching in one direction to find the boundary of the support
trace the boundary around and find minima and maxima in each coordinate

As the support might be non-convex the might be more than one extreme which would touch the bounding box.

(4)
If we assume that the support do not contain any slim parts going outside less than some size we could divide the rectangle into a raster and find the rasterized border eg. with contour tracing. The possible error caused by rasterization could be compensated by enlarging the resulting BB by a pixel or so.

This wouldn't be much efficient for larger supports.

(5)
When computing BB's of several similar functions in a sequence as the initial seed could be used the barycenter of the previous resulting BB, possibly shifted by gradient of this quantity.

What do you think about such a problem? Does anybody have an experience with something similar or could recommend a particular technique useful in this context. Any help is appreciated! Thank you very much!


texts:
Consider an FSM and a finite set of variables. The FSM has the special property that each state contains a set of commands, with each command taking the form of "variable = expr(variable, ...)" e.g., x = y + z + 2. The commands are "activated" whenever the FSM transitions into the containing state.

My question is what class of problems are computable in this model? Perhaps more specifically, say M(k) is one of these state machines with k variables.

Perhaps the only claim that seems obvious to me about this construction is that all computable problems for M(k+1) is strictly larger than for M(k).

Please pardon me if my question is not well formed, or if I'm misusing some terminology. Thanks in advance.

Edit: Suppose also we add the additional constraint that each 'variable' has some range [-r, r].

Edit2: Thanks Martin Schwartz. I don't have the "street cred" yet to upvote or respond to your answer. Thanks!


texts:
Scott Aaronson said in the paper entitled "Why Philosophers Should Care About Computational Complexity" (Please see ECCC Report: TR11-108, section 7, pp 25-31):

  Following the work of Kearns and Valiant, we now know that many
  natural learning problems — as an example, inferring the rules of a
  regular or context-free language from random examples of grammatical
  and ungrammatical sentences — are computationally intractable.

My question is: Which factors make the problem of inferring the grammar difficult? Is the introducing random examples of ungrammatical sentences? If so, what would happen if the condition of "random examples of grammatical and ungrammatical sentences" is replace with "random examples of grammatical sentences with probability p>0 and random examples of ungrammatical sentences with probability 1-p"?


texts: A topological space related to SAT: is it compact?

texts:
The Satisfiability problem is, of course, a fundamental problem in theoretical CS. I was playing with one version of the problem with infinitely many variables. $\newcommand{\sat}{\mathrm{sat}} \newcommand{\unsat}{\mathrm{unsat}}$

Basic Setup. Let $X$ be a nonempty and possibly infinite set of variables. A literal is either a variable $x \in X$ or its negation $\neg x$. A clause $c$ is a disjunction of finite number of literals. Finally, we define a formula $F$ as a set of clauses.

An assignment of $X$ is a function $\sigma : X \to \{0,1\}$. I will not explicitly define the condition for when an assignment $\sigma$ satisfies a clause; it is slightly cumbersome, and is the same as in standard SAT. Finally, an assignment satisfies a formula if it satisfies every constituent clause. Let $\sat(F)$ be the set of satisfying assignments for $F$, and let $\unsat(F)$ be the complement of $\sat(F)$.

A topological space.

Our goal is to endow the space of all assignments of $X$, call this $\Sigma$, with a topological structure. Our closed sets are of the form $\sat(F)$ where $F$ is a formula. We can verify that this is indeed a topology:

The empty formula $\emptyset$ containing no clauses is satisfied by all assignments; so $\Sigma$ is closed.
The formula $\{ x, \neg x \}$ for any $x \in X$ is a contradiction. So $\emptyset$ is closed.
Closure under arbitrary intersection. Suppose $F_{i}$ is a formula for each $i \in I$. Then $\sat \left(\bigcup_{i \in I} F_i\right) = \bigcap_{i \in I} \sat(F_i)$.
Closure under finite union. Suppose $F$ and $G$ are two formulas, and define
$$
F \vee G := \{ c \vee d \,:\, c \in F, d \in G \}.
$$
Then $\sat(F \vee G) = \sat(F) \cup \sat(G)$.This needs an argument, but I'll skip this.

Call this topology $\mathcal T$, the "satisfiability topology"(!) on $\Sigma$. Of course, the opens sets of this topology are of the form $\unsat(F)$. Moreover, I observed that the collection of open sets
$$
\{ \unsat(c) \,:\, c \text{ is a clause} \}
$$
forms a basis for $\mathcal T$. (Exercise!)

Compact? I feel that this is an interesting, if not terribly useful, way to look at things. I want to understand whether this topological space possesses traditional interesting properties like compactness, connectedness etc. In this post, we will restrict ourselves to compactness:

  Let $X$ be a countably infinite collection of variables.1 Is $\Sigma$ compact under $\mathcal T$?

One can prove the following

  Proposition. $\mathcal T$ is compact if and only for all unsatisfiable formulas $F$, there exists a finite unsatisfiable subformula $\{ c_1, c_2, \ldots, c_m \} \subseteq F$.

(Not-so-hard exercise!) After several days of thinking, I do not have much progress in answering this question. I also do not have strong evidence for or against compactness. Can you suggest some approach?

Finally, as a bonus question:

  Has such a structure been studied before?

1The restriction to countable $X$ is just for simplicity; it also feels like the next natural step from finite number of variables.


texts: Complexity of Localization in Wireless Networks

texts:
Let distinct points $1 ... n$ sit in $\mathbb{R}^2$.  We say points $i$ and $j$ are neighbors if $|i-j| < 3 \pmod{n-2}$, meaning each point is neighbors with points with indexes within $2$, wrapping around.

The problem is:

  For each pair of neighbors we are given their pairwise distances (and we know which distance corresponds to which points), and we want to reconstruct the
  pairwise distances of all points.  My
  questions is, what is the complexity
  of this localization problem?

I don't know of a polynomial time algorithm.

This is motivated by problems in localization in sensor networks, where agents, placed ad-hoc, can wirelessly communicate with their lexicographic neighbors, and we want to reconstruct their positions.

I don't know much about geometry / localization problems, so this might be easy or known.  The closest problem I know about is the Turnpike problem, recently pointed out on this forum by @Suresh Venkat.


texts: The origin of the terms "efficient" and "feasible" computation/algorithm

texts:
I would like to know about the history of these two terms: "efficient", "feasible".

Who used them about computation/algorithms the first time? (in modern sense of these terms, i.e. 20th century).
How did they become mainstream?
How did these two terms start to be used as synonyms?

I know that Cobham used the term "feasible" in the statement of his thesis which associated with polynomial time computability. But is there an earlier reference? There doesn't seem to be an explicit reference to these terms in Godel's letter to von Neumann. I was not able to find any related article predating 1960 (using Google Scholar).

Another interesting point is that the title of Cobham's paper from 1965 is "The intrinsic computational difficulty of functions". When did "computational complexity" replace "computational difficulty"?


texts: Algorithm to decide if a CTL formula can also be expressed in LTL and translate it?

texts:
So I'm trying to solve some CTL formulas on a given system using model-checking.
I'm trying several different solvers; some of them only accept LTL as input, but have some nice partial-order reductions built-in that I would like to use and should perform well on my systems that feature heavy interleaving.
We know the intersection of LTL and CTL is non-empty (e.g. invariants lie there) but do you know of an algorithm to determine if a CTL formula can also be expressed in LTL, and to translate it if so ?


texts:
I have a set $S$ with two preorders $\mathord{\le}_1,\mathord{\le}_2\subseteq S\times S$ which a priori are unrelated.  Let $\equiv_1$ and $\equiv_2$ be the induced equivalences (i.e., $x\equiv_1 y$ iff $x\le_1 y\le_1 x$ and $x\equiv_2 y$ iff $x\le_2 y\le_2 x$).

I also have an operation $\land$ which turns out to give greatest lower bounds for both preorders: for all $x,y\in S$, $x\le_1 y$ iff $x\land y\equiv_1 x$ and $x\le_2 y$ iff $x\land y\equiv_2 x$.

Can I conclude anything about the relationship between my preorders?

(Note that the problem becomes trivial if my preorders are partial orders: in that case, the above implies $\mathord{\le}_1=\mathord{\le}_2$.)


texts: Complexity of checking whether linear equations have a positve solution

texts:
Consider a system of linear equations $Ax=0$, where $A$ is a $n\times n$ matrix with rational entries. Assume that the rank of $A$ is $<n$. What is the complexiy to check
whether it has a solution $x$ such that all entries of $x$ are stricly greater than 0 (namely, $x$ is a positive vector)? Of course, one can use Gauss elimination, but this seems not to be optimal.


texts:
What is the difference between logical framework and type theory? Both of them have types, terms, and are based on dependently typed lambda calculus.

We have Edinburg LF which is based on lambda-pi calculus, however, it seems to me that there's some subtle difference there.


texts:
Given a set S of nxn permutation matrices (which is only a small fraction of the n! possible permutation matrices), how can we find minimal-size subsets T of S such that adding the matrices of T has at least 1 in every position?

I am interested in this problem where S is a small subgroup of S_n. I am wondering whether it is possible to find (and implement!) approximation algorithms that are much quicker than the greedy algorithms (run many times until it got 'lucky', which is a very slow procedure but nonetheless it has given some near optimal bounds in small cases), or whether inapproximability guarantees that I cannot.

A few easy facts about this problem:
A length n cyclic group of permutation matrices solves this problem, of course optimally. (At least n matrices are needed because each permutation matrix has n ones and there are n^2 ones needed.)

The sets S of which I am interested do not have a n-cyclic group in them.

This problem is a very special case of set cover. Indeed, if we let X be the set (1,2, ... n)*(1,2,... n), with n^2 elements, then each permutation matrix corresponds to a size n subset, and I'm looking for the smallest subcollection of these subsets that cover X. Set cover itself is not a good way to look at this problem, because approximation of the general set cover problem.

The only reason why this problem is not much too slow using the greedy approach is because symmetry in the permutation group helps eliminate a lot of redundancy. In particular, if S is a subgroup, and T is a small subset which is a minimal covering set, then the sets sT (multiply T by any element of the group s) are still in S and still are a covering set (of course of the same size, so still minimal.) In case you were wondering, the successful case has n~30 and |S|~1000, with lucky greedy results having |T| ~37. Cases with n~50 have some very poor bounds taking a very long time to get.

To summarize, I am wondering if there are approximation approaches to this problem or if it is still general enough to fit within some inapproximability theorem- like there is for the general set cover problem. What algorithms are used to approximate related problems in practice? It seems like there may be something possible since the subsets are all of the same size and every element appears at the same small frequency 1/n.

-B


texts:
Here is an abstraction of an online learning / bandit problem that I've been working on in the summer. I haven't seen a problem like this before, and it looks quite interesting. If you know of any related work, I would appreciate references.

The Problem
The setting is that of multi-armed bandits. You have N arms. Each arm i has an unknown but fixed probability distribution over rewards that can be earned by playing it. For concreteness, let's assume that each arm i pays reward $10 with probability p[i] and reward $0 with prob. 1-p[i].

In every round t you select a set S[t] of arms to play. For each arm you select, you pay a fee of $1 up front. For each selected arm, you collect a reward that is drawn from the (unknown) reward probability distribution of that arm. All rewards are credited to your bank account, and all fees are deducted from that account. In addition, you get a credit of $1 at the beginning of every iteration.

The problem is to develop a policy to select a subset of arms to play in each iteration to maximize profit (i.e. rewards minus fees for playing) over a long enough horizon, subject to the constraint that it must maintain a non-negative account balance at all times.

I did not specify whether the per-arm reward distributions are chosen from a prior distribution or chosen by an adversary. Both choices make sense. The adversary formulation is more appealing to me, but probably harder to make progress on. Here, the adversary chooses a vector (D1, D2, .., DN) of distributions. Given the distributions, the optimal budget balanced policy is to play all arms whose expected reward is greater than $1. Let P be the per-step profit of this optimal omniscient policy. I want my online policy to minimize regret (i.e. loss of profit over a time window T) wrt this omniscient policy.


texts: Find the cheapest cycle through two points on a rectangular grid

texts:
I have a task, but I have no idea how to solve it.

We have to find a cycle going through $(1,1)$ and $(n,n)$ (X axis on the picture is indexed right to left) such that the sum of values in cells is minimized. A cycle can't contain a cell more than once.

Example:


texts: Integer relation detection for Subset Sum or NPP?

texts:
Is there a way to encode an instance of Subset Sum or the Number Partition Problem so that a (small) solution to an integer relation yields an answer?  If not definitely, then in some probabilistic sense?

I know that LLL (and perhaps PSLQ) have been used with moderate success in solving Subset Sum problems in the 'low-density' region, where the range of numbers chosen is greater than $2^N$, but these methods don't scale well to instances of larger size and fail in the 'high-density' region, when the range of numbers chosen is much smaller than $2^N$.  Here low-density and high-density refers to the number of solutions.  The low-density region refers to the few or no solutions that exist whereas high density refers to a region with many solutions.

In the high density region, LLL finds (small) integer relations amongst instances given, but as instance size increases, the probability of the relation found being a viable Subset Sum or Number Partition Problem solution becomes decreasingly small.

Integer relation detection is polynomial to within an exponential bound of optimal whereas Subset Sum and NPP are obviously NP-Complete, so in general this is probably not possible, but if the instance is drawn uniformly at random, could this make it simpler?

Or should I not even be asking this question and instead be asking if there is a way to reduce the exponential bound from the optimal answer in lieu of an exponential increase in computation?


texts:
Question: Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?

Background: I recently stumbled upon the dissertation "Computational complexity of multitape Turning machines and Random Access Machines" by Takumi Kasai (see here: https://repository.kulib.kyoto-u.ac.jp/dspace/handle/2433/86527).
As far as I can tell, the author shows that there exists a function $g$ such that $g$ can be computed in $O(n)$ time by RAM machines, but cannot be computed in $O(n^{2-\varepsilon})$ time by Multitape Turing machines for all $\varepsilon > 0$.
Can this result be extended to deciding languages (instead of computing functions)?  In other words, can we prove that there is a language decidable in $O(n)$ time by RAM machines that cannot be decided in $O(n^{2-\varepsilon})$ time by Multitape Turing machines for all $\varepsilon > 0$?


texts:
The GMD decoder is an algorithm for decoding concatenated codes up to half their minimal distance. The standard presentation of this algorithm usually proceeds in two steps: First, one shows a randomized decoding algorithm, and proves that this algorithm works in expectation, rather than with high probability. Then, one uses the latter proof to show how to derandomize the latter algorithm to get an algorithm that always works.

In all the presentations that I could find, it is never shown that the randomized algorithm works with high probability. However, it is not hard to see that this is indeed the case. I need to use this fact, and I wonder whether it was proved somewhere and I can give a reference, or whether I need to prove it myself.

So in short, my question is: Is there a reference for a paper that proves that the randomized decoder works with high probability?


texts: Is there any work combining machine learning and the more exotic forms of complexity theory?

texts: It seems to me that machine learning/data mining experts are familiar with P and NP, but rarely talk about some of the more subtle complexity classes (e.g. NC, BPP, or IP) and their implications for effectively analyzing data. Is there any survey of work doing this?


texts: Sentences in what kinds of grammar in the Chomsky hierarchy can be parsed by an LSTM of a given size?

texts:
Given

an LSTM $N$ of a given size $A$,
a sentence $S$ with a given number of words $B$,
a Chomsky grammar hierarchy level $C$ in 0-3,
a Chomsky grammar $G$ of level $C$ of size $D$,

A given fixed, concrete grammar $G$ defines a set of sentences $S$ which have the structure described by the grammar.  The size parameter $D$ gives a bound on the complexity of $G$.  Let's use the definition of an unrestricted grammar $G = (V, \Sigma, P, S)$, where

$V$ is a set of nonterminal symbols
$\Sigma$ is a set of terminal symbols
$P$ is a set of production rules and
$S$ is a set of start symbols in $V$

For our size measure $D$ we can adopt a simple rule such as $D=|V|+|\Sigma|+|P|$ where $|Q|$ is the number of elements in set $Q$.

Assume that the input to $N$ is a vector of size $B$ of integers representing words of $S$, and the output of $N$ is a single binary category with value 1 for $S$ in $G$ and 0 otherwise, and that the node weights of $N$ have been adjusted to optimally perform the recognition task.  In practice this would be through a labelled training process.  Let's assume that we have an oracle that gives us an optimal assignment of node weights.  The neural network architecture together with its size parameters (number of layers, number of nodes per layer and so on), together with the constant weights assigned to the nodes, comprise together a particular kind of computer program which operates in a fixed and well understood way.  In particular it is a kind of dataflow computation graph with some constant inputs, some variable inputs, some outputs and some feedback of certain node outputs as node inputs.   Once it has been configured, it operates in a deterministic and completely defined way.

Q1. Can $N$ recognize sentences (accept or reject) $S$?

Q2. Is this a problem in Theoretical Computer Science?

Q3. If the Chomsky Hierarchy is too old-fashioned, can you work this problem for the Complexity Zoo?


texts: A special case of the boolean multivariate quadratic polynomial problem

texts:
It's well known that in the general case, the boolean MQ problem:

given $(f_1, \ldots, f_n) \in \mathbb{F}_2[x_1, \ldots, x_m]$ with $\deg(f_i) = 2$, can we find a solution $\vec{y}: f_i(\vec{y}) = 0$,

is NP-hard.  I was wondering if there was an efficient algorithm for the special case in which each $f_i$ is the product of linear functions?


texts: Is a limited space-time hierarchy theorem correct?

texts:
Is a limited (deterministic) space-time hierarchy theorem correct?
For example, we have a limitation of $O(n^2)$  space then:
can we find problems that can be solved in $O(n^k)$ time and $O(n^2)$ space, but that have no algorithms that run in time $O(n^{k-1})$ and $O(n^2)$ space?


texts: Given a matrix $A$ maximize the number of positive elements in $Ax$ under specific constraints for $x$

texts:
Let $A = [a_{ij}]$ be a symmetric matrix with nonnegative values and $k << n/2$ a given constant. We want to rearrange the columns of the matrix such that the number of rows with the following property is maximized:
$$\sum_{j=1}^k a_{ij} > \sum_{j=k+1}^n a_{ij}$$

I have tried a greedy approach as well as to choose the $k$ columns with the largest sum. I think there is also a connection with the 2-partition of a set into sets such that the difference of their sums is maximized, but I have not any proofs.

Any ideas? Is there an efficient optimal or approximate algorithm for the problem? Can we prove if it is NP-hard?


texts: Are there any implementations of Cook-Levin?

texts:
Does anyone know if there is an implementation of Cook-Levin?
A program that gets an input like the following:

$M$: the code of a machine model/simple program in a programming language like C,
$\vec{n}$: binary integers for the size of the inputs (in bits),
$t$: a binary integer as a bound on the number of steps (if it is needed),
$m$: a binary integer as a bound on the amount of memory (if it is needed),

and outputs a Boolean circuit $C$ that computes $M$ on inputs of size $\vec{n}$?
Or a compiler from simple programs in a language like C to Turing machines,
plus an implementation of Cook-Levin for Turing machines.
By a simple program in C I mean a program that does not use libraries
(using standard computational libraries can be fine), i.e.
computes a function of its inputs and
does not interact with the environment (file system, network, other processes, ...).

Motivation:
Sometimes we want to turn instances of other NP problems into SAT instances
so we can run SAT solvers on them.
In place of writing a reduction program for each NP problem
we can use an implementation of Cook-Levin plus the code of a verifier for the NP problem.


texts: Convex Body with minimum expected l2 norm

texts:
Consider a convex body $K$ centered at origin and symmetric (i.e. if $x\in K$ then $-x\in K$). I desire to find a different convex body $L$ such that $K\subseteq L$ and the following measure is minimized:

$f(L)=\mathbb{E}(\sqrt{x^T \cdot x})$, where $x$ is a point chosen uniformly at random from L.

I am ok with constant factor approximation to the measure.

Some notes - The first intuitive guess that $K$ itself is the answer is wrong. For example consider $K$ to be a thin cylinder in very high dimension. Then we can get $L$ such that $f(L)<f(K)$ by letting $L$ have more volume close to origin.


texts:
Can any tree on $n$ nodes be decomposed into a set of $O(\log n)$ caterpillars? If not, what is the maximum number of caterpillars required? Are there efficient algorithms for finding the decomposition?

Any papers on this topic will be highly appreciated.


texts:
In conditional min-entropy extractor, there is a joint distribution $(X,Y)$ such that if the average min-entropy (for some appropriate notion of it) ${\rm H}_\infty(X|Y)$ is large, then ${\rm Ext}(X, Z)$, where $Z$ is a seed distribution that is independent from both $X$ and $Y$, looks random. This can be equivalently viewed as an "adversary", who has some limited knowledge $Y$ of $X$, cannot predict ${\rm Ext}(X, Z)$.

My question concerns the case where the adversary knows something about $Z$. I model this situation as that there is another random variable $M$ (say of $O(1)$ bits), that is allowed to be correlated with both $X$ and $Z$. Of course, if there is no structure about $M$, then there is no hope. As an example, suppose that $M = {\rm Ext}_1(X, Z)$ where $\rm Ext_1$ is the projection of $\rm Ext$ to its first bit, then clearly one cannot hope that the joint distribution $(M, Y, {\rm Ext}(X, Z))$ looks random.

My question is then the case where we do know something about $M$. Specifically, consider the case that the correlation between any bit of $M$ and any bit of ${\rm Ext}(X, Z)$ is small. In other words, $(M, {\rm Ext}(X, Z))$ is close to $(M, U)$ where $U$ is the uniform distribution (or modeling in another way, $(M, {\rm Ext}(X, Z))$ is close to $(U, {\rm Ext}(X, Z))$.

Do we know extractor constructions in this situation? Any pointer or reference? This problem seems pretty natural.

Thanks.


texts: Best method of Error Correction in Quantum Key Distribution

texts: As far as I can tell, almost all implementations of QKD use Brassard and Salvail's CASCADE algorithm for error correction. Is this really the best known method of correcting errors in a shared sequence of random qubits, or is there a better proposition that implementations of QKD should be using instead?


texts: W[1]-hard problems on bounded degree graphs

texts:
Do you know problems which are W[1]-hard even for bounded degree graphs?

Metric Dimension is hard on graphs with degree at most 3, but it is W[2]-hard.
Red-Blue Nonblocker used to be W[1]-hard on bounded degree graphs but there was an error in the proof (book of Downey Fellows 2013), and it is hard only if blue vertices are of bounded degree.


texts: While studying ${\bf NP}$ complete problems we have from Ladners' theorem - if ${\bf P}$ $\neq$ ${\bf NP}$-there are ${\bf NP}$ problems not in the class ${\bf P}$ nor ${\bf NP}$-complete.  Ladners' theorem is well known in the setting of ${\bf NP}$ completeness. The analog in the setting of real computation using the Blum-Shub-Smale model, that  ${\bf P}$$_{\mathbb{R}}$ $\neq$ ${\bf NP}$$_{\mathbb{R}} \Rightarrow$ there are ${\bf NP}$$_{\mathbb{R}}$ problems not in the class ${\bf P}$$_{\mathbb{R}}$ nor are they ${\bf NP}_{\mathbb{R}}$ complete should hold. So it is natural to think of ${\bf NP}$ intermediate problems over reals, or ${\bf NPI}$$_{\mathbb{R}}$ in the context of ladners theorem holding over reals (using the Blum Shub Smale model). Or an analogue of Ladners theorem over the reals(or other algebraic structures). Are there any candidate problems for this class ${\bf NPI}$$_{\mathbb{R}}$. Is it natural to think of the class ${\bf NPI}$$_{\mathbb{R}}$ - even to think of problems in this class of ${\bf NPI}$$_{\mathbb{R}}$, or even any known?


texts: norms of compressible and incompressible vector

texts:
Let $a$ be a vector in $R^m$, such that $\sum_{i=1}^ma_i=0$
I would like to bound $\sqrt{2m(2m-1)}\|a\|_{\infty}$ by $\sqrt{2m}\|a\|_2$ (or other way arround with the sharp constants), in the case when  vector $a$ is compressible and when vector $a$ is incompressible:

(Here is definitions of the compressible and incompressible vectors I use:
If we consider $R^{\sigma^c}=\mathsf{span}\{e_i: i\in\sigma^c\}$, $\sigma\subset\{1,...,m\}$, $|\sigma^c|=M$.

$x \in \mathsf{Comp}(M, \rho)$ iff there exists $\sigma$ with $|\sigma^c|\leq M$, s.t. projection $|P_{\sigma}x|\leq \rho$.

$x \in \mathsf{Incomp}(M, \rho)$ iff for any $\sigma$ with $|\sigma^c|\leq M$, s.t. projection $|P_{\sigma}x|> \rho$.

I wanted somehow to control $l_{\infty}$ norm. I guess I can do it only with incompressible vectors. But what can we say about compressible vestors?)


texts: Examples of ineffective PH collapse theorems?

texts:
What are some examples of theorems of the form "If $X$, then $PH$ collapses", but where the proof does not say which level $PH$ collapses to?

The canonical example would be "If $PH = PSPACE$, then $PH$ collapses", though this one is trivial.  Are there more interesting examples?


texts:
What I am trying to achieve is multiple k-selections (different but small datasets) running in parallel on a GPU. Basically, my aim is to select kth smallest element from an array of floats such that each work-group processes one array using CUDA and efficiently utilizes thread-level parallelism.

The number of arrays to be sorted as such run into thousands. I am not sure if I have seen such scaling done anywhere before. I have seen algorithms like the Duane Merrill Radix sort (which is actually sorting, not selection) or the randomized selection algorithm by Monroe et al. or k-selection algorithms by Alabi et al. However, ALL of them have been built for choosing the kth element from an extremely large array/vector and not multiple lists in parallel as I want.

The number of items in an array and k are pre-determined (n<10000). Could you suggest me any algorithm of k-selection of multiple short lists in parallel?


texts: Is eta-equivalence for functions compatiable with Haskell's seq operation?

texts:
Lemma: Assuming eta-equivalence we have that (\x -> ⊥) = ⊥ :: A -> B.

Proof: ⊥ = (\x -> ⊥ x) by eta-equivalence, and (\x -> ⊥ x) = (\x -> ⊥) by reduction under the lambda.

The Haskell 2010 report, section 6.2 specifies the seq function by two equations:

seq :: a -> b -> b
seq ⊥ b  =  ⊥
seq a b  =  b, if a ≠ ⊥

It then claims "As a consequence, ⊥ is not the same as \x -> ⊥, since seq can be used to distinguish them."

My question is, is that really a consequence of the definition of seq?

The implicit argument seems to be that seq would be uncomputable if seq (\x -> ⊥) b = ⊥.  However I haven't been able to prove that such a seq would be uncomputable.  It seems to me such a seq is both monotone, and continuous, which puts it in the the realm of being computable.

An algorithm that implement such as seq might work by attempting to search for for some x where f x ≠ ⊥ by enumerating the domain of f starting with ⊥. Though such an implementation, even if possible at all, gets pretty hairy once we want to make seq polymorphic.

Is there a proof that there is no computable seq that identifies (\x -> ⊥) with ⊥ :: A -> B?  Alternatively, is there some construction of seq that does identify (\x -> ⊥) with ⊥ :: A -> B?


texts:
This question arose in the context of cryptography, but below I will present it in terms of complexity theory, since people here are more acquainted with the latter. This question is related to Problems in NP but not in Average-P/poly and Beating Nonuniformity by Oracle Access.

Informal statement: When do non-uniform adversaries (i.e. poly-size family of circuits) succeed in breaking a cryptographic scheme, but uniform adversaries (i.e. probabilistic poly-time Turing machines) do not?

Complexity-theoretic statement: This is not exactly the same as the above informal statement, but I'm actually interested in this version:

  What natural problems lie in $(\mathsf{NP} \cap \mathsf{P/poly}) - \mathsf{AvgP}$ ?

In other words, what hard-on-average natural $\mathsf{NP}$ problems can be solved by poly-sized family of circuits?

The word solved can be interpreted as the worst-case or average-case (the latter is preferred).

If natural problems cannot be found easily, artificial problems are acceptable as well.


texts: Paritioning a graph into clique and independent set

texts:
I am interested in the complexity of the following problems:

Input: an undirected graph $G = \langle V, E \rangle$

Query 1: is there a partition of $V$ into two a clique $C$ and an independent set $I$ of equal size?

Query 2: are there a clique $C \subseteq V$ and an independent set $I \subseteq V$ whose sizes are at least $\frac{|V|}{4}$?


texts: Expected value of the evaluation of Boolean circuits of depth $2n$

texts:
I am not an expert on circuits and I wonder whether the following problem was already studied (and possibly solved). Any reference or suitable method to solve this question would be welcome.

Let $C_{n}$ be the Boolean circuit satisfying the following conditions:

the depth of $C$ is $2n$,
the gates of odd level are binary $\operatorname{AND}$ gates,
the gates of even level are binary $\operatorname{OR}$ gates.

The circuit $C_{n}$ computes a function $f_n$ which associates to each binary word of
length $2^{2n}$ a Boolean value.
For instance, for $n = 1$, $f_1(1010) = 0$ and $f_1(0011) = 1$, as shown in the
figure below:

For $0 \leqslant k \leqslant 2^{2n}$, let $L_k = \{ u \in \{0, 1\}^{2^{2n}} \mid |u|_1 = k \}$,
a language of size
$$
  \binom{2^{2n}}{k} = \frac{2^{2n}!}{k! (2^{2n} - k)!}
$$
Here is an instance of the problem I have in mind: if 40\% of the bits of the input
$x$ are equal to $1$, what is the expected value of $f_n(x)$? Here are a few more precise instances of this problem.

Compute the average value of $f_n(x)$ on $L_k$, that is,
$$
  \frac{k! (2^{2n} - k)!}{2^{2n}!} \sum_{x \in L_k} f_n(x),
$$
In particular, let $c \in [0,1]$ be a real number and let $c_n = \lfloor
 c2^{2n}\rfloor$. Can one estimate the average value of $f_n(x)$ on $L_{c_n}$, that is,
$$
 \frac{c_n! (2^{2n} - c_n)!}{2^{2n}!} \sum_{x \in L_{c_n}} f_n(x)\ ?
$$
Does the limit of the previous expression exists when $n$ tends to $\infty$?
$$
 \lim_{n \to \infty} \frac{1}{\binom{2^{2n}}{c_n}} \sum_{x \in L_{c_n}} f_n(x) =
 \lim_{n \to \infty} \frac{c_n! (2^{2n} - c_n)!}{2^{2n}!} \sum_{x \in L_{c_n}} f_n(x)
$$


texts:
Can intersection of two languages in NP which are not NP complete be NP complete?

Can intersection of two languages in coNP which are not coNP complete be coNP complete?

Can intersection of two languages one in coNP but not complete and other in NP but not NP complete be NP complete or coNP complete?


texts: Second order logic = PH. Do even higher order logics correspond to anything on complexity side of things?

texts: In the context of descriptive complexity PH is the class of languages expressible by statements of second-order logic. What classes of languages do higher order logics correspond to?


texts: What algorithm on a PRAM computes the connected components of a graph with least time complexity?

texts: The fastest method to compute the connected components of an undirected graph on a PRAM I have found is O(log n loglog n) in the 1993 paper Finding connected components in O(log n loglog n) time on the EREW PRAM, by K. Chong and T. Lam. Is there an algorithm with a smaller time complexity?


texts:
Perfect graphs exhibits many nice properties which enables NP complete problems to be solvable in polynomial time.

My question: Are there any result which indicates existence of some superclass of perfect graphs with similar properties ?


texts: Are there any propositional proof systems which are not Cook-Reckhow proof systems?

texts:
An abstract proof system is a polynomial time function $f$ whose
  range is equal to the set of tautologies. If $\tau$ is a tautology, then an $f$-proof of $\tau$ is any value $\pi$ such that $f(\pi) = \tau$.

Is there an example of a propositional  proof system which doesn't satisfy this definition?


texts: Equivalent SDP problems different solving times

texts: I have two SDP problems which are proved to be equivalent (in terms of optimal objective values) to each other in theory. Moreover, they have same number of constraints and variables respectively.  But in numerical tests, we found out that solving one is faster than the other. I can't find a reason to explain this observation.  Do you have any idea about the possible reasons to explain this?


texts:
It is not known whether NEXP is contained in P/poly. Indeed proving that NEXP is not in P/poly would have some applications in derandomization.

What is the smallest uniform class C for which one can prove that
C is not contained in P/poly?
Would showing that co-NEXP is not contained in P/poly have some
    other complexity theoretic consequences as in the case NEXP vs P/poly?

Note: I'm aware that $SP_2$ is known not to be contained in $Size[n^k]$ for each fixed constant $k$ (This was also shown for MA with 1 bit of advice). But in this question I'm not interested in results for fixed $k$. I'm really interested in classes which are different from P/Poly, even if these classes are very large.


texts: Is there a reasonable automated proof system for TCS theorems?

texts:
Suppose I wanted to formalize Turing's proof regarding the halting problem so that a machine could check it.  Some of the well-known automated theorem proving systems include Mizar, Coq, and HOL4.  I downloaded and experimented with Coq, but it doesn't have a library for Turing machines.  I thought to code one myself, but found the tutorial lacking and the language difficult to pick up.

My question is:  Is there an automated theorem prover that is generally good at proving theorems that involve Turing machines?  I would consider such a theorem prover "good" if it can formalize a proof of the undecidability of the halting problem using already-existing libraries.  I would consider it even better if it's relatively easy to pick up.  (For the record, I don't usually have difficulty with programming languages.)

Thanks,

Philip


texts:
What happens if we define ${\bf PPAD}$ such that instead of a polytime Turing-machine/polysize circuit, a logspace Turing-machine or an ${\bf AC^0}$ circuit encodes the problem?

Recently giving faster algorithms for Circuit satisfiability for small circuits turned out to be important, so I wonder what happens to rectricted versions of ${\bf PPAD}$.


texts: Smallest axis-aligned box that contains $k$ points

texts:
Input: A set of $n$ points in $\mathbb{R}^3$, and an integer $k \le n$.

Output: The smallest volume axis-aligned bounding box that contains at least $k$ of these $n$ points.

I'm wondering if any algorithms are known for this problem.  The best I could think of was $O(n^5)$ time, loosely as follows: brute-force over all possible upper and lower bounds for two of the three dimensions; for each of these $O(n^4)$ possibilities, we can solve the corresponding $1$-dimensional version of the problem in $O(n)$ time using a sliding window algorithm.


texts: Lower bounds for list/set data structures without delete

texts:
I'm interested in lower bounds on the amortized time cost for either of the following dynamic data structure problems, in the cell probe or RAM model, or any model that lets us do operations on words in constant time. There shouldn't be any restriction on the size of uninitialized memory that you're allowed to index into.
For both problems, i is a log n bit word, and I'm fine with assuming that x is also a word.
Data structure 1

insert(i,x) : insert x at position i in the list
get(i) : return the i-th element of the list

Data structure 2

add(x) : add x to the set
getByRank(i) : return the i-th largest element in the set

For both problems, log n / log log n seems like an upper bound using trees of branching factor sqrt(log n), but I haven't worked that out carefully at all.
I have read Lower Bounds for Data Structures, and I'm aware of the lower bounds for prefix sum (see e.g. https://cstheory.stackexchange.com/a/21575/28706 or lecture notes
http://www.tcs.tifr.res.in/~prahladh/teaching/2011-12/comm/lectures/l21.pdf or https://arxiv.org/pdf/cs/0502041.pdf). I don't see how to use the prefix sum result, and the other results I could find are all for data structures that support a delete operation.
I admit I have not studied the lower bound proofs... so forgive me if either of these problems are simple adaptations.
Note: the 2005 arXiv paper I linked to above might imply a lower bound of log n / log log n for the following related, but harder, problem, which adds a third operation:

add(x) : same as in data structure 1 above
getByRank(i) : same as in data structure 1 above
rank(x) : return the rank (ordinal) of x, where x was previously added.


texts: Which model of computation is "the best"?

texts:
In 1937 Turing described a Turing machine. Since then many models of computation have been decribed in attempt to find a model which is like a real computer but still simple enough to design and analyse algorithms.

As a result, we have dozen of algorithms for, e.g., SORT-problem for different models of computation. Unfortunately, we even cannot be sure that an implementation of an algorithm with running time O(n) in a word RAM with bit-vector operations allowed will run faster than an an implementation of an algorithm with running time O(n⋅logn) in a word RAM (I am talking about "good" implementations only, of course).

So, I want to understand which of existing models is "the best" for designing algorithms and I am looking for an up-to-date and detailed survey on models of computation, which gives pros and cons of models and their closeness to reality.


texts: Dissecting tetrahedra into similar tetrahedra

texts:
(i) Does anybody know what is the smallest number $k$ such that there
  is a tetrahedron T that can be subdivided into $k$ tetrahedra that are
  similar to T ?

I know $k$ is at most 8 (I know a tetrahedron that can be subdivided into 8 similar tetrahedra), and at least 3 (I can prove no tetrahedron can be subdivided into 2 tetrahedra that are similar to the whole). Does anybody know better lower or upper bounds?

  (ii) What if we require the tetrahedra in the subdivision to have the
  same size? (Again, I know $3 \leq k \leq 8$)


texts:
Suppose we want to join two relations on a predicate. Is this in NC?

I realize that a proof of it not being in NC would amount to a proof that $P\not=NC$, so I'd accept evidence of it being an open problem as an answer.

I'm interested in the general case as well as specific cases (e.g. perhaps with some specific data structure it can be parallelized).

Some specifics:

We could consider an equijoin $A.x = B.y$. On a single processor, a hash-based algorithm runs in $O(|A|+|B|)$ and this is the best we can do since we have to read each relation
If the predicate is a "black box" where we have to check each pair, there are $|A|\cdot|B|$ pairs, and each one could be in or not, so $2^{ab}$ possibilities. Checking each pair divides the possibilities in half, so the best we can do is $O(ab)$.

Could either of these (or some third type of join) be improved to $\log^k n$ on multiple processors?

(Reposted from here as per site policy.)


texts: An alternative model of a probabilistic Turing machine

texts: A probabilistic Turing machine operates with an additional tape of random bits, and its output is a random variable with some distribution over the random bits. Is it also useful to talk about the distribution over all inputs (rather than over all random bits)? For example, is it possible that there exists a probabilistic turing machine that accurately solves the halting problem with a probability of 99% (over the space of all possible valid computer programs received as input)?


texts: Minimum size counter-example in a 2-machine scheduling problem proof

texts:
I'm confused about something in the main proof in this paper (sorry that it's behind a paywall, but I assume many people on here have access to such things through their university and my posting the paper somewhere accessible would be, you know, technically illegal). It's not that I think the authors made an error; I'm just brand new at this and there's a lot of stuff I don't understand.

The point in question is four pages into the paper (sorry), but I'll try to summarize it. First of all, this variation of the scheduling problem is $P2|r_j|C_{max}$, i.e. 2-machine scheduling with release dates and no preemption with the goal of minimizing the makespan. Also, you're allowed to delay the assignment of jobs as opposed to having to assign them immediately if a machine is available. (This allows the algorithm to let any additional jobs come in to better determine how to assign them.)

The paper's claim is that its algorithm is ($1 + \alpha$)-competitive, $\alpha$ = 0.38197. The value of $\alpha$ is also used by the algorithm itself, since it waits $\alpha p_n$ ($p_n$ = the processing time of the last job started) before assigning each job.

The proof is by contradiction, where it takes $\sigma$ as the minimum schedule that makes the algorithm take longer than $1 + \alpha$ ($1$ being the length of the optimal offline schedule).

Let $j$ be the last job released when one of the machines is idle and no jobs are available. (Any time when both machines are idle can basically be ignored). Let $k$ be the job running when $j$ is released. If there's never a time when a machine is idle while there are no jobs available, let $r_j = C_k = 0$. ($r$ stands for release time; $C$ stands for completion time.)

Let $p$ equal any processing the optimal offline algorithm would need to do on previously released jobs at time $r_j$ (which may be 0).

The paper states: "Since $\sigma$ is a minumum size counterexample, $C_k \le (1 + \alpha)(r_j + p)$."

This comes out of nowhere for me. Why isn't it conceivable that $C_k$ could be greater than $(1 + \alpha)(r_j + p)$? I get that the makespan of $\sigma$ is basically just over $(1 + \alpha)C_{max}(opt)$, but why would the completion time of any job, even a "special" one like $k$, fall under a similar restriction? What if, for instance, $C_k(\sigma)$ is way over $(1 + \alpha)(r_j + p)$, but nevertheless, for whatever reason, $\sigma$ really catches up after that point and still finishes at $(1 + \alpha)C_{max}(opt)$? I suppose that seems unlikely, but why isn't it possible?

I sense that I'm being a bit picky, but on the other hand, I also sense that there's something I'm fundamentally not understanding.

Sorry this is so long. And sorry for breaking whatever forum rule or guideline I've no doubt violated.


texts: Algorithms to classify the geometrical relationship of two 3D-geometries

texts:
I have multiple 3D volumes which are represented by their boundaries (set of polygons each represented as a list of 3D-coordinates). I am now looking for algorithms to decide if

volume A is inside volume A
volume B is disjoint of volume B

Also I am interested in the dimension of the intersection of A and B if they aren't disjoint.

Specific ideas for algorithms would be just as helpful as references to useful books or papers.


texts: Colouring achieving simple discrepancy bound?

texts:
Given a hypergraph $H$ with $n$ vertices and $m$ edges,
one of the simplest inequalities on the discrepancy of $H$ is
$\text{disc}(H) \le \sqrt{2n \ln (2m)}$.

This is usually proved by mixing together one type of Chernoff bound using the probabilistic method (for instance, see the outline proof at the Wikipedia article on discrepancy).

Is there a known colouring $\chi \colon V(H) \to \{-1,1\}$ of the vertices of a hypergraph $H$ with $-1$ and $1$ that witnesses this bound?  In other words, such that for every edge $e \in E(H)$,
$$\left|\sum_{v \in e} \chi(v)\right| \le \sqrt{2n \ln (2m)}.$$

Of course, the probabilistic method guarantees the existence of such a $\chi$, but is there an algorithm better than exhaustively checking all possible colourings?

For completeness, the discrepancy of a hypergraph $H$ is the minimum over all possible colourings $\chi \colon V(H) \to \{-1,1\}$ of
the largest value of the local discrepancy $\left|\sum_{v \in e} \chi(v)\right|$ over all edges $e$ of $H$.


texts: Extended Formulaiton and Integer Programming

texts:
An extended formulation (EF) of a polytope $P\subseteq \mathbb{R}^d$ is a system of  linear constraints
$Ex + Fy  = g, y\geq 0$

in variables $(x,y)\in \mathbb{R}^{d+r}$ where $E,F$ are real
matrices with $d,r$ columns respectively and $g$ is a column vector
such that $x\in P$ if and only if there exists $y$ such that the equation above holds.

size of the EF is the number of linear constraints.

$P_{\mbox{spanning tree}}(G) = conv\{ \chi^{E(T)} \in \mathbb{R}^{E} : T \mbox{ is a spanning tree of }G \}.$

It is known that this polytope has the following formulation.

$x(E[U]) \leq  |U| -1$ for nonempty $U \subseteq  V $,
$x(E) = |V|-1 $,
$x_e > 0 $ for $ e\in E $

It is also known that the optimal solution of the following LP is 0-1 vector and the EF of spanning tree polytope has the size $O(n^{3}),n $is the size of the vertex set.

minmize:$\sum_{e \in E} c_{e}x_{e}  $

subject to:

$x(E[U]) \leq  |U| -1$ for nonempty $U \subseteq  V $,

$x(E) = |V|-1 $,

$x_e > 0 $ for $ e\in E $

Q1

Combining the above facts, does the folowing statement hold ?

Statement:

There is the foloowing system of $O(n^{3})$  linear constraints

$\sum_{e \in E} 1\cdot x_{e}\geq |V|-1$

$Ex + Fy  = g, y\geq 0$,

and it holds that  $x\in \mathbb{R}^{d}$ satisfies the above  linear constraints $\iff$  $x\in \{0,1  \}^{d}$

Q2

Is the significance of the notion of EF that the small size linear programming relaxation of 0-1 integer programming which solves some combinatorial problems can compute exact integer solution?

Q3

Recently [Fiorini, Massar, Pokutta, Tiwary and De Wolf][1] proved that any extended formulation of any of the three polytopes described above require an exponential number of innequalities.  [1]: http://arxiv.org/abs/1111.0837

Does  this result means that small size LP relaxation of 0-1 integer programming which solves the $NP-complete$ problems can $not$ compute exact integer solution   ?


texts: Two papers give contradictory bounds on linear probing. How do I resolve the disparity?

texts:
I've been reading over two papers recently. The first, "Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream" proves that, assuming there is sufficient entropy in a data source, weak hash functions end up producing distributions very close to truly uniformly random distributions. The other paper, "On the $k$-Independence Required for Linear Probing and Minwise Independence" gives strong lower bounds on the expected cost of linear probing lookups assuming different strengths of hash functions.

I'm having trouble reconciling the results of these two papers. The first paper proves that using 2-wise independent hash functions, if the entropy of the data source generating the elements of a linear probing hash table is sufficiently high, then the expected cost of a lookup is O(1) (and, more strongly, is equal to the bound assuming totally uniform hashing plus an o(1) term). On the other hand, the second paper proves that there exists a family of 2-universal hash functions for which the expected cost of a lookup in a linear probing hash table is $\Theta(\sqrt n)$.

These statements seem at odds with one another. I suspect that there's some technical condition from one of the two papers that I'm missing that make these bounds not conflict.

How can both of these statements be true at the same time?


texts: Entropy bounds on solutions to problems in BPP and other complexity classes based on entropy demands

texts:
Has anyone studied the asymptotics of problems in complexity classes like $BPP$? The thought came to me that if a problem in $BPP$ only requires $O(log(n))$ bits of entropy to solve then, intuitively, you should be able to generate every bit string of length $k*log(n)$ for some $k$ and use those bits to simulate a probabilistic algorithm which solves the problem for each bit string. Then if the algorithm was written correctly the correct result should occur in greater than $\frac{2}{3}$ of the cases you ran the input on. It might be the case that every problem in $BPP$ can be solved with $O(log(n))$ bits of entropy which I think would lead to a proof that $P = BPP$. On the same token it seems possible that there might exist an algorithm that requires $O(n)$ bits of entropy. This seems like it might provide a reason for the separation between P and BPP which seems unlikely.

This also just in general seems like a resource to think about the asymptotics of that I hadn't thought about before and I'd be generally interested in learning about what has been done in this area. There are some easy things we can conclude from the start like every solution to a problem in $BPP$ uses at most $O(n^c)$ bits of entropy since you can branch on at most $O(n^c)$ bits if your running time is $O(n^c)$. As outlined above though I suspect it must be the case that every problem in $BPP$ can be solved in $O(log(n))$ bits of entropy.

Are any lower bounds on entropy requirements for problems in BPP known? Is there any material on this general area I could read? Is there a known proof that if a probabilistic algorithm requires at most $O(log(n))$ bits of entropy then it has a deterministic counterpart that solves the same problem in $P$? Is there a proof that if there exists a problem in $BPP$ that requires $O(n)$ bits then $P \ne BPP$ (that would also imply P != NP so obviously something isn't proven there). If not Shannon entropy then perhaps min-entropy?


texts: Lower bounds for constant-depth formulae?

texts:
We know a lot about the limitations of (polynomial size) constant-depth circuits. Since (polynomial size) constant-depth formulae are an even more restricted model of computation, all problems known not to be in AC0 are also not computable by a constant-depth formula.  However, since it's an easier model, I'm guessing there are more problems known to be not computable in this model.  Has this been studied? (I'm guessing it has been, but I'm probably not using the right search terms.)

Specifically I am interested in the following question: Is there some function f, which can be computed by an AC0 circuit of size S, but needs a constant-depth formula of size at least quadratic in S, or super-polynomial in S?  What's the best known result of this kind?

In case it is not clear what I mean by constant-depth formula, I mean a formula which if you write out as a tree (with internal nodes being AND/OR/NOT gates, and leaves being inputs), then this tree has constant height. Equivalently, a constant-depth formula is a constant-depth circuit in which all non-input gates have fanout 1.


texts:
This problem originates from the tiling lowerbound method for communication complexity. In that method, there is a 0-1 matrix $M_{n \times n}$. A rectangle is defined as a submatrix $A \times B$ where $A \subseteq \{0,1\}^n$ and $B \subseteq \{0,1\}^n$. A rectangle is said to be monochromatic if all its elements are 0 (or all are 1). Define the minimum number of monochromatic rectangles needed to tile the whole matrix $M$ as $\chi$.

But the tiling defined as above might be difficult to visualize. For example, consider

$\begin{bmatrix}
1 0 1 0 \\
0 0 0 0 \\
1 0 1 0 \\
0 0 0 0
\end{bmatrix}$

At first glance it might be that $\chi$ is very large. But after permuting the second and third row/column, we have

$\begin{bmatrix}
1 1 0 0 \\
1 1 0 0 \\
0 0 0 0 \\
0 0 0 0
\end{bmatrix}$

then $\chi$ is easily seen to be 3 (since permutation doesn't change $\chi$).

To ease visulization, we define a contiguous rectangle as a rectangle with additional requirement that both $A$ and $B$ are contiguous. (For ex. $\{1,2,3\}$ is contiguous but $\{1,3,4\}$ isn't.) Assume $M'$ is formed from $M$ by a row/column permutation (which means you can permute any rows and any columns of $M$). Define $\chi'(M')$ as the mininum number of contiguous rectangles needed to tile $M'$. Define $\chi' = \min\{\chi'(M')$ | for any $M'\}$. The question is:

Is $\chi$ = $\chi'$?


texts: Finding the paths through a graph that reuse as many of the nodes as possible

texts:
I'm implementing an encryption algorithm which does a bunch xor operations to mix up the columns. Because I want to find the lower bound of the number of xor operations, I'm trying to figure out the best way to reuse intermediate results. I've created a graph with all the intermediate results and now want to find the paths through that graph that reuse the most nodes.

Simplified example: I want to calculate $abc$ and $bcd$ from $a,b,c,d$. I can only combine two variables at a time. Combining is commutative: the order does not matter. I've created a graph with all the possible intermediate results ($ab, bc, cd$). Obviously the best way to calculate $abc$ and $bcd$ is to do it like $abc = a (bc)$ and $bcd = d (bc)$. This way you can reuse the result of $bc$ and you end up doing 3 operations, instead of the 4 operations if you would do something like $abc = (ab)c$ and $bcd = (bc)d$.

In other words, I want fo find these paths:

       abc         bcd
        |           |
  +-----+--+--------+
  |        |        |
  | ab     bc   cd  |
  |        |        |
  |      +-+-+      |
  |      |   |      |
  a      b   c      d

Is there an algorithm suitable for finding this, or is there an algorithm that I can adapt to find this? (If there is an approach that doesn't use graphs, I'd like to learn of it as well).

Actual problem:
I have 16 inputs $x_0 \cdots x_{15}$ which are xored like this:

$$
\begin{array}{rcl}
x_0 &=& x_0 \oplus x_4 \oplus x_7 \oplus x_{10} \oplus x_{12} \oplus x_{14} \oplus x_{15} \\
x_{1} &=& x_1 \oplus x_4 \oplus x_{11} \oplus x_{12} \oplus x_{15} \\
x_{2} &=& x_2 \oplus x_5 \oplus x_8 \oplus x_9 \oplus x_{12} \\
x_{3} &=& x_3 \oplus x_6 \oplus x_9 \oplus x_{10} \oplus x_{13} \\
x_{4} &=& x_0 \oplus x_3 \oplus x_4 \oplus x_8 \oplus x_{10} \oplus x_{11} \oplus x_{14} \\
x_{5} &=& x_0 \oplus x_5 \oplus x_8 \oplus x_{11} \oplus x_{15} \\
x_{6} &=& x_1 \oplus x_6 \oplus x_8 \oplus x_{12} \oplus x_{13} \\
x_{7} &=& x_2 \oplus x_7 \oplus x_9 \oplus x_{13} \oplus x_{14} \\
x_{8} &=& x_2 \oplus x_4 \oplus x_6 \oplus x_7 \oplus x_8 \oplus x_{12} \oplus x_{15} \\
x_{9} &=& x_3 \oplus x_4 \oplus x_7 \oplus x_9 \oplus x_{12} \\
x_{10} &=& x_0 \oplus x_1 \oplus x_4 \oplus x_{10} \oplus x_{13} \\
x_{11} &=& x_1 \oplus x_2 \oplus x_5 \oplus x_{11} \oplus x_{14} \\
x_{12} &=& x_0 \oplus x_2 \oplus x_3 \oplus x_6 \oplus x_8 \oplus x_{11} \oplus x_{12} \\
x_{13} &=& x_0 \oplus x_3 \oplus x_7 \oplus x_8 \oplus x_{13} \\
x_{14} &=& x_0 \oplus x_4 \oplus x_5 \oplus x_9 \oplus x_{14} \\
x_{15} &=& x_1 \oplus x_5 \oplus x_6 \oplus x_{10} \oplus x_{15} \\
\end{array}
$$

I want to find groups such as $\{x_0, x_4\}$, $\{x_1, x_4\}$ and $\{x_{0}, x_{4}, x_{10}\}$ that are contained in several of these multiplications.


texts: Object-Oriented Programming Languages based on assignment

texts:
Is it correct to claim that an object-oriented programming language based on assignment (e.g., Java and Smalltalk) introduces mutability and hence complexity in concurrent applications ?
In other words: is there a direct correlation between a language being based on assignment and mutability ?


texts: Do Banach spaces and linear contraction maps form a model of ILL with an exponential?

texts:
Recently, I read on the nLab that the category of Banach spaces and linear contractions is small complete, small cocomplete, and monoidal closed.

This means that Banach spaces and short linear maps form a model of intuitionistic multiplicative-additive linear logic, and the fact that it is small (co)complete seems to suggest that the construction of Melliès, Tabareau
and Tasson in An explicit formula for the free exponential
modality of linear logic would go through in this category, supplying an interpretation of the exponential as well.

I found this quite surprising, since interpreting linear logic in infinite-dimensional vector spaces seems to have prompted an awful lot of work over the last two decades.

Does this model for ILL with an exponential actually work? I haven't seen it before in the literature, so maybe it fails for some obvious reason that I am overlooking...
If so, what is the motivation for placing so much emphasis on finding  models of specifically classical linear logic in (some restriction of) infinite-dimensional vector spaces?


texts: If a problem is NP-hard (using polynomial time reductions), does that imply that it is P-hard (using log space or NC reductions)?  It seems intuitive that if it is as hard as any problem in NP that it should be as hard as any problem in P, but I don't see how to chain the reductions and get a log space (or NC) reduction.