Biblio Discovery — Demo Discovery Service

69 hasil

Menampilkan 1–20 · 0,43 detik · RSS

Jurnal

TheoretiCS

Scopus

ISSN 2751-4838 · TheoretiCS Foundation e.V. · 69 artikel di indeks

  1. Artikel Jurnal

    Algorithmizing the Multiplicity Schwartz-Zippel Lemma

    Siddharth Bhandari; Prahladh Harsha; Mrinal Kumar dkk.

    TheoretiCS, Vol. Volume 4 · 2025 · Inggris · DOAJ Scopus

    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…

  2. Artikel Jurnal

    Directed Acyclic Outerplanar Graphs Have Constant Stack Number

    Paul Jungeblut; Laura Merker; Torsten Ueckerdt

    TheoretiCS, Vol. Volume 4 · 2025 · Inggris · DOAJ Scopus

    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…

  3. Artikel Jurnal

    Randomized Communication and Implicit Graph Representations

    Nathaniel Harms; Sebastian Wild; Viktor Zamaraev

    TheoretiCS, Vol. Volume 4 · 2025 · Inggris · DOAJ Scopus

    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…

  4. Artikel Jurnal

    Protocols for Quantum Weak Coin Flipping

    Atul Singh Arora; Jérémie Roland; Chrysoula Vlachou dkk.

    TheoretiCS, Vol. Volume 4 · 2025 · Inggris · DOAJ Scopus

    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…

  5. Artikel Jurnal

    Approximate Counting for Spin Systems in Sub-Quadratic Time

    Konrad Anand; Weiming Feng; Graham Freifeld dkk.

    TheoretiCS, Vol. Volume 4 · 2025 · Inggris · DOAJ Scopus

    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…

  6. Artikel Jurnal

    On Small-depth Frege Proofs for PHP

    Johan Håstad

    TheoretiCS, Vol. Volume 4 · 2025 · Inggris · DOAJ Scopus

    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…

  7. Artikel Jurnal

    Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time

    Nick Fischer; Leo Wennmann

    TheoretiCS, Vol. Volume 4 · 2025 · Inggris · DOAJ Scopus

    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…

  8. Artikel Jurnal

    A Simple $(1-ε)$-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching

    Sepehr Assadi

    TheoretiCS, Vol. Volume 4 · 2025 · Inggris · DOAJ Scopus

    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…

  9. Artikel Jurnal

    Learning Algorithms for Verification of Markov Decision Processes

    Tomáš Brázdil; Krishnendu Chatterjee; Martin Chmelik dkk.

    TheoretiCS, Vol. Volume 4 · 2025 · Inggris · DOAJ Scopus

    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…

  10. Artikel Jurnal

    Regular Languages in the Sliding Window Model

    Moses Ganardi; Danny Hucke; Markus Lohrey dkk.

    TheoretiCS, Vol. Volume 4 · 2025 · Inggris · DOAJ Scopus

    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…

  11. Artikel Jurnal

    3SUM in Preprocessed Universes: Faster and Simpler

    Shashwat Kasliwal; Adam Polak; Pratyush Sharma

    TheoretiCS, Vol. Volume 4 · 2025 · Inggris · DOAJ Scopus

    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…

  12. Artikel Jurnal

    Parameterized algorithms for block-structured integer programs with large entries

    Jana Cslovjecsek; Martin Koutecký; Alexandra Lassota dkk.

    TheoretiCS, Vol. Volume 4 · 2025 · Inggris · DOAJ Scopus

    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…

  13. Artikel Jurnal

    On the Constant-Depth Circuit Complexity of Generating Quasigroups

    Nathaniel A. Collins; Joshua A. Grochow; Michael Levet dkk.

    TheoretiCS, Vol. Volume 4 · 2025 · Inggris · DOAJ Scopus

    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…

  14. Artikel Jurnal

    A $(3+\varepsilon)$-Approximate Correlation Clustering Algorithm in Dynamic Streams

    Mélanie Cambus; Fabian Kuhn; Etna Lindy dkk.

    TheoretiCS, Vol. Volume 4 · 2025 · Inggris · DOAJ Scopus

    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…

  15. Artikel Jurnal

    Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs

    Susanna F. de Rezende; Jakob Nordström; Kilian Risse dkk.

    TheoretiCS, Vol. Volume 4 · 2025 · Inggris · DOAJ Scopus

    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…

  16. Artikel Jurnal

    A Note on Approximating Weighted Nash Social Welfare with Additive Valuations

    Yuda Feng; Shi Li

    TheoretiCS, Vol. Volume 4 · 2025 · Inggris · DOAJ Scopus

    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…

  17. Artikel Jurnal

    Completing the picture for the Skolem Problem on order-4 linear recurrence sequences

    Piotr Bacik

    TheoretiCS, Vol. Volume 4 · 2025 · Inggris · DOAJ Scopus

    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…

  18. Artikel Jurnal

    Multidimensional Quantum Walks, with Application to $k$-Distinctness

    Stacey Jeffery; Sebastian Zur

    TheoretiCS, Vol. Volume 4 · 2025 · Inggris · DOAJ Scopus

    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…

  19. Artikel Jurnal

    Computing Threshold Budgets in Discrete-Bidding Games

    Guy Avni; Suman Sadhukhan

    TheoretiCS, Vol. Volume 4 · 2025 · Inggris · DOAJ Scopus

    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…

  20. Artikel Jurnal

    A $4/3$ Approximation for $2$-Vertex-Connectivity

    Miguel Bosch-Calvo; Fabrizio Grandoni; Afrouz Jabal Ameli

    TheoretiCS, Vol. Volume 4 · 2025 · Inggris · DOAJ Scopus

    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…