Results 21 to 30 of about 1,078 (84)
Additive Combinatorics and its Applications in Theoretical Computer Science
Theory of Computing, 2017 Additive combinatorics (or perhaps more accurately, arithmetic combinatorics) is a branch of mathematics which lies at the intersection of combinatorics, number theory, Fourier analysis and ergodic theory.
Shachar Lovett
semanticscholar +1 more source
Character Sums and Deterministic Polynomial Root Finding in Finite Fields [PDF]
, 2014 We obtain a new bound of certain double multiplicative character sums. We use this bound together with some other previously obtained results to obtain new algorithms for finding roots of polynomials modulo a prime $p$
E. Shparlinski +3 more
core +1 more source
The Threshold for Subgroup Profiles to Agree is Logarithmic
Theory of Computing, 2019 For primes p > 2 and e > 3 there are at least pe−3/e groups of order p2e+2 that have equal multisets of isomorphism types of proper subgroups and proper quotient groups, isomorphic character tables, and power maps.
James B. Wilson
semanticscholar +1 more source
Convex Geometry and its Applications
Oberwolfach Reports, 2019 The geometry of convex domains in Euclidean space plays a central role in several branches of mathematics: functional and harmonic analysis, the theory of PDE, linear programming and, increasingly, in the study of algorithms in computer science.
Franck Barthe, M. Henk, M. Ludwig
semanticscholar +1 more source
Two Compact Incremental Prime Sieves [PDF]
, 2015 A prime sieve is an algorithm that finds the primes up to a bound $n$. We say that a prime sieve is incremental, if it can quickly determine if $n+1$ is prime after having found all primes up to $n$. We say a sieve is compact if it uses roughly $\sqrt{n}$
Sorenson, Jonathan P.
core +3 more sources
Algorithms, Graph Theory, and Linear Equations in Laplacian Matrices
, 2011 The Laplacian matrices of graphs are fundamental. In addition to facilitating the application of linear algebra to graph theory, they arise in many practical problems.
D. Spielman
semanticscholar +1 more source
Super-polynomial approximation branching algorithms
RAIRO Oper. Res., 2016 We give sufficient conditions for deriving moderately exponential and/or parameterized time approximation schemata (i.e., algorithms achieving ratios 1 ± , for arbitrarily small) for broad classes of combinatorial optimization problems via a well-known ...
B. Escoffier, V. Paschos, E. Tourniaire
semanticscholar +1 more source
Weighted Integral of Infinitely Differentiable Multivariate Functions is Exponentially Convergent
Numerical Mathematics: Theory, Methods and Applications, 2019 We study the problem of a weighted integral of infinitely differentiable multivariate functions defined on the unit cube with the L∞-norm of partial derivative of all orders bounded by 1.
Guiqiao Xu
semanticscholar +1 more source
, 2020 We study the dynamic optimality conjecture, which predicts that splay trees are a form of universally efficient binary search tree, for any access sequence.
Russo, Luís M. S.
core +1 more source
Average case complexity of linear multivariate problems [PDF]
, 1992 We study the average case complexity of a linear multivariate problem $(\lmp)$ defined on functions of $d$ variables. We consider two classes of information.
Woźniakowski, Henryk
core +2 more sources