Theory of Computing Report

The following is a conversation between Clyde Kruskal and Bill Gasarch.

CLYDE:  Bill, a student, Ian Roberts,  asked me if there are any non-primitive recursive functions that people actually want to compute.

BILL: Off hand I would say no, but non-prim rec functions DO come up in natural ways.

CLYDE: That's not what he asked.

BILL: Even so, that's what I will blog about. OH, one more thing, why does he want to know?

CLYDE: Ask him directly. (BILL then emailed Ian)

BILL: Good question about NATURAL problems that are not prim-rec, but why do you want to know?

IAN:  Meyer and Richie proved (see here) that if you limit the control flow to IF statements, FOR loops with finite iterators then the class of functions you implement is  exactly the primitive recursive functions. So I was wondering if I could avoid ever using WHILE loops since they are harder to reason about. 

BILL: YES you COULD avoid ever using WHILE LOOPS; however, there are times when using them is the best way to go.

CLYDE: Bill, when is the last time you wrote a program? And LaTex does not count. 

BILL: Good point. Rather than take my word for it, let's ASK my readers. I'll add that to my list of RANDOM THOUGHTS ABOUT non-prim rec functions. 

SO, random thoughts on non-prim rec functions

0) Are there problems for which writing a WHILE loop is the way to go even though they are  not needed? 

1) HALT is not prim recursive and we want to compute it. Oh well. All future examples will be computable.

2) QUESTION: Are there simple programming languages so that HALT restricted to them is decidable but not primitive recursive? I suspect one could contrive such a language so I ask for both natural and contrived examples. 

3) The Paris-Harrington Numbers from Ramsey Theory are computable and  grow MUCH faster than prim rec. Indeed- they grow much faster than Ackermann's function. See Wikipedia Entry.

4) The Kanamori-McAloon Theorem from Ramsey theory is computable and grow MUCH faster than prim rec. Indeed- they grow much faster than Ackemann's function. See Wikipedia Entry. They are not as well known as the Paris-Harrington numbers. Hopefully this blog post will help that. 

5) Goodstein's Theorem yields numbers that are computable and grow MUCH faster than prim rec. Indeed, they grow much faster than Ackermann's function. See Wikipedia Entry and/or my blog post on them.

6) QUESTION: Of PH, KM, GOOD, which grows fastest? Second fastest? Third fastest? Perhaps some are tied.

6) QUESTION: We know that GO and CHESS have very high complexity, but are still prim recursive. We know that there are some math games (e.g., the Hydra game) that are not prim recursive. Are there any FUN  games whose complexity is NOT prim recursive?

7) Tarjan's UNION-FIND data structure has amortized complexity roughly O(n alpha(n)) where alpha(n) is the inverse of Ackermann's function. This is also a lower bound. See Wikipedia entry on disjoint-set data structure. QUESTION: Is Tarjan's UNION-FIND data structure actually used? It can be used to speed up Kruskal's MST algorithm, but that just takes the question back one step: Is MST a problem people really want to solve? I asked Lance and he asked chatty. For the results of that see here . The answer seems to be YES, though I wonder if the speedup that UNION-FIND gives is important. Union-Find is also used in the Hoshen-Kopelman Algorithm for (to quote Wikipedia) labeling clusters on a grid, where the grid is a regular network of  cells, with the cells being either occupied or unoccupied.  Other issues:  (a) is UNION-FIND hard to code up? Lance tells me that it is easy to code up.  (b) Is the constant reasonable?

8) Is the Ackerman Security Company called that since they claim that breaking their security is as hard as computing Ackerman's function? Unlikely- they spell it with only one n at the end. Even so, my class believed me when I told them that. 

9) The finite version of Kruskal's Tree Theorem YADA YADA YADA not prim rec. Wikipedia Entry

CLYDE: You can't YADA YADA YADA my Uncle Joe!

BILL: It's my party and you'll cry if you want to, cry if you want to, cry if you want to. (See here for Leslie Gore's song Its my party and I'll cry if I want to which is not about non primitive recursive functions. Also see her sequel Judy's turn to cry.  A much better song with a better message for teenagers is her You don't own me.)

CLYDE: Oh well. However, I'll make sure to tell that example to my class.

By gasarch

Authors: Adam Bouland, Daniel Brod, Ishaun Datta, Bill Fefferman, Daniel Grier, Felipe Hernandez, Michal Oszmaniec

BosonSampling is the leading candidate for demonstrating quantum computational advantage in photonic systems. While we have recently seen many impressive experimental demonstrations, there is still a formidable distance between the complexity-theoretic hardness arguments and current experiments. One of the largest gaps involves the ratio of photons to modes: all current hardness evidence assumes a "high-mode" regime in which the number of linear optical modes scales at least quadratically in the number of photons. By contrast, current experiments operate in a "low-mode" regime with a linear number of modes. In this paper we bridge this gap, bringing the hardness evidence for the low-mode experiments to the same level as had been previously established for the high-mode regime. This involves proving a new worst-to-average-case reduction for computing the Permanent that is robust to large numbers of row repetitions and also to distributions over matrices with correlated entries.

Authors: Manuel Fernandez V

In this paper we prove that the $\ell_0$ isoperimetric coefficient for any axis-aligned cubes, $\psi_{\mathcal{C}}$, is $\Theta(n^{-1/2})$ and that the isoperimetric coefficient for any measurable body $K$, $\psi_K$, is of order $O(n^{-1/2})$. As a corollary we deduce that axis-aligned cubes essentially "maximize" the $\ell_0$ isoperimetric coefficient: There exists a positive constant $q > 0$ such that $\psi_K \leq q \cdot \psi_{\mathcal{C}}$, whenever $\mathcal{C}$ is an axis-aligned cube and $K$ is any measurable set. Lastly, we give immediate applications of our results to the mixing time of Coordinate-Hit-and-Run for sampling points uniformly from convex bodies.

Authors: Wenjing Chen, Shuo Xing, Victoria G. Crawford

We consider the optimization problem of cardinality constrained maximization of a monotone submodular set function $f:2^U\to\mathbb{R}_{\geq 0}$ (SM) with noisy evaluations of $f$. In particular, it is assumed that we do not have value oracle access to $f$, but instead for any $X\subseteq U$ and $u\in U$ we can take samples from a noisy distribution with expected value $f(X\cup\{u\})-f(X)$. Our goal is to develop algorithms in this setting that take as few samples as possible, and return a solution with an approximation guarantee relative to the optimal with high probability. We propose the algorithm Confident Threshold Greedy (CTG), which is based on the threshold greedy algorithm of Badanidiyuru and Vondrak [1] and samples adaptively in order to produce an approximate solution with high probability. We prove that CTG achieves an approximation ratio arbitrarily close to $1-1/e$, depending on input parameters. We provide an experimental evaluation on real instances of SM and demonstrate the sample efficiency of CTG.

Authors: Antonios Antoniadis, Hajo Broersma, Yang Meng

