Artūrs Bačkurs

Tight Hardness Results for LCS and Other Sequence Similarity Measures

2015

Two important similarity measures between sequences are the longest common subsequence (LCS) and the dynamic time warping distance (DTWD). The computations of these measures for two given sequences are central tasks in a variety of …

Fast Algorithms for Parsing Sequences of Parentheses with Few Errors

2016

We consider the problem of fixing sequences of unbalanced parentheses. A classic algorithm based on dynamic programming computes the optimum sequence of edits required to solve the problem in cubic time. We show the first …

If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser

2015

The CFG recognition problem is: given a context-free grammar G and a string w of length n, decide if w can be obtained from G. This is the most basic parsing question and is a …

Privately Aligning Language Models with Reinforcement Learning

2023 · arXiv (Cornell University)

Positioned between pre-training and user deployment, aligning large language models (LLMs) through reinforcement learning (RL) has emerged as a prevailing strategy for training instruction following-models such as ChatGPT. In this work, we initiate the study …

Differentially Private Fine-tuning of Language Models

2024 · Journal of Privacy and Confidentiality

We give simpler, sparser, and faster algorithms for differentially private fine-tuning of large-scale pre-trained language models, which achieve the state-of-the-art privacy versus utility tradeoffs on many standard NLP tasks. We propose a meta-framework for this …