Online scheduling of equal-length jobs with incompatible families on multiple batch machines to maximize the weighted number of early jobs

This paper studies the online scheduling of equal-length jobs with incompatible families on multiple batch machines which can process the jobs from a common family in batches, where each batch has a capacity b with $b=\infty$ in the unbounded batching and $b<\infty$ in the bounded batching. Each job J has an equal-length integral processing time $p>0$, an integral release time $r(J)?0$, an integral deadline $d(J)?0$ and a real weight $w(J)?0$. The goal is to determine a preemptive schedule with restart which maximizes the weighted number of early jobs. When $p=1$, we show that a simple greedy online algorithm has a competitive ratio 2, and establish the lower bound $2?1/b$. This means that the greedy algorithm is of the best possible for $b=\infty$. When p is any positive integer, we provide an online algorithm of competitive ratio $3+2\sqrt{2}$ for both $b=\infty$ and $b<\infty$. This is the first online algorithm for the problem with a constant competitive ratio.     

Mod (2p+1)-orientations in line graphs

Jaeger in 1984 conjectured that every $(4p)$-edge-connected graph has a mod $(2p+1)$-orientation. It has also been conjectured that every $(4p+1)$-edge-connected graph is mod $(2p+1)$-contractible. In [Z.-H. Chen, H.-J. Lai, H. Lai, Nowhere zero flows in line graphs, Discrete Math. 230 (2001) 133–141], it has been proved that if G has a nowhere-zero 3-flow and the minimum degree of G is at least 4, then $L(G)$ also has a nowhere-zero 3-flow. In this paper, we prove that the above conjectures on line graphs would imply the truth of the conjectures in general, and we also prove that if G has a mod $(2p+1)$-orientation and $\delta (G)?4p$, then $L(G)$ also has a mod $(2p+1)$-orientation, which extends a result in Chen et al. (2001) [2].     

Cryptographic hardness for learning intersections of halfspaces

We give the first representation-independent hardness results for PAC learning intersections of halfspaces, a central concept class in computational learning theory. Our hardness results are derived from two public-key cryptosystems due to Regev, which are based on the worst-case hardness of well-studied lattice problems. Specifically, we prove that a polynomial-time algorithm for PAC learning intersections of $n^{\mathrm{?}}$ halfspaces (for a constant $\mathrm{?}>0$) in n dimensions would yield a polynomial-time solution to $\stackrel{?}{O}(n^{1.5})$-$\mathsf{uSVP}$ (unique shortest vector problem). We also prove that PAC learning intersections of $n^{\mathrm{?}}$ low-weight halfspaces would yield a polynomial-time quantum solution to $\stackrel{?}{O}(n^{1.5})$-$\mathsf{SVP}$ and $\stackrel{?}{O}(n^{1.5})$-$\mathsf{SIVP}$ (shortest vector problem and shortest independent vector problem, respectively). Our approach also yields the first representation-independent hardness results for learning polynomial-size depth-2 neural networks and polynomial-size depth-3 arithmetic circuits.     

A shortest cycle for each vertex of a graph

We present an algorithm that finds, for each vertex of an undirected graph, a shortest cycle containing it. While for directed graphs this problem reduces to the All-Pairs Shortest Paths problem, this is not known to be the case for undirected graphs.We present a truly sub-cubic randomized algorithm for the undirected case. Given an undirected graph with n vertices and integer weights in $1,\dots ,M$, it runs in $\stackrel{?}{O}(\sqrt{M}{n}^{(\omega +3)/2})$ time where $\omega <2.376$ is the exponent of matrix multiplication. As a by-product, our algorithm can be used to determine which vertices lie on cycles of length at most t in $\stackrel{?}{O}(M{n}^{\omega }t)$ time. For the case of bounded real edge weights, a variant of our algorithm solves the problem up to an additive error of ? in $\stackrel{?}{O}(n^{(\omega +6)/3})$ time.     

Deterministic extractors for small-space sources

We give polynomial-time, deterministic randomness extractors for sources generated in small space, where we model space s sources on ${\{0,1\}}^n$ as sources generated by width $2^s$ branching programs. Specifically, there is a constant $\eta >0$ such that for any $\zeta >n^{?\eta }$, our algorithm extracts $m=(\delta ?\zeta )n$ bits that are exponentially close to uniform (in variation distance) from space s sources with min-entropy δn, where $s=\Omega ({\zeta }^{3}n)$. Previously, nothing was known for $\delta ?1/2$, even for space 0. Our results are obtained by a reduction to the class of total-entropy independent sources. This model generalizes both the well-studied models of independent sources and symbol-fixing sources. These sources consist of a set of r independent smaller sources over ${\{0,1\}}^{?}$, where the total min-entropy over all the smaller sources is k. We give deterministic extractors for such sources when k is as small as $\mathsf{polylog}(r)$, for small enough ?.     

Finding large 3-free sets I: The small n case

There has been much work on the following question: given n, how large can a subset of $\{1,\dots ,n\}$ be that has no arithmetic progressions of length 3. We call such sets 3-free. Most of the work has been asymptotic. In this paper we sketch applications of large 3-free sets, present techniques to find large 3-free sets of $\{1,\dots ,n\}$ for $n?250$, and give empirical results obtained by coding up those techniques. In the sequel we survey the known techniques for finding large 3-free sets of $\{1,\dots ,n\}$ for large n, discuss variants of them, and give empirical results obtained by coding up those techniques and variants.