69 hasil
Menampilkan 1–20 · 0,43 detik · RSS
TheoretiCS
Scopus
ISSN 2751-4838 · TheoretiCS Foundation e.V. · 69 artikel di indeks
-
Artikel Jurnal
Algorithmizing the Multiplicity Schwartz-Zippel Lemma
The multiplicity Schwartz-Zippel lemma asserts that over a field, a low-degree polynomial cannot vanish with high multiplicity very often on a sufficiently large product set. Since its discovery in a work of Dvir, Kopparty, Saraf and Sudan [SIAM J. Comput., 2013], the lemma has found numerous…
-
Artikel Jurnal
Directed Acyclic Outerplanar Graphs Have Constant Stack Number
The stack number of a directed acyclic graph $G$ is the minimum $k$ for which there is a topological ordering of $G$ and a $k$-coloring of the edges such that no two edges of the same color cross, i.e., have alternating endpoints along the topological ordering. We prove that the stack number of…
-
Artikel Jurnal
Randomized Communication and Implicit Graph Representations
We initiate the focused study of constant-cost randomized communication, with emphasis on its connection to graph representations. We observe that constant-cost randomized communication problems are equivalent to hereditary (i.e. closed under taking induced subgraphs) graph classes which admit…
-
Artikel Jurnal
Protocols for Quantum Weak Coin Flipping
Weak coin flipping is an important cryptographic primitive$\unicode{x2013}$it is the strongest known secure two-party computation primitive that classically becomes secure only under certain assumptions (e.g. computational hardness), while quantumly there exist protocols that achieve arbitrarily…
-
Artikel Jurnal
Approximate Counting for Spin Systems in Sub-Quadratic Time
We present two randomised approximate counting algorithms with $\widetilde{O}(n^{2-c}/\varepsilon^2)$ running time for some constant $c>0$ and accuracy $\varepsilon$: (1) for the hard-core model with fugacity $\lambda$ on graphs with maximum degree $\Delta$ when $\lambda=O(\Delta^{-1.5-c_1})$ where…
-
Artikel Jurnal
On Small-depth Frege Proofs for PHP
We study Frege proofs for the one-to-one graph Pigeon Hole Principle defined on the $n\times n$ grid where $n$ is odd. We are interested in the case where each formula in the proof is a depth $d$ formula in the basis given by $\land$, $\lor$, and $\neg$. We prove that in this situation the proof…
-
Artikel Jurnal
Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time
In this work we revisit the elementary scheduling problem $1||\sum p_j U_j$. The goal is to select, among $n$ jobs with processing times and due dates, a subset of jobs with maximum total processing time that can be scheduled in sequence without violating their due dates. This problem is NP-hard…
-
Artikel Jurnal
A Simple $(1-ε)$-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching
We present a simple semi-streaming algorithm for $(1-ε)$-approximation of bipartite matching in $O(\log{\!(n)}/ε)$ passes. This matches the performance of state-of-the-art "$ε$-efficient" algorithms -- the ones with much better dependence on $ε$ albeit with some mild dependence on $n$ -- while…
-
Artikel Jurnal
Learning Algorithms for Verification of Markov Decision Processes
We present a general framework for applying learning algorithms and heuristical guidance to the verification of Markov decision processes (MDPs). The primary goal of our techniques is to improve performance by avoiding an exhaustive exploration of the state space, instead focussing on particularly…
-
Artikel Jurnal
Regular Languages in the Sliding Window Model
We study the space complexity of the following problem: For a fixed regular language $L$, we receive a stream of symbols and want to test membership of a sliding window of size $n$ in $L$. For deterministic streaming algorithms we prove a trichotomy theorem, namely that the (optimal) space…
-
Artikel Jurnal
3SUM in Preprocessed Universes: Faster and Simpler
We revisit the 3SUM problem in the \emph{preprocessed universes} setting. We present an algorithm that, given three sets $A$, $B$, $C$ of $n$ integers, preprocesses them in quadratic time, so that given any subsets $A' \subseteq A$, $B' \subseteq B$, $C' \subseteq C$, it can decide if there exist…
-
Artikel Jurnal
Parameterized algorithms for block-structured integer programs with large entries
We study two classic variants of block-structured integer programming. Two-stage stochastic programs are integer programs of the form $\{A_i \mathbf{x} + D_i \mathbf{y}_i = \mathbf{b}_i\textrm{ for all }i=1,\ldots,n\}$, where $A_i$ and $D_i$ are bounded-size matrices. On the other hand, $n$-fold…
-
Artikel Jurnal
On the Constant-Depth Circuit Complexity of Generating Quasigroups
We investigate the constant-depth circuit complexity of the Isomorphism Problem, Minimum Generating Set Problem (MGS), and Sub(quasi)group Membership Problem (Membership) for groups and quasigroups (=Latin squares), given as input in terms of their multiplication (Cayley) tables. Despite decades of…
-
Artikel Jurnal
A $(3+\varepsilon)$-Approximate Correlation Clustering Algorithm in Dynamic Streams
Grouping together similar elements in datasets is a common task in data mining and machine learning. In this paper, we study streaming algorithms for correlation clustering, where each pair of elements is labeled either similar or dissimilar. The task is to partition the elements and the objective…
-
Artikel Jurnal
Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
We show exponential lower bounds on resolution proof length for pigeonhole principle (PHP) formulas and perfect matching formulas over highly unbalanced, sparse expander graphs, thus answering the challenge to establish strong lower bounds in the regime between balanced constant-degree expanders as…
-
Artikel Jurnal
A Note on Approximating Weighted Nash Social Welfare with Additive Valuations
We give the first $O(1)$-approximation for the weighted Nash Social Welfare problem with additive valuations. The approximation ratio we obtain is $e^{1/e} + ε\approx 1.445 + ε$, which matches the best known approximation ratio for the unweighted case. Both our algorithm and analysis are simple. We…
-
Artikel Jurnal
Completing the picture for the Skolem Problem on order-4 linear recurrence sequences
For almost a century, the decidability of the Skolem Problem - that is, the problem of finding whether a given linear recurrence sequence (LRS) has a zero term - has remained open. A breakthrough in the 1980s established that the Skolem Problem is indeed decidable for algebraic LRS of order at most…
-
Artikel Jurnal
Multidimensional Quantum Walks, with Application to $k$-Distinctness
While the quantum query complexity of $k$-distinctness is known to be $O\left(n^{3/4-1/4(2^k-1)}\right)$ for any constant $k \geq 4$, the best previous upper bound on the time complexity was $\widetilde{O}\left(n^{1-1/k}\right)$. We give a new upper bound of…
-
Artikel Jurnal
Computing Threshold Budgets in Discrete-Bidding Games
In a two-player zero-sum graph game, the players move a token throughout a graph to produce an infinite play, which determines the winner of the game. Bidding games are graph games in which in each turn, an auction (bidding) determines which player moves the token: the players have budgets, and in…
-
Artikel Jurnal
A $4/3$ Approximation for $2$-Vertex-Connectivity
The 2-Vertex-Connected Spanning Subgraph problem (2VCSS) is among the most basic NP-hard (Survivable) Network Design problems: we are given an (unweighted) undirected graph $G$. Our goal is to find a spanning subgraph $S$ of $G$ with the minimum number of edges which is $2$-vertex-connected, namely…