We introduce learning augmented algorithms to the online graph coloring problem. Although the simple greedy algorithm FirstFit is known to perform poorly in the worst case, we are able to establish a relationship between the structure of any input graph $G$ that is revealed online and the number of colors that FirstFit uses for $G$. Based on this relationship, we propose an online coloring algorithm FirstFitPredictions that extends FirstFit while making use of machine learned predictions. We show that FirstFitPredictions is both \emph{consistent} and \emph{smooth}. Moreover, we develop a novel framework for combining online algorithms at runtime specifically for the online graph coloring problem. Finally, we show how this framework can be used to robustify by combining it with any classical online coloring algorithm (that disregards the predictions).

We study the Range Avoidance Problem (Avoid), in which the input is an expanding circuit $C : \{0,1\}^n \to \{0,1\}^{n+1}$, and the goal is to find a $y \in \{0,1\}^{n+1}$ that is not in the image of $C$. We are interested in the randomized complexity of this problem, i.e., in the question of whether there exist efficient randomized algorithms that output a valid solution to $\Avoid$ with probability significantly greater than $1/2$. (Notice that achieving probability $1/2$ is trivial by random guessing.) Our first main result shows that cryptographic one-way functions exist unless Avoid can be solved efficiently with probability $1-1/n^{C}$ (on efficiently sampleable input distributions). In other words, even a relatively weak notion of hardness of Avoid already implies the existence of all cryptographic primitives in Minicrypt. In fact, we show something a bit stronger than this. In particular, we introduce two new natural problems, which we call CollisionAvoid and AffineAvoid. Like Avoid, these are total search problems in the polynomial hierarchy. They are provably at least as hard as Avoid, and seem to be notably harder. We show that one-way functions exist if either of these problems is weakly hard on average. Our second main result shows that in certain settings Avoid can be solved with probability 1 in expected polynomial time, given access to either an oracle that approximates the Kolmogorov-Levin complexity of a bit string, or an oracle that approximates conditional time-bounded Kolmogorov complexity. This shows an interesting connection between Avoid and meta-complexity. Finally, we discuss the possibility of proving hardness of Avoid. We show barriers preventing simple reductions from hard problems in FNP to Avoid.

The relationships between various meta-complexity problems are not well understood in the worst-case regime, including whether the search version is harder than the decision version, whether the hardness scales with the ``threshold", and how the hardness of different meta-complexity problems relate to one another, and to the task of function inversion. In this note, we present resolutions to some of these questions with respect to the black-box analog of these problems. In more detail, let $MK^t_MP[s]$ denote the language consisting of strings $x$ with $K_{M}^t(x) < s(|x|)$, where $K_M^t(x)$ denotes the $t$-bounded Kolmogorov complexity of $x$ with $M$ as the underlying (Universal) Turing machine, and let $search-MK^t_MP[s]$ denote the search version of the same problem. We show that if there for every Universal Turing machine $U$ there exists a $2^{\alpha n}poly(n)$-size $U$-oracle aided circuit deciding $MK^t_UP [n-O(1)]$, then for every function $s$, and every---not necessarily universal---Turing machine $M$, there exists a $2^{\alpha s(n)}poly(n)$-size $M$-oracle aided circuit solving $search-MK^t_MP[s(n)]$; this in turn yields circuits of roughly the same size for both the Minimum Circuit Size Problem (MCSP), and the function inversion problem, as they can be thought of as instantiating $MK^t_MP$ with particular choices of (a non-universal) TMs $M$ (the circuit emulator for the case of MCSP, and the function evaluation in the case of function inversion). As a corollary of independent interest, we get that the complexity of black-box function inversion is (roughly) the same as the complexity of black-box deciding $MK^t_UP[n-O(1)]$ for any universal TM $U$; that is, also in the worst-case regime, function inversion is ``equivalent" to deciding $MK^t_UP$, in the black-box setting.

Proving explicit lower bounds on the size of algebraic formulas is a long-standing open problem in the area of algebraic complexity theory. Recent results in the area (e.g. a lower bound against constant-depth algebraic formulas due to Limaye, Srinivasan, and Tavenas (FOCS 2021)) have indicated a way forward for attacking this question: show that we can convert a general algebraic formula to a 'homogeneous' algebraic formula with moderate blow-up in size, and prove strong lower bounds against the latter model. Here, a homogeneous algebraic formula $F$ for a polynomial $P$ is a formula in which all subformulas compute homogeneous polynomials. In particular, if $P$ is homogeneous of degree $d$, $F$ does not contain subformulas that compute polynomials of degree greater than $d$. We investigate the feasibility of the above strategy and prove a number of positive and negative results in this direction. --- Lower bounds against weighted homogeneous formulas: We show the first lower bounds against homogeneous formulas 'of any depth' in the 'weighted' setting. Here, each variable has a given weight and the weight of a monomial is the sum of weights of the variables in it. This result builds on a lower bound of Hrubeš and Yehudayoff (Computational Complexity (2011)) against homogeneous multilinear formulas. This result is strong indication that lower bounds against homogeneous formulas is within reach. --- Improved (quasi-)homogenization for formulas: A simple folklore argument shows that any formula $F$ for a homogeneous polynomial of degree $d$ can be homogenized with a size blow-up of $d^{O(\log s)}.$ We show that this can be improved superpolynomially over fields of characteristic $0$ as long as $d = s^{o(1)}.$ Such a result was previously only known when $d = (\log s)^{1+o(1)}$ (Raz (J. ACM (2013))). Further, we show how to get rid of the condition on $d$ at the expense of getting a 'quasi-homogenization' result: this means that subformulas can compute polynomials of degree up to poly$(d).$ --- Lower bounds for non-commutative homogenization: A recent result of Dutta, Gesmundo, Ikenmeyer, Jindal and Lysikov (2022) implies that to homogenize algebraic formulas of any depth, it suffices to homogenize 'non-commutative' algebraic formulas of depth just $3$. We are able to show strong lower bounds against such homogenization, suggesting barriers for this approach. --- No Girard-Newton identities for positive characteristic: In characteristic $0$, it is known how to homogenize constant-depth algebraic formulas with a size blow-up of $\exp(O(\sqrt{d}))$ using the Girard-Newton identities. Finding analogues of these identities in positive characteristic would allow us, paradoxically, to show 'lower bounds' for constant-depth formulas over such fields. We rule out a strong generalization of Girard-Newton identities in the setting of positive characteristic, suggesting that a different approach is required.

We give simply exponential lower bounds on the probabilities of a given strongly Rayleigh distribution, depending only on its expectation. This resolves a weak version of a problem left open by Karlin-Klein-Oveis Gharan in their recent breakthrough work on metric TSP, and this resolution leads to a minor improvement of their approximation factor for metric TSP. Our results also allow for a more streamlined analysis of the algorithm. To achieve these new bounds, we build upon the work of Gurvits-Leake on the use of the productization technique for bounding the capacity of a real stable polynomial. This technique allows one to reduce certain inequalities for real stable polynomials to products of affine linear forms, which have an underlying matrix structure. In this paper, we push this technique further by characterizing the worst-case polynomials via bipartitioned forests. This rigid combinatorial structure yields a clean induction argument, which implies our stronger bounds. In general, we believe the results of this paper will lead to further improvement and simplification of the analysis of various combinatorial and probabilistic bounds and algorithms.

Authors: Lev Gordeev, Edward Hermann Haeusler

In this paper we present simplified proofs of our results NP = coNP = PSPACE.

Authors: Shenggen Zheng, Yaqiao Li, Minghua Pan, Jozef Gruska, Lvzhou Li

Time-space tradeoff has been studied in a variety of models, such as Turing machines, branching programs, and finite automata, etc. While communication complexity as a technique has been applied to study finite automata, it seems it has not been used to study time-space tradeoffs of finite automata. We design a new technique showing that separations of query complexity can be lifted, via communication complexity, to separations of time-space complexity of two-way finite automata. As an application, one of our main results exhibits the first example of a language $L$ such that the time-space complexity of two-way probabilistic finite automata with a bounded error (2PFA) is $\widetilde{\Omega}(n^2)$, while of exact two-way quantum finite automata with classical states (2QCFA) is $\widetilde{O}(n^{5/3})$, that is, we demonstrate for the first time that exact quantum computing has an advantage in time-space complexity comparing to classical computing.

Authors: Benny Sudakov, István Tomon

Given an $m\times n$ binary matrix $M$ with $|M|=p\cdot mn$ (where $|M|$ denotes the number of 1 entries), define the discrepancy of $M$ as $\mbox{disc}(M)=\displaystyle\max_{X\subset [m], Y\subset [n]}\big||M[X\times Y]|-p|X|\cdot |Y|\big|$. Using semidefinite programming and spectral techniques, we prove that if $\mbox{rank}(M)\leq r$ and $p\leq 1/2$, then

$$\mbox{disc}(M)\geq \Omega(mn)\cdot \min\left\{p,\frac{p^{1/2}}{\sqrt{r}}\right\}.$$

We use this result to obtain a modest improvement of Lovett's best known upper bound on the log-rank conjecture. We prove that any $m\times n$ binary matrix $M$ of rank at most $r$ contains an $(m\cdot 2^{-O(\sqrt{r})})\times (n\cdot 2^{-O(\sqrt{r})})$ sized all-1 or all-0 submatrix, which implies that the deterministic communication complexity of any Boolean function of rank $r$ is at most $O(\sqrt{r})$.

Authors: T-H. Hubert Chan, Gramoz Goranci, Shaofeng H.-C. Jiang, Bo Wang, Quan Xue

The Euclidean Steiner tree problem asks to find a min-cost metric graph that connects a given set of \emph{terminal} points $X$ in $\mathbb{R}^d$, possibly using points not in $X$ which are called Steiner points. Even though near-linear time $(1 + \epsilon)$-approximation was obtained in the offline setting in seminal works of Arora and Mitchell, efficient dynamic algorithms for Steiner tree is still open. We give the first algorithm that (implicitly) maintains a $(1 + \epsilon)$-approximate solution which is accessed via a set of tree traversal queries, subject to point insertion and deletions, with amortized update and query time $O(\poly\log n)$ with high probability. Our approach is based on an Arora-style geometric dynamic programming, and our main technical contribution is to maintain the DP subproblems in the dynamic setting efficiently. We also need to augment the DP subproblems to support the tree traversal queries.

Authors: Arun Jambulapati, James R. Lee, Yang P. Liu, Aaron Sidford

We consider the sparsification of sums $F : \mathbb{R}^n \to \mathbb{R}$ where $F(x) = f_1(\langle a_1,x\rangle) + \cdots + f_m(\langle a_m,x\rangle)$ for vectors $a_1,\ldots,a_m \in \mathbb{R}^n$ and functions $f_1,\ldots,f_m : \mathbb{R} \to \mathbb{R}_+$. We show that $(1+\varepsilon)$-approximate sparsifiers of $F$ with support size $\frac{n}{\varepsilon^2} (\log \frac{n}{\varepsilon})^{O(1)}$ exist whenever the functions $f_1,\ldots,f_m$ are symmetric, monotone, and satisfy natural growth bounds. Additionally, we give efficient algorithms to compute such a sparsifier assuming each $f_i$ can be evaluated efficiently.

Our results generalize the classic case of $\ell_p$ sparsification, where $f_i(z) = |z|^p$, for $p \in (0, 2]$, and give the first near-linear size sparsifiers in the well-studied setting of the Huber loss function and its generalizations, e.g., $f_i(z) = \min\{|z|^p, |z|^2\}$ for $0 < p \leq 2$. Our sparsification algorithm can be applied to give near-optimal reductions for optimizing a variety of generalized linear models including $\ell_p$ regression for $p \in (1, 2]$ to high accuracy, via solving $(\log n)^{O(1)}$ sparse regression instances with $m \le n(\log n)^{O(1)}$, plus runtime proportional to the number of nonzero entries in the vectors $a_1, \dots, a_m$.

Authors: Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, Maximilian Probst Gutenberg

We give the first almost-linear time algorithms for several problems in incremental graphs including cycle detection, strongly connected component maintenance, $s$-$t$ shortest path, maximum flow, and minimum-cost flow. To solve these problems, we give a deterministic data structure that returns a $m^{o(1)}$-approximate minimum-ratio cycle in fully dynamic graphs in amortized $m^{o(1)}$ time per update. Combining this with the interior point method framework of Brand-Liu-Sidford (STOC 2023) gives the first almost-linear time algorithm for deciding the first update in an incremental graph after which the cost of the minimum-cost flow attains value at most some given threshold $F$. By rather direct reductions to minimum-cost flow, we are then able to solve the problems in incremental graphs mentioned above.

At a high level, our algorithm dynamizes the $\ell_1$ oblivious routing of Rozho\v{n}-Grunau-Haeupler-Zuzic-Li (STOC 2022), and develops a method to extract an approximate minimum ratio cycle from the structure of the oblivious routing. To maintain the oblivious routing, we use tools from concurrent work of Kyng-Meierhans-Probst Gutenberg which designed vertex sparsifiers for shortest paths, in order to maintain a sparse neighborhood cover in fully dynamic graphs.

To find a cycle, we first show that an approximate minimum ratio cycle can be represented as a fundamental cycle on a small set of trees resulting from the oblivious routing. Then, we find a cycle whose quality is comparable to the best tree cycle. This final cycle query step involves vertex and edge sparsification procedures reminiscent of previous works, but crucially requires a more powerful dynamic spanner which can handle far more edge insertions. We build such a spanner via a construction that hearkens back to the classic greedy spanner algorithm.

• Lance Fortnow notices fewer faculty job ads in this year’s November CRA News and asks: “is there a real drop in hiring, or something else?”

• Vida Dujmović awarded University of Ottawa Research Chair (\(\mathbb{M}\)).

• POPL 2024 registration is on the order of £2000? It’s convenient that this ridiculous fee is nowhere visible on the POPL web site. This needs to be shown to all the computational geometers who would still like SoCG to return to the ACM fold. (Last year’s early registration fee: $375.)

• Characterization of the quadrilaterals that admit billiard circuits (\(\mathbb{M}\)), Katherine Knox. This means that a billiard ball can bounce once off each side in order before returning to its starting position. The author proved this when she was in 7th grade! See also Geogebra applet.

• The corolla (\(\mathbb{M}\)), something like a crown-shaped 3d flexagon decorated with Escher prints, with making-of blog post.

• Mathematical drawing hacks (\(\mathbb{M}\)), including tips on how to draw Möbius strips, tetrahedra, and curly brackets.

• Open access to heritage images is becoming increasingly difficult in Italy (\(\mathbb{M}\)). The background to this is an Italian court case last year in which The Gallerie dell’Accademia di Venezia, a public museum in Venice, won a lawsuit forcing jigsaw puzzle maker Ravensburger to pay royalties for reproductions of far far out of copyright works by Leonardo Da Vinci. This decision poses a threat not just to toy companies, but to Wikipedia and other users of public domain artworks.

• How to plagiarize and get away with it (\(\mathbb{M}\), via): become powerful enough that your friends in the court system declare you to be the true author of your bachelor’s thesis and enjoin your university from publishing their investigations. El Pais tells the story of Mexican supreme court justice Yasmín Esquivel.

• Robin Houston asks how few adjacent cubes in a \(4\times 4\times 4\) grid need to be glued to make the whole thing rigid. I found a solution with 50 glued pairs, the current record, but I’m not convinced its optimal. Image link is a spoiler.

• Slide-glide cyclides (\(\mathbb{M}\)). Banana-shaped pieces (geared at their shared base) that slide past each other to provide a mechanical demonstration of the equality of area of a sphere and a disk of twice the radius. 3d print and video by Henry Segerman.

• Why it’s important to choose the right kind of spiral in your designs (\(\mathbb{M}\)). Bernoulli merely ended up with a permanent mistake on his tombstone (an Archimedean spiral replacing his requested logarithmic spiral). But if you design a rock-climbing cam with a non-logarithmic spiral, or with the wrong logarithmic spiral, its incorrect angle against the rock may fail to protect you from a fall. And spiral wheels with a different carefully chosen shape can be used to design rocking self-propelled skateboards, crutches that help push their users forward, and therapeutic shoes that lengthen the gait of one foot, training people with gait impairments to walk better.

• What should I do if I suspect one of the journal reviews I got is Al-generated? (\(\mathbb{M}\)) Consensus answer: complain to the editor.

• The first mathematics publication I know of for the binary tiling or Böröczky tiling of the hyperbolic plane (\(\mathbb{M}\)) was in 1974 by Károly Böröczky. The same recursive structure appeared earlier, in a 1957 work of M. C. Escher, “Regular Division of the Plane VI”. I thought that might be the beginning of the story, but then I noticed that the Smith chart used in microwave engineering looks very similar: compare the binary tiling (below left) to the Smith chart (right) in the two Wikipedia images below.

  

  The same subdivision on horocycles and perpendicular hyperbolic lines is present in both images, and the same effect of refining the subdivision like a quadtree as you move further away from the center of the drawing. But the Smith charts perform the subdivision in a more irregular pattern, rather than subdividing at each successive horocycle. The original 1939 Smith chart looks similar, but rotated \(90^\circ\) and with an even more irregular pattern of subdivisions. See page 33 of Electronics magazine from January 1939.

By David Eppstein

Responsibilities:

Design the syllabus and teach to develop storylines and characters, character profiles, bios, and sketches, scripts of in-game dialogues, storyboards; Design grading metrics.

Qualifications:

Technical or humanitarian background;
Excellent command of Game Design and Gamification processes;
Experience of teaching young adults.

Website: https://career.innopolis.university/en/job/
Email: faculty@innopolis.ru

By shacharlovett

Responsibilities:

Design the syllabus and teach Game Design Methodologies, Gamification Processes, and Player Experiences;
Teach such as project-based learning, active discussions, role play, cases, etc.; Design grading metrics.

Qualifications:

Technical or humanitarian background;
Excellent command of Game Design and Gamification processes;
Experience of teaching young adults.

Website: https://career.innopolis.university/en/job/
Email: faculty@innopolis.ru

By shacharlovett

Qualifications:

Ph.D. degree and published research in Computer Science .
Focus on AI, GameDev and Data Science.

Responsibilities:

Frontal teaching the courses: Game History, Unity Game Development, Interactive Narrative, and Business of Games, etc. during the academic year; lead research activities, advise and mentor students.

Website: https://career.innopolis.university/en/job/
Email: faculty@innopolis.ru

By shacharlovett

Qualifications:

PhD degree
practical experience in Sensor Fusion, SLAM, Perception, ML, RL, DL strong record of published papers in CV for robotic application experience as PI in projects

Responsibilities:

Up to 120 hours of frontal teaching in 4 courses per year, leading research, advising and mentoring students, other activities for developing the intellectual environment.

Website: https://career.innopolis.university/en/job/
Email: faculty@innopolis.ru

By shacharlovett

Qualifications:
PhD degree
2+ years of Assistant Professorship
record of published papers in A* conferences

Responsibilities:
Up to 120 academic hours of frontal teaching in 4 courses per year, leading high quality research, advising and mentoring students, other activities related to developing and maintaining the intellectual and cultural environment of the University.

Website: https://career.innopolis.university/en/job/
Email: faculty@innopolis.ru

By shacharlovett

Qualifications:
PhD degree and published research in software quality, software architecture experience of leading software development teams
industry experience

Responsibilities:
Up to 120 academic hours of frontal teaching in 4 courses per year, leading high quality research, advising and mentoring students, other activities for developing and maintaining the intellectual environment.

Website: https://career.innopolis.university/en/job/
Email: faculty@innopolis.ru

By shacharlovett

Qualifications:

PhD degree and published research in programming languages, compilers, databases, OS

industry experience

Responsibilities:
Up to 120 academic hours of frontal teaching in 4 courses per year, leading high quality research, advising and mentoring students, other activities related to developing and maintaining the intellectual and cultural environment of the University.

Website: https://career.innopolis.university/en/job/
Email: faculty@innopolis.ru

By shacharlovett

Qualifications:

PhD degree

TAship experience

experience in Machine Learning

strong record of published papers

Responsibilities:

Up to 120 academic hours of frontal teaching in 4 courses per year, leading high quality research, advising and mentoring students, other activities related to developing and maintaining the intellectual and cultural environment of the University.

Website: https://career.innopolis.university/en/job/
Email: faculty@innopolis.ru

By shacharlovett

Qualifications:

PhD degree

depth of expertise

experience of being a TA

strong record of published papers

Responsibilities:

Up to 120 academic hours of frontal teaching in 4 courses per year, leading high quality research, advising and mentoring students, other activities related to developing and maintaining the intellectual and cultural environment of the University.

Website: https://career.innopolis.university/en/job/
Email: faculty@innopolis.ru

By shacharlovett

EPFL invite applications for a faculty position in all areas of quantum computing and quantum algorithms.

Screening starts at December 15 but later applicants will also be considered. Reach out to Ola Svensson with any questions about the search, position, and school!

Website: http://go.epfl.ch/qc-jobs
Email: ola.svensson@epfl.ch

By shacharlovett

Authors: Luís Cunha, Ignasi Sau, Uéverton Souza

Genome rearrangements are events where large blocks of DNA exchange places during evolution. The analysis of these events is a promising tool for understanding evolutionary genomics, providing data for phylogenetic reconstruction based on genome rearrangement measures. Many pairwise rearrangement distances have been proposed, based on finding the minimum number of rearrangement events to transform one genome into the other, using some predefined operation. When more than two genomes are considered, we have the more challenging problem of rearrangement-based phylogeny reconstruction. Given a set of genomes and a distance notion, there are at least two natural ways to define the "target" genome. On the one hand, finding a genome that minimizes the sum of the distances from this to any other, called the median genome. Finding a genome that minimizes the maximum distance to any other, called the closest genome. Considering genomes as permutations, some distance metrics have been extensively studied. We investigate median and closest problems on permutations over the metrics: breakpoint, swap, block-interchange, short-block-move, and transposition. In biological matters some values are usually small, such as the solution value d or the number k of input permutations. For each of these metrics and parameters d or k, we analyze the closest and the median problems from the viewpoint of parameterized complexity. We obtain the following results: NP-hardness for finding the median/closest permutation for some metrics, even for k = 3; Polynomial kernels for the problems of finding the median permutation of all studied metrics, considering the target distance d as parameter; NP-hardness result for finding the closest permutation by short-block-moves; FPT algorithms and infeasibility of polynomial kernels for finding the closest permutation for some metrics parameterized by the target distance d.

Authors: Kerven Durdymyradov, Mikhail Moshkov

In this paper, we study arbitrary infinite binary information systems each of which consists of an infinite set called universe and an infinite set of two-valued functions (attributes) defined on the universe. We consider the notion of a problem over information system, which is described by a finite number of attributes and a mapping associating a decision to each tuple of attribute values. As algorithms for problem solving, we investigate deterministic and nondeterministic decision trees that use only attributes from the problem description. Nondeterministic decision trees are representations of decision rule systems that sometimes have less space complexity than the original rule systems. As time and space complexity, we study the depth and the number of nodes in the decision trees. In the worst case, with the growth of the number of attributes in the problem description, (i) the minimum depth of deterministic decision trees grows either as a logarithm or linearly, (ii) the minimum depth of nondeterministic decision trees either is bounded from above by a constant or grows linearly, (iii) the minimum number of nodes in deterministic decision trees has either polynomial or exponential growth, and (iv) the minimum number of nodes in nondeterministic decision trees has either polynomial or exponential growth. Based on these results, we divide the set of all infinite binary information systems into three complexity classes. This allows us to identify nontrivial relationships between deterministic decision trees and decision rules systems represented by nondeterministic decision trees. For each class, we study issues related to time-space trade-off for deterministic and nondeterministic decision trees.

Authors: Piotr Kawałek, Armin Weiß

The Constant Degree Hypothesis was introduced by Barrington et. al. (1990) to study some extensions of $q$-groups by nilpotent groups and the power of these groups in a certain computational model. In its simplest formulation, it establishes exponential lower bounds for $\mathrm{AND}_d \circ \mathrm{MOD}_m \circ \mathrm{MOD}_q$ circuits computing AND of unbounded arity $n$ (for constant integers $d,m$ and a prime $q$). While it has been proved in some special cases (including $d=1$), it remains wide open in its general form for over 30 years.

In this paper we prove that the hypothesis holds when we restrict our attention to symmetric circuits with $m$ being a prime. While we build upon techniques by Grolmusz and Tardos (2000), we have to prove a new symmetric version of their Degree Decreasing Lemma and apply it in a highly non-trivial way. Moreover, to establish the result we perform a careful analysis of automorphism groups of $\mathrm{AND} \circ \mathrm{MOD}_m$ subcircuits and study the periodic behaviour of the computed functions.

Finally, our methods also yield lower bounds when $d$ is treated as a function of $n$.

Authors: Rohan Goyal, Prahladh Harsha, Mrinal Kumar, Ashutosh Shankar

We show that the known list-decoding algorithms for univariate multiplicity and folded Reed-Solomon (FRS) codes can be made to run in nearly-linear time. This yields, to our knowledge, the first known family of codes that can be decoded in nearly linear time, even as they approach the list decoding capacity. Univariate multiplicity codes and FRS codes are natural variants of Reed-Solomon codes that were discovered and studied for their applications to list-decoding. It is known that for every $\epsilon >0$, and rate $R \in (0,1)$, there exist explicit families of these codes that have rate $R$ and can be list-decoded from a $(1-R-\epsilon)$ fraction of errors with constant list size in polynomial time (Guruswami & Wang (IEEE Trans. Inform. Theory, 2013) and Kopparty, Ron-Zewi, Saraf & Wootters (SIAM J. Comput. 2023)). In this work, we present randomized algorithms that perform the above tasks in nearly linear time. Our algorithms have two main components. The first builds upon the lattice-based approach of Alekhnovich (IEEE Trans. Inf. Theory 2005), who designed a nearly linear time list-decoding algorithm for Reed-Solomon codes approaching the Johnson radius. As part of the second component, we design nearly-linear time algorithms for two natural algebraic problems. The first algorithm solves linear differential equations of the form $Q\left(x, f(x), \frac{df}{dx}, \dots,\frac{d^m f}{dx^m}\right) \equiv 0$ where $Q$ has the form $Q(x,y_0,\dots,y_m) = \tilde{Q}(x) + \sum_{i = 0}^m Q_i(x)\cdot y_i$. The second solves functional equations of the form $Q\left(x, f(x), f(\gamma x), \dots,f(\gamma^m x)\right) \equiv 0$ where $\gamma$ is a high-order field element. These algorithms can be viewed as generalizations of classical algorithms of Sieveking (Computing 1972) and Kung (Numer. Math. 1974) for computing the modular inverse of a power series, and might be of independent interest.

Authors: Guoxin Fang, Tianyu Zhang, Yuming Huang, Zhizhou Zhang, Kunal Masania, Charlie C.L. Wang

This work explores a spatial printing method to fabricate continuous fiber-reinforced thermoplastic composites (CFRTPCs), which can achieve exceptional mechanical performance. For models giving complex 3D stress distribution under loads, typical planar-layer based fiber placement usually fails to provide sufficient reinforcement due to their orientations being constrained to planes. The effectiveness of fiber reinforcement could be maximized by using multi-axis additive manufacturing (MAAM) to better control the orientation of continuous fibers in 3D-printed composites. Here, we propose a computational approach to generate 3D toolpaths that satisfy two major reinforcement objectives: 1) following the maximal stress directions in critical regions and 2) connecting multiple load-bearing regions by continuous fibers. Principal stress lines are first extracted in an input solid model to identify critical regions. Curved layers aligned with maximal stresses in these critical regions are generated by computing an optimized scalar field and extracting its iso-surfaces. Then, topological analysis and operations are applied to each curved layer to generate a computational domain that preserves fiber continuity between load-bearing regions. Lastly, continuous fiber toolpaths aligned with maximal stresses are generated on each surface layer by computing an optimized scalar field and extracting its iso-curves. A hardware system with dual robotic arms is employed to conduct the physical MAAM tasks depositing polymer or fiber reinforced polymer composite materials by applying a force normal to the extrusion plane to aid consolidation. When comparing to planar-layer based printing results in tension, up to 644% breaking forces and 240% stiffness are observed on shapes fabricated by our spatial printing method.

Authors: François Clément, Carola Doerr, Kathrin Klamroth, Luís Paquete

The $L_{\infty}$ star discrepancy is a very well-studied measure used to quantify the uniformity of a point set distribution. Constructing optimal point sets for this measure is seen as a very hard problem in the discrepancy community. Indeed, optimal point sets are, up to now, known only for $n\leq 6$ in dimension 2 and $n \leq 2$ for higher dimensions. We introduce in this paper mathematical programming formulations to construct point sets with as low $L_{\infty}$ star discrepancy as possible. Firstly, we present two models to construct optimal sets and show that there always exist optimal sets with the property that no two points share a coordinate. Then, we provide possible extensions of our models to other measures, such as the extreme and periodic discrepancies. For the $L_{\infty}$ star discrepancy, we are able to compute optimal point sets for up to 21 points in dimension 2 and for up to 8 points in dimension 3. For $d=2$ and $n\ge 7$ points, these point sets have around a 50% lower discrepancy than the current best point sets, and show a very different structure.

Authors: Andrea Marinoni, Pietro Lio', Alessandro Barp, Christian Jutten, Mark Girolami

Embedding graphs in continous spaces is a key factor in designing and developing algorithms for automatic information extraction to be applied in diverse tasks (e.g., learning, inferring, predicting). The reliability of graph embeddings directly depends on how much the geometry of the continuous space matches the graph structure. Manifolds are mathematical structure that can enable to incorporate in their topological spaces the graph characteristics, and in particular nodes distances. State-of-the-art of manifold-based graph embedding algorithms take advantage of the assumption that the projection on a tangential space of each point in the manifold (corresponding to a node in the graph) would locally resemble a Euclidean space. Although this condition helps in achieving efficient analytical solutions to the embedding problem, it does not represent an adequate set-up to work with modern real life graphs, that are characterized by weighted connections across nodes often computed over sparse datasets with missing records. In this work, we introduce a new class of manifold, named soft manifold, that can solve this situation. In particular, soft manifolds are mathematical structures with spherical symmetry where the tangent spaces to each point are hypocycloids whose shape is defined according to the velocity of information propagation across the data points. Using soft manifolds for graph embedding, we can provide continuous spaces to pursue any task in data analysis over complex datasets. Experimental results on reconstruction tasks on synthetic and real datasets show how the proposed approach enable more accurate and reliable characterization of graphs in continuous spaces with respect to the state-of-the-art.

Authors: Gabriel Gouvine

Optimal transport (OT) and unbalanced optimal transport (UOT) are central in many machine learning, statistics and engineering applications. 1D OT is easily solved, with complexity O(n log n), but no efficient algorithm was known for 1D UOT. We present a new approach that leverages the successive shortest path algorithm for the corresponding network flow problem. By employing a suitable representation, we bundle together multiple steps that do not change the cost of the shortest path. We prove that our algorithm solves 1D UOT in O(n log n), closing the gap.

Authors: Praneeth Kacham, David P Woodruff

We study lower bounds on adaptive sensing algorithms for recovering low rank matrices using linear measurements. Given an $n \times n$ matrix $A$, a general linear measurement $S(A)$, for an $n \times n$ matrix $S$, is just the inner product of $S$ and $A$, each treated as $n^2$-dimensional vectors. By performing as few linear measurements as possible on a rank-$r$ matrix $A$, we hope to construct a matrix $\hat{A}$ that satisfies $\|A - \hat{A}\|_F^2 \le c\|A\|_F^2$, for a small constant $c$. It is commonly assumed that when measuring $A$ with $S$, the response is corrupted with an independent Gaussian random variable of mean $0$ and variance $\sigma^2$. Cand\'es and Plan study non-adaptive algorithms for low rank matrix recovery using random linear measurements.

At a certain noise level, it is known that their non-adaptive algorithms need to perform $\Omega(n^2)$ measurements, which amounts to reading the entire matrix. An important question is whether adaptivity helps in decreasing the overall number of measurements. We show that any adaptive algorithm that uses $k$ linear measurements in each round and outputs an approximation to the underlying matrix with probability $\ge 9/10$ must run for $t = \Omega(\log(n^2/k)/\log\log n)$ rounds showing that any adaptive algorithm which uses $n^{2-\beta}$ linear measurements in each round must run for $\Omega(\log n/\log\log n)$ rounds to compute a reconstruction with probability $\ge 9/10$. Hence any adaptive algorithm that has $o(\log n/\log\log n)$ rounds must use an overall $\Omega(n^2)$ linear measurements. Our techniques also readily extend to obtain lower bounds on adaptive algorithms for tensor recovery and obtain measurement-vs-rounds trade-off for many sensing problems in numerical linear algebra, such as spectral norm low rank approximation, Frobenius norm low rank approximation, singular vector approximation, and more.

Authors: Anoushk Kharangate

Merkle trees have become a widely successful cryptographic data structure. Enabling a vast variety of applications from checking for inconsistencies in databases like Dynamo to essential tools like Git to large scale distributed systems like Bitcoin and other blockchains. There have also been various versions of Merkle trees like Jellyfish Merkle Trees and Sparse Merkle Trees designed for different applications. However, one key drawback of all these Merkle trees is that with a large data set the cost of computing the tree increases significantly, moreover insert operations on a single leaf require re-building the entire tree. For certain use cases building the tree this way is acceptable, however in environments where compute time needs to be as low as possible and where data is processed in parallel, we are presented with a need for asynchronous computation. This paper proposes a solution where given a batch of data that has to be processed concurrently, a Merkle Tree can be constructed from the batch asynchronously without needing to recalculate the tree for every insert.

Authors: Manal Helal, Vitali Sintchenko

The translation of comparative genomics into clinical decision support tools often depends on the quality of sequence alignments. However, currently used methods of multiple sequence alignments suffer from significant biases and problems with aligning diverged sequences. The objective of this study was to develop and test a new multiple sequence alignment (MSA) algorithm suitable for the high-throughput comparative analysis of different microbial genomes. This algorithm employs an innovative tensor indexing method for partitioning the dynamic programming hyper-cube space for parallel processing. We have used the clinically relevant task of identifying regions that determine resistance to antibiotics to test the new algorithm and to compare its performance with existing MSA methods. The new method "mmDst" performed better than existing MSA algorithms for more divergent sequences because it employs a simultaneous alignment scoring recurrence, which effectively approximated the score for edge missing cell scores that fall outside the scoring region.

Authors: Christopher Zawacki, Eyad Abed

With the rapid growth of digital platforms, there is increasing apprehension about how personal data is being collected, stored, and used by various entities. These concerns range from data breaches and cyber-attacks to potential misuse of personal information for targeted advertising and surveillance. As a result, differential privacy (DP) has emerged as a prominent tool for quantifying a system's level of protection. The Gaussian mechanism is commonly used because the Gaussian density is closed under convolution, a common method utilized when aggregating datasets. However, the Gaussian mechanism only satisfies approximate differential privacy. In this work, we present novel analysis of the Symmetric alpha-Stable (SaS) mechanism. We prove that the mechanism is purely differentially private while remaining closed under convolution. From our analysis, we believe the SaS Mechanism is an appealing choice for privacy focused applications.

Authors: Ainesh Bakshi, Vincent Cohen-Addad, Samuel B. Hopkins, Rajesh Jayaram, Silvio Lattanzi

Multi-dimensional Scaling (MDS) is a family of methods for embedding pair-wise dissimilarities between $n$ objects into low-dimensional space. MDS is widely used as a data visualization tool in the social and biological sciences, statistics, and machine learning. We study the Kamada-Kawai formulation of MDS: given a set of non-negative dissimilarities $\{d_{i,j}\}_{i , j \in [n]}$ over $n$ points, the goal is to find an embedding $\{x_1,\dots,x_n\} \subset \mathbb{R}^k$ that minimizes \[ \text{OPT} = \min_{x} \mathbb{E}_{i,j \in [n]} \left[ \left(1-\frac{\|x_i - x_j\|}{d_{i,j}}\right)^2 \right] \]

Despite its popularity, our theoretical understanding of MDS is extremely limited. Recently, Demaine, Hesterberg, Koehler, Lynch, and Urschel (arXiv:2109.11505) gave the first approximation algorithm with provable guarantees for Kamada-Kawai, which achieves an embedding with cost $\text{OPT} +\epsilon$ in $n^2 \cdot 2^{\tilde{\mathcal{O}}(k \Delta^4 / \epsilon^2)}$ time, where $\Delta$ is the aspect ratio of the input dissimilarities. In this work, we give the first approximation algorithm for MDS with quasi-polynomial dependency on $\Delta$: for target dimension $k$, we achieve a solution with cost $\mathcal{O}(\text{OPT}^{ \hspace{0.04in}1/k } \cdot \log(\Delta/\epsilon) )+ \epsilon$ in time $n^{ \mathcal{O}(1)} \cdot 2^{\tilde{\mathcal{O}}( k^2 (\log(\Delta)/\epsilon)^{k/2 + 1} ) }$.

Our approach is based on a novel analysis of a conditioning-based rounding scheme for the Sherali-Adams LP Hierarchy. Crucially, our analysis exploits the geometry of low-dimensional Euclidean space, allowing us to avoid an exponential dependence on the aspect ratio $\Delta$. We believe our geometry-aware treatment of the Sherali-Adams Hierarchy is an important step towards developing general-purpose techniques for efficient metric optimization algorithms.

What is the difference between engineering and computer science? CS is not an engineering field, though there is some overlap. It's not the digital versus physical. To capture the difference we can look two tech CEOs dominating the news recently, Elon Musk and Sam Altman.

Engineers are problem solvers creating or improving technologies to reach a goal. Tesla has led the way for cars to become electric, connected and autonomous. SpaceX has develops highly capable rocket technology at lower cost. Ultimately though Tesla makes cars that go from A to B and SpaceX sends stuff into space. When Musk bought Twitter he focused on the engineering, but Twitter's challenges were not in its engineering and this is why Twitter/X has been floundering.

Computer scientists make platforms. The Internet, cloud computing, programming languages, mobile computing, cryptography, databases, social networks even NP-completeness don't focus on individual problems, rather they create environments that users and developers can apply to a variety of new applications and challenges.

AI is no exception. OpenAI has no specific goal or purpose it is trying to solve. There's AGI but that's more of a vague benchmark that may (or may not) be passed as ChatGPT and its successors continue to improve.

AWS, Python, Apple and OpenAI all have developers conferences. Tesla and SpaceX do not. Elon Musk has actually made Twitter/X harder for developers to build on. I don't hold high hopes for Grok.

It's not a perfect division, many engineers create platforms and computer scientists tackle specific problems. Nevertheless it's a good way to see the distinction between the fields.

Don't think the CS way is always the better way. You have less control of platforms, they can act in unexpected ways and people can use them unintentionally or intentionally to cause harm. Mitigating those harms is a challenge we must continuously address.

By Lance Fortnow

One funded PhD position is available in the group of Dr Matthias C. Caro, who will join the University of Warwick, UK, in Fall 2024. This is an excellent opportunity to join one of the most active CS theory groups in the UK and to become part of the interdisciplinary research initiative Warwick Quantum. Candidates interested in quantum computing and learning theory are encouraged to apply.

Website: https://warwick.ac.uk/fac/sci/dcs/news/?newsItem=8a1785d88bf6b075018c15b1e42170fb
Email: matthias.caro@fu-berlin.de

By shacharlovett

Authors: Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu

The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the number of variables, from one where every assignment fails to satisfy an $\varepsilon$ fraction of constraints for some absolute constant $\varepsilon > 0$. PIH plays the role of the PCP theorem in parameterized complexity. However, PIH has only been established under Gap-ETH, a very strong assumption with an inherent gap.

In this work, we prove PIH under the Exponential Time Hypothesis (ETH). This is the first proof of PIH from a gap-free assumption. Our proof is self-contained and elementary. We identify an ETH-hard CSP whose variables take vector values, and constraints are either linear or of a special parallel structure. Both kinds of constraints can be checked with constant soundness via a "parallel PCP of proximity" based on the Walsh-Hadamard code.

Authors: Miriam Fischer, Martin Gairing, Dario Paccagnan

In this work we study the power and limitations of fair interventions in weighted congestion games. Specifically, we focus on interventions that aim at improving the equilibrium quality (price of anarchy) and are fair in the sense that identical players receive identical treatment. Within this setting, we provide three key contributions: First, we show that no fair intervention can reduce the price of anarchy below a given factor depending solely on the class of latencies considered. Interestingly, this lower bound is unconditional, i.e., it applies regardless of how much computation interventions are allowed to use. Second, we propose a taxation mechanism that is fair and show that the resulting price of anarchy matches this lower bound, while the mechanism can be efficiently computed in polynomial time. Third, we complement these results by showing that no intervention (fair or not) can achieve a better approximation if polynomial computability is required. We do so by proving that the minimum social cost is NP-hard to approximate below a factor identical to the one previously introduced. In doing so, we also show that the randomized algorithm proposed by Makarychev and Sviridenko (Journal of the ACM, 2018) for the class of optimization problems with a "diseconomy of scale" is optimal, and provide a novel way to derandomize its solution via equilibrium computation.

Authors: Gregory Valiant

We describe two algorithms for multiplying n x n matrices using time and energy n^2 polylog(n) under basic models of classical physics. The first algorithm is for multiplying integer-valued matrices, and the second, quite different algorithm, is for Boolean matrix multiplication. We hope this work inspires a deeper consideration of physically plausible/realizable models of computing that might allow for algorithms which improve upon the runtimes and energy usages suggested by the parallel RAM model in which each operation requires one unit of time and one unit of energy.

Authors: Omri Ben-Eliezer, Esty Kelman, Uri Meir, Sofya Raskhodnikova

The online manipulation-resilient testing model, proposed by Kalemaj, Raskhodnikova and Varma (ITCS 2022 and Theory of Computing 2023), studies property testing in situations where access to the input degrades continuously and adversarially. Specifically, after each query made by the tester is answered, the adversary can intervene and either erase or corrupt $t$ data points. In this work, we investigate a more nuanced version of the online model in order to overcome old and new impossibility results for the original model. We start by presenting an optimal tester for linearity and a lower bound for low-degree testing of Boolean functions in the original model. We overcome the lower bound by allowing batch queries, where the tester gets a group of queries answered between manipulations of the data. Our batch size is small enough so that function values for a single batch on their own give no information about whether the function is of low degree. Finally, to overcome the impossibility results of Kalemaj et al. for sortedness and the Lipschitz property of sequences, we extend the model to include $t<1$, i.e., adversaries that make less than one erasure per query. For sortedness, we characterize the rate of erasures for which online testing can be performed, exhibiting a sharp transition from optimal query complexity to impossibility of testability (with any number of queries). Our online tester works for a general class of local properties of sequences. One feature of our results is that we get new (and in some cases, simpler) optimal algorithms for several properties in the standard property testing model.

Authors: Andreas Opedal, Eleftheria Tsipidi, Tiago Pimentel, Ryan Cotterell, Tim Vieira

The left-corner transformation (Rosenkrantz and Lewis, 1970) is used to remove left recursion from context-free grammars, which is an important step towards making the grammar parsable top-down with simple techniques. This paper generalizes prior left-corner transformations to support semiring-weighted production rules and to provide finer-grained control over which left corners may be moved. Our generalized left-corner transformation (GLCT) arose from unifying the left-corner transformation and speculation transformation (Eisner and Blatz, 2007), originally for logic programming. Our new transformation and speculation define equivalent weighted languages. Yet, their derivation trees are structurally different in an important way: GLCT replaces left recursion with right recursion, and speculation does not. We also provide several technical results regarding the formal relationships between the outputs of GLCT, speculation, and the original grammar. Lastly, we empirically investigate the efficiency of GLCT for left-recursion elimination from grammars of nine languages.

Authors: Jonathan Allcock, Jinge Bao, Aleksandrs Belovs, Troy Lee, Miklos Santha

We initiate a systematic study of the time complexity of quantum divide and conquer algorithms for classical problems. We establish generic conditions under which search and minimization problems with classical divide and conquer algorithms are amenable to quantum speedup and apply these theorems to an array of problems involving strings, integers, and geometric objects. They include LONGEST DISTINCT SUBSTRING, KLEE'S COVERAGE, several optimization problems on stock transactions, and k-INCREASING SUBSEQUENCE. For most of these results, our quantum time upper bound matches the quantum query lower bound for the problem, up to polylogarithmic factors.

Authors: Weihao Kong, Mingda Qiao, Rajat Sen

We study the problem of recovering Gaussian data under adversarial corruptions when the noises are low-rank and the corruptions are on the coordinate level. Concretely, we assume that the Gaussian noises lie in an unknown $k$-dimensional subspace $U \subseteq \mathbb{R}^d$, and $s$ randomly chosen coordinates of each data point fall into the control of an adversary. This setting models the scenario of learning from high-dimensional yet structured data that are transmitted through a highly-noisy channel, so that the data points are unlikely to be entirely clean.

Our main result is an efficient algorithm that, when $ks^2 = O(d)$, recovers every single data point up to a nearly-optimal $\ell_1$ error of $\tilde O(ks/d)$ in expectation. At the core of our proof is a new analysis of the well-known Basis Pursuit (BP) method for recovering a sparse signal, which is known to succeed under additional assumptions (e.g., incoherence or the restricted isometry property) on the underlying subspace $U$. In contrast, we present a novel approach via studying a natural combinatorial problem and show that, over the randomness in the support of the sparse signal, a high-probability error bound is possible even if the subspace $U$ is arbitrary.

Authors: C. Q. Cheng, K. S. Wong, L. K. Soon

Graph database is designed to store bidirectional relationships between objects and facilitate the traversal process to extract a subgraph. However, the subgraph matching process is an NP-Complete problem. Existing solutions to this problem usually employ a filter-and-verification framework and a divide-and-conquer method. The filter-and-verification framework minimizes the number of inputs to the verification stage by filtering and pruning invalid candidates as much as possible. Meanwhile, subgraph matching is performed on the substructure decomposed from the larger graph to yield partial embedding. Subsequently, the recursive traversal or set intersection technique combines the partial embedding into a complete subgraph. In this paper, we first present a comprehensive literature review of the state-of-the-art solutions. l2Match, a subgraph isomorphism algorithm for small queries utilizing a Label-Pair Index and filtering method, is then proposed and presented as a proof of concept. Empirical experimentation shows that l2Match outperforms related state-of-the-art solutions, and the proposed methods optimize the existing algorithms.

Authors: Dinesh Kumar Baghel, Erel Segal-Halevi

Given items of different sizes and a fixed bin capacity, the bin-packing problem is to pack these items into a minimum number of bins such that the sum of item sizes in a bin does not exceed the capacity. We define a new variant called $k$-times bin packing ($k$BP), where the goal is to pack the items such that each item appears exactly $k$ times, in $k$ different bins. We generalize some existing approximation algorithms for bin-packing to solve $k$BP, and analyze their performance ratio.

The study of $k$BP is motivated by the problem of fair electricity distribution. In many developing countries, the total electricity demand is higher than the supply capacity. We show that $k$-times bin packing can be used to distribute the electricity in a fair and efficient way. Particularly, we implement generalizations of the First-Fit and First-Fit-Decreasing bin-packing algorithms to solve $k$BP, and apply the generalizations to real electricity demand data. We show that our generalizations outperform existing heuristic solutions to the same problem